目录
Description
有三个好朋友喜欢在一起玩游戏,A君写下一个字符串S,B君将其复制一遍得到T,C君在T的任意位置(包括首尾)插入一个字符得到U.现在你得到了U,请你找出S.
Input
第一行一个数N,表示U的长度.
第二行一个字符串U,保证U由大写字母组成
Output
输出一行,若S不存在,输出"NOT POSSIBLE".若S不唯一,输出"NOT UNIQUE".否则输出S.
Sample Input1
7
ABXCABC
Sample Output1
ABC
Sample Input2
6
ABCDEF
Sample Output2
NOT POSSIBLE
Sample Input3
9
ABABABABA
Sample Output3
NOT UNIQUE
Hint
对于100%的数据 2<=N<=2000001
题解
这题很显然是一道字符串(Hash)，但是有一些坑点
由于我将若S不唯一看成了若插入的位置不唯一，创造了我的首(WA)
接着，我却将每次可以的(S)记录下来，导致时间代价太大，造成了我的首(TLE)，(TLE)代码如下：
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
using namespace std;
typedef unsigned long long ull;
const int L=2000005,E=100007;
char s[L],Out[L];
int l,Ans;
ull power[L],h[L];
void PutIn(int id)//超时的关键
{
if(id<=l/2)
{
for(int i=1;i<=l/2;++i) Out[i]=s[i+l/2+1];
return;
}
for(int i=1;i<=l/2;++i) Out[i]=s[i];
}
int Check(int id)//超时的关键
{
if(id<=l/2)
{
for(int i=1;i<=l/2;++i)
if(Out[i]!=s[i+l/2+1]) return 1;
return 0;
}
for(int i=1;i<=l/2;++i)
if(Out[i]!=s[i]) return 1;
return 0;
}
int main()
{
scanf("%d
%s",&l,s+1);
if(l%2==0) {puts("NOT POSSIBLE");goto end;}
power[0]=1;
for(int i=1;i<=l;++i) power[i]=power[i-1]*E;
for(int i=1;i<=l;++i) h[i]=h[i-1]*E+s[i];
for(int i=1;i<=l;++i)
{
if(i<=l/2)
{
if((h[l/2+1]-h[i]*power[l/2+1-i]+h[i-1]*power[l/2+1-i])
==(h[l]-h[l/2+1]*power[l/2]))
if(!Ans) {Ans=i;PutIn(i);}
else if(Check(i))
{puts("NOT UNIQUE");goto end;}
}
else
{
if(h[l/2]
==(h[l]-h[i]*power[l-i]+h[i-1]*power[l-i]-h[l/2]*power[l-l/2-1]))
if(!Ans) {Ans=i;PutIn(i);}
else if(Check(i))
{puts("NOT UNIQUE");goto end;}
}
}
if(!Ans) puts("NOT POSSIBLE");
else
{
for(int i=1;i<=l/2;++i) printf("%c",Out[i]);
putchar('
');
}
end:
return 0;
}
注意到上面代码中造成(TLE)的罪魁祸首，如果我们能够(O(1))来比较的话那么问题不就迎刃而解了吗
字符串(Hash)的作用是什么？
将字符转化成数，从而方便的计算与比较大小，（大雾
(My~Code)
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
using namespace std;
typedef unsigned long long ull;
const int L=2000005,E=100007;
char s[L];
int l,Ans;
ull power[L],h[L],hAns;
int main()
{
scanf("%d
%s",&l,s+1);
if(l%2==0) {puts("NOT POSSIBLE");goto end;}
power[0]=1;
for(int i=1;i<=l;++i) power[i]=power[i-1]*E;
for(int i=1;i<=l;++i) h[i]=h[i-1]*E+s[i];
for(int i=1;i<=l;++i)
{
if(i<=l/2)
{
if((h[l/2+1]-h[i]*power[l/2+1-i]+h[i-1]*power[l/2+1-i])
==(h[l]-h[l/2+1]*power[l/2]))//此处的过程需要用草稿纸或大脑子
if(!Ans) Ans=i,hAns=h[l]-h[l/2+1]*power[l/2];
else if(h[l]-h[l/2+1]*power[l/2]!=hAns)
{puts("NOT UNIQUE");goto end;}
}
else
{
if(h[l/2]
==(h[l]-h[i]*power[l-i]+h[i-1]*power[l-i]-h[l/2]*power[l-l/2-1]))
if(!Ans) Ans=i,hAns=h[l/2];
else if(h[l/2]!=hAns)
{puts("NOT UNIQUE");goto end;}
}
}
if(!Ans) puts("NOT POSSIBLE");
else
{
if(Ans<=l/2)
{
for(int i=l/2+2;i<=l;++i) printf("%c",s[i]);
putchar('
');
}
else
{
for(int i=1;i<=l/2;++i) printf("%c",s[i]);
putchar('
');
}
}
end:
return 0;
}