【牛客网周赛32】个人解题思路

地址：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)=
\begin{cases}
0& \text{x为偶数}\\
x& \text{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/（头好晕，不太打得进代码，先贴个链接吧。）