2017.8.2 Noip2018模拟测试赛（十八）

日期：	八月二日	总分：	300分
难度：	提高 ~ 省选	得分：	40分（又炸蛋了！！）

题目列表：

T1：分手是祝愿

T2：残缺的字符串

T3：树点涂色

赛后心得：

哎，T1求期望，放弃。

看T2像是 KMP 打完发现并不可做，有感觉像是 FFT，放弃

T3我打了个树剖套线段树，调了好久，发现修改操作处理不了，又想到 LCT……

比赛结束！！…… MMP

题解：

T1：分手是祝愿

期望dp，首先，最优解肯定是从大到小，有开的灯就把它按灭

（因为不按的话，编号小的不会对大的有影响，所以会导致这盏灯一直亮着）

不考虑 k，f[i] 表示最优 i 步按得次数的期望。

有 i 种情况能按到对的按钮，n-i 种按错，则状态转移方程：

$$ f_i=frac{i}{n}+frac{n-i}{n}(1+f_i+f_{i+1}) $$

(n个开关，i个正确，其他n-i个会增加一个错误，需f[n+1]+f[n]次操作变到i-1)

化简得：

$$ f_i=frac{n+(n-i)f_{i+1}}{i} $$

显然 f[n]=1，k 以下也为1，直接递推求解。

最后 $ans=sum_{i=1}^n f_i$

CODE:

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<vector>
 4 using namespace std;
 5 
 6 #define mod 100003LL
 7 int n,k,cnt,ans,fac,inv[100005];
 8 int g[100005],f[100005];
 9 bool vis[100005];
10 vector<int> fc[100005];
11 
12 int main(){
13     scanf("%d%d",&n,&k);
14     for(int i=1;i<=n;i++)scanf("%d",vis+i);
15     fac=inv[0]=inv[1]=1;
16     for(int i=2;i<=n;i++){
17         inv[i]=1LL*(mod-mod/i)*inv[mod%i]%mod;
18         fac=1LL*fac*i%mod;
19     }
20     for(int i=1;i<=n;i++)
21     for(int j=i;j<=n;j+=i)fc[j].push_back(i);
22     for(int i=n;i>=1;i--)
23         if(vis[i]){
24             for(int j=0;j<fc[i].size();j++)
25                 vis[fc[i][j]]^=1;
26             cnt++;
27         }
28     if(cnt<=k){
29         printf("%d
",1LL*cnt*fac%mod);
30         return 0;
31     }
32     g[n]=1;
33     for(int i=1;i<=k;i++)g[i]=1;
34     for(int i=n-1;i>k;i--)g[i]=(1LL*(n-i)*g[i+1]%mod+n)*inv[i]%mod;
35     for(int i=cnt;i>=1;i--)(ans+=g[i])%=mod;
36     printf("%d
",1LL*ans*fac%mod);
37 }

T2：残缺的字符串

看起来像是KMP，实际上是FFT。

题解戳这里，我认为他讲的已经很清楚了！

CODE：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<complex>
 4 using namespace std;
 5 
 6 const double PI=acos(-1);
 7 typedef complex<long double> cmplx;
 8 int n,m,bit=1,rev[1200005],ans[300005];
 9 cmplx a[1200005],b[1200005];
10 char A[300005],B[300005];
11 
12 void get_rev(){
13     while(bit<=n+m)bit<<=1;
14     for(int i=0;i<bit;i++)
15     rev[i]=(rev[i>>1]>>1)|(i&1)*(bit>>1);
16 }
17 
18 void FFT(cmplx a[],int dft){
19     for(int i=0;i<bit;i++)
20         if(i<rev[i])swap(a[i],a[rev[i]]);
21     for(int i=1;i<bit;i<<=1){
22         cmplx W=exp(cmplx(0,dft*PI/i));
23         for(int j=0;j<bit;j+=i<<1){
24             cmplx w(1,0);
25             for(int k=j;k<i+j;k++,w*=W){
26                 cmplx x=a[k];
27                 cmplx y=w*a[k+i];
28                 a[k]=x+y,a[k+i]=x-y;
29             }
30         }
31     }
32     if(dft==-1)for(int i=0;i<bit;i++)a[i]/=bit;
33 }
34 
35 int main(){
36     scanf("%d%d",&m,&n);
37     scanf("%s%s",A,B);
38     for(int i=0;i<m;i++)
39         if(A[i]!='*')a[m-i-1]=(long double)1.0/(A[i]-'a'+1+1e3);
40     for(int i=0;i<n;i++)
41         if(B[i]!='*')b[i]=(long double)B[i]-'a'+1+1e3;
42     get_rev();
43     FFT(a,1),FFT(b,1);
44     for(int i=0;i<bit;i++)a[i]*=b[i];
45     FFT(a,-1);
46     for(int i=m-1;i<=n-1;i++){
47         int x=a[i].real()+0.25;
48         if(fabs(a[i].real()-x)<1e-8){
49             ans[++ans[0]]=i-m+2;
50         }
51     }
52     printf("%d
",ans[0]);
53     for(int i=1;i<=ans[0];i++)
54         printf("%d ",ans[i]);
55 }

其实这种解法像 Hash 一样有几率发生碰撞的，可能小数加小数，变为整数，但如同 Hash 正确率够高，不用担心。

卡精度啊！！我用了 long double 慢的像屎一样MMP

T3：树点涂色

LCT+线段树

题解戳这里

CODE：

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 using namespace std;
  5 
  6 #define lch ch[0]
  7 #define rch ch[1]
  8 int n,m,opt,x,y,cnt,tot=0,h[100005];
  9 int dep[100005],siz[100005],son[100005];
 10 int tid[100005],rak[100005],tp[100005],fa[100005];
 11 int maxv[400005],add[4000005];
 12 struct Edge{
 13     int x,next;
 14 }e[200005];
 15 struct Splay{
 16     int fa,ch[2];
 17 }v[100005];
 18 
 19 inline void add_edge(int x,int y){
 20     e[++tot].x=y;
 21     e[tot].next=h[x],h[x]=tot;
 22 }
 23 
 24 void dfs1(int x,int father,int deep){
 25     siz[x]=1,fa[x]=father,dep[x]=deep;
 26     v[x].fa=father;
 27     for(int i=h[x];i;i=e[i].next){
 28         if(e[i].x==father)continue;
 29         dfs1(e[i].x,x,deep+1);
 30         siz[x]+=siz[e[i].x];
 31         if(siz[e[i].x]>siz[son[x]])son[x]=e[i].x;
 32     }
 33 }
 34 
 35 void dfs2(int x,int top){
 36     tid[x]=++cnt,rak[cnt]=x,tp[x]=top;
 37     if(son[x])dfs2(son[x],top);
 38     for(int i=h[x];i;i=e[i].next){
 39         if(e[i].x==fa[x]||e[i].x==son[x])continue;
 40         dfs2(e[i].x,e[i].x);
 41     }
 42 }
 43 
 44 void pushdown(int o){
 45     add[o<<1]+=add[o];
 46     add[o<<1|1]+=add[o];
 47     maxv[o<<1]+=add[o];
 48     maxv[o<<1|1]+=add[o];
 49     add[o]=0;
 50 }
 51 
 52 void build(int o,int l,int r){
 53     if(r-l==1){
 54         maxv[o]=dep[rak[l]]+1;
 55     }else{
 56         int mid=l+r>>1;
 57         build(o<<1,l,mid),build(o<<1|1,mid,r);
 58         maxv[o]=max(maxv[o<<1],maxv[o<<1|1]);
 59     }
 60 }
 61 
 62 void update(int o,int l,int r,int x,int y,int a){
 63     if(l>=x&&r<=y){
 64         add[o]+=a,maxv[o]+=a;
 65     }else{
 66         pushdown(o);
 67         int mid=l+r>>1;
 68         if(x<mid)update(o<<1,l,mid,x,y,a);
 69         if(y>mid)update(o<<1|1,mid,r,x,y,a);
 70         maxv[o]=max(maxv[o<<1],maxv[o<<1|1]);
 71     }
 72 }
 73 
 74 int query(int o,int l,int r,int x,int y){
 75     if(l>=x&&r<=y)return maxv[o];
 76     pushdown(o);
 77     int mid=l+r>>1;
 78     int ans=0;
 79     if(x<mid)ans=max(ans,query(o<<1,l,mid,x,y));
 80     if(y>mid)ans=max(ans,query(o<<1|1,mid,r,x,y));
 81     return ans;
 82 }
 83 
 84 int LCA(int x,int y){
 85     while(tp[x]!=tp[y]){
 86         if(dep[tp[x]]<dep[tp[y]])swap(x,y);
 87         x=fa[tp[x]];
 88     }
 89     if(dep[x]>dep[y])swap(x,y);
 90     return x;
 91 }
 92 
 93 inline bool isroot(int x){
 94     return v[v[x].fa].lch!=x&&v[v[x].fa].rch!=x;
 95 }
 96 
 97 inline void rotate(int x){
 98     int y=v[x].fa,z=v[y].fa;
 99     if(!isroot(y))v[z].ch[v[z].rch==y]=x;
100     v[x].fa=z;
101     bool k=v[y].rch==x;
102     v[y].ch[k]=v[x].ch[k^1];
103     if(v[x].ch[k^1])v[v[x].ch[k^1]].fa=y;
104     v[x].ch[k^1]=y,v[y].fa=x;
105 }
106 
107 inline void splay(int x){
108     while(!isroot(x)){
109         int y=v[x].fa,z=v[y].fa;
110         if(!isroot(y)){
111             if(v[y].lch==x^v[z].lch==y)rotate(x);
112             else rotate(y);
113         }
114         rotate(x);
115     }
116 }
117 
118 void access(int x){
119     for(int y=0;x;y=x,x=v[x].fa){
120         splay(x);
121         if(v[x].rch){
122             int k=v[x].rch;
123             while(v[k].lch)k=v[k].lch;
124             update(1,1,n+1,tid[k],tid[k]+siz[k],1);
125         }
126         v[x].rch=y;
127         if(y){
128             int k=y;
129             while(v[k].lch)k=v[k].lch;
130             update(1,1,n+1,tid[k],tid[k]+siz[k],-1);
131         }
132     }
133 }
134 
135 int main(){
136 //    puts("silly pcj!!!")
137     scanf("%d%d",&n,&m);
138     for(int i=1;i<n;i++){
139         scanf("%d%d",&x,&y);
140         add_edge(x,y);
141         add_edge(y,x);
142     }
143     dfs1(1,0,0),dfs2(1,1);
144     build(1,1,n+1);
145     for(int i=1;i<=m;i++){
146         scanf("%d",&opt);
147         if(opt!=2)scanf("%d",&x);
148         else scanf("%d%d",&x,&y);
149         if(opt==1)access(x);
150         if(opt==2){
151             int lca=LCA(x,y);
152             int sum1=query(1,1,n+1,tid[x],tid[x]+1);
153             int sum2=query(1,1,n+1,tid[y],tid[y]+1);
154             int sum=query(1,1,n+1,tid[lca],tid[lca]+1);
155             printf("%d
",sum1+sum2-2*sum+1);
156         }
157         if(opt==3)
158             printf("%d
",query(1,1,n+1,tid[x],tid[x]+siz[x]));
159     }
160 }