bzoj 3916 题解，20200224-G

题意： 有三个好朋友喜欢在一起玩游戏,A君写下一个字符串S,B君将其复制一遍得到T,C君在T的任意位置(包括首尾)插入一个字符得到U.现在你得到了U,请你找出S. 2<=N<=2000001 ## 理解 阅读题意后发现，我们需要找到那个为奇数个的字母。如果有多个或者没有奇数个的字母，说明有锅，输出无解。 然后愉快地开始枚举那个字母，然后哈希。注意要分5种情况：第一个，最后一个，中间那个，第一个->中间那个，中间那个->最后一个。后两种情况哈希需要分段。记录下合法的插入位置，最后再看有几个合法的插入位置。 然后提交，发现WA。 发现需要求得是不同的S字符串，而非不同的插入位置。然后判重。 提交，发现TLE。 为什么会TLE？因为我用的是暴力判重，最坏复杂度$\Theta(N^2)$ 最后得出重要论断：由于每一次只有一个插入位置，所以要么是后面半段，要么是前面半段。如图。  所以我们只需要开两个bool，分别记录前/后半段是否可能作为答案，然后最后判断是否重复就好了。于是顺利把判重降到了$\Theta(N)$ ## 代码 ``` #include<bits/stdc++.h> #define int long long using namespace std; char c[2100001]; int n,nn; int a[2100001]; int lst[100]; int pos[100],npos=0,univ; unsigned long long pw[2100001],hsh[2100001]; int flag[10]; int geths(int a,int b){ return hsh[b]-hsh[a-1]*pw[b-a+1]; } bool check(int a1,int b1,int a2,int b2){ return geths(a1,b1)==geths(a2,b2)?1:0; } signed main(){ cin>>nn; cin>>(c+1); n=strlen(c+1); pw[0]=1; for(int i=1;i<=n;++i){ a[i]=c[i]-'A'+1; pw[i]=pw[i-1]*29; hsh[i]=hsh[i-1]*29+a[i]; lst[a[i]]++; } for(int i=1;i<=26;++i){ if(lst[i]%2==1){ pos[++npos]=i; } } if(npos>1){ puts("NOT POSSIBLE"); return 0; } univ=pos[1]; for(int i=1;i<=n;++i){ if(a[i]==univ){ if(i==1){ if(check(2,(n+1)/2,(n+1)/2+1,n)) flag[2]=1; } else if(i==n){ if(check(1,(n+1)/2-1,(n+1)/2,n-1)) flag[1]=1; } else if(i<(n+1)/2){ if(check(1,i-1,(n+1)/2+1,(n+1)/2+i-1)&&check(i+1,(n+1)/2,(n+1)/2+i,n)) flag[2]=1; } else if(i==(n+1)/2){ if(check(1,i-1,i+1,n)) flag[1]=flag[2]=1; } else if(i>(n+1)/2){ if(check(i+1,n,i-(n+1)/2+1,(n+1)/2-1)&&check((n+1)/2,i-1,1,i-(n+1)/2)) flag[1]=1; } } } if(!flag[1]&&!flag[2]){ puts("NOT POSSIBLE"); } else{ if(flag[1]&&flag[2]){ for(int i=(n+1)/2+1,j=1;i<=n&&j<=n/2;++i,++j) if(c[i]!=c[j]){ puts("NOT UNIQUE"); return 0; } } if(flag[2]){ for(int i=(n+1)/2+1;i<=n;++i) putchar(c[i]); puts(""); } else if(flag[1]){ for(int i=1;i<=n/2;++i) putchar(c[i]); puts(""); } } return 0; } ```