地址：https://ac.nowcoder.com/acm/contest/272#question
看到比赛的时候到学校熄灯的时间只有50分钟左右了，当时只A了1、3题
现在给出自己做题时的思路（1、3题）
P.S.其他会做的题目陆续会更新上来
【第一题】
很明显的贪心，由于要值最小，那么不如选择直接构造，把一段长度为k的1移动到正中间位置即可，由于是偶数，更方便了；
位移操作采用快速幂实现
代码：
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #define mod 1000000007 6 #define int long long//由于我有一丢丢懒... 7 using namespace std; 8 inline int read(){ 9 char chr=getchar(); int f=1,ans=0; 10 while(!isdigit(chr)) {if(chr=='-') f=-1;chr=getchar();} 11 while(isdigit(chr)) {ans=(ans<<3)+(ans<<1);ans+=chr-'0';chr=getchar();} 12 return ans*f; 13 } 14 void write(int x){ 15 if(x<0) putchar('-'),x=-x; 16 if(x>9) write(x/10); 17 putchar(x%10+'0'); 18 } 19 int n,m; 20 int ans=0; 21 int ksm(int x,int p){ 22 if(p==0) return 1; 23 if(p==1) return x%mod; 24 int t=ksm(x,p>>1); 25 if(p&1) return t*t%mod*x%mod; 26 else return t*t%mod; 27 } 28 signed main(){ 29 n=read(),m=read(); 30 n=max(n,m); 31 m-=2; 32 ans+=(ksm(2,n-1)+1)%mod; 33 ans=(ans+(ksm(2,m)-1)*ksm(2,((n-m-2)>>1)+1)%mod)%mod; 34 cout<<ans; 35 return 0; 36 }
【第三题】
求期望？
刚好前几天写了一篇期望DP专题，于是果断跳过第二题，直接做第三题。
上面这个链接博客理解透彻的话，可以推出一个方程：
f[i][j]表示第i次取数时白球个数为j的概率，其中第一维由于只与上一个有关，可以压掉（这里不给出了）
f[i][j]+=f[i-1][j]*(double)(i-j+1)/(double)(i+1)+f[i-1][j-1]*(double)(j-1)/double(i+1)
ans=∑f[n][i]*i (i=1~n+1)
然而n<=10^6
肿么办？
根据经验，有些求概率期望的题目是有通项公式的，于是把n=0~100全部输出来(部分)
1.5000000
2.0000000
2.5000000
3.0000000
3.5000000
4.0000000
4.5000000
5.0000000
5.5000000公差为0.5的等差数列！！
于是...
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 inline int read(){ 7 char chr=getchar(); int f=1,ans=0; 8 while(!isdigit(chr)) {if(chr=='-') f=-1;chr=getchar();} 9 while(isdigit(chr)) {ans=(ans<<3)+(ans<<1);ans+=chr-'0';chr=getchar();} 10 return ans*f; 11 } 12 void write(int x){ 13 if(x<0) putchar('-'),x=-x; 14 if(x>9) write(x/10); 15 putchar(x%10+'0'); 16 } 17 int n; 18 double ans=0; 19 double f[2000005]; 20 int main(){ 21 n=read(); 22 ans=0.5*n+1.0; 23 printf("%.7lf",ans); 24 return 0; 25 }
【订正】
【第二题】
@#￥%……&*·！第二题这么水，然鹅没有 做 想出来
首先我们要知道一个异或的性质:
x^x=0
x^x^x=x
x^x^x^x=0
若令n个相同的x异或和=f(n)
则有：
$$f(n)=
egin{cases}
0& ext{x为偶数}\
x& ext{x为奇数}
end{cases}$$LaTeX真难用。。。
然后这道题就没有什么难的了，遍历一遍就OK了
代码：
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 inline int read(){ 7 char chr=getchar(); int f=1,ans=0; 8 while(!isdigit(chr)) {if(chr=='-') f=-1;chr=getchar();} 9 while(isdigit(chr)) {ans=(ans<<3)+(ans<<1);ans+=chr-'0';chr=getchar();} 10 return ans*f; 11 } 12 void write(int x){ 13 if(x<0) putchar('-'),x=-x; 14 if(x>9) write(x/10); 15 putchar(x%10+'0'); 16 } 17 const int M=500005; 18 int n,a[500005],ans=0,x; 19 int head[M<<1],nxt[M<<1],ver[M<<1],tot,cnt[M]; 20 inline void add(int x,int y){ver[++tot]=y;nxt[tot]=head[x];head[x]=tot;} 21 void dfs(int x,int fa){ 22 cnt[x]=1; 23 for(int i=head[x];i;i=nxt[i]){ 24 if(ver[i]==fa) continue; 25 dfs(ver[i],x); 26 cnt[x]+=cnt[ver[i]]; 27 } 28 int p=n-cnt[x],s=p+1; 29 for(int i=head[x];i;i=nxt[i]){ 30 if(ver[i]==fa) continue; 31 p+=s*cnt[ver[i]];s+=cnt[ver[i]]; 32 }//统计子树从一端到达另一端的次数 33 if(p&1) ans^=a[x];//异或的性质 34 } 35 int main(){ 36 n=read(); 37 for(int i=1;i<n;i++){ 38 int x=read(),y=read(); 39 add(x,y);add(y,x); 40 } 41 for(int i=1;i<=n;i++) a[i]=read(); 42 dfs(1,0); 43 printf("%d",ans); 44 return 0; 45 }
【第五题】
O(nm) 可以过，看了题解才会做...
难点：离线的思想把空间压成O（m+n）的操作很玄妙！
代码：
见：https://paste.ubuntu.com/p/XwBdHh9BNG/（头好晕，不太打得进代码，先贴个链接吧。）