bzoj 3916 题解,20200224-G

2020-02-24 00:17:07


题意:

有三个好朋友喜欢在一起玩游戏,A君写下一个字符串S,B君将其复制一遍得到T,C君在T的任意位置(包括首尾)插入一个字符得到U.现在你得到了U,请你找出S.

2<=N<=2000001

理解

阅读题意后发现,我们需要找到那个为奇数个的字母。如果有多个或者没有奇数个的字母,说明有锅,输出无解。

然后愉快地开始枚举那个字母,然后哈希。注意要分5种情况:第一个,最后一个,中间那个,第一个->中间那个,中间那个->最后一个。后两种情况哈希需要分段。记录下合法的插入位置,最后再看有几个合法的插入位置。

然后提交,发现WA。

发现需要求得是不同的S字符串,而非不同的插入位置。然后判重。

提交,发现TLE。

为什么会TLE?因为我用的是暴力判重,最坏复杂度 $\Theta(N^2)$

最后得出重要论断:由于每一次只有一个插入位置,所以要么是后面半段,要么是前面半段。如图。

pic1

所以我们只需要开两个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;
}