WNJXYKの博客

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 Input2:

6
ABCDEF

Sample Input3:

9
ABABABABA

Sample Output1:

ABC

Sample Output2:

NOT POSSIBLE

Sample Output3:

NOT UNIQUE

HINT

对于100%的数据 2<=N<=2000001

题解

我们只需要分情况讨论加入字母在第一个，[第一个，最中间]，(最中间，最后]三种情况讨论就行了！
最后注意要用字符数组和scanf/printf…

代码

<

pre class=”lang:c++ decode:true ” title=”BZOJ 3019″>/**************************************************************
Problem: 3916
User: wnjxyk
Language: C++
Result: Accepted
Time:756 ms
Memory:6664 kb
****************************************************************/
#include
#include
using namespace std;
int n;
char str[2000010];
char Ans[2000010];
char tmpAns[2000010];
int flag=0;
int delta1,delta2;
int delta;
int hl;
inline bool check(char a[],char b[],int len){
for (int i=0;i<len;i++) if (a[i]!=b[i]) return false;
return true;
}
int main(){
//freopen(“friends.in”,”r”,stdin);
//freopen(“friends.out”,”w”,stdout);
scanf(“%d%s”,&n,&str);
hl=(n-1)/2;
memset(Ans,’\0′, sizeof(Ans));
if (!(n&1)){printf(“NOT POSSIBLE\n”);return 0;}
flag=1;
memset(tmpAns,’\0′, sizeof(tmpAns));
delta1=1;
delta2=1+hl;
delta=0;
for (int i=1;i<=hl;i++){
if (str[delta1+i-1]!=str[delta2+i-1])
flag–;
else
tmpAns[i-1]=str[delta1+i-1];
if (!flag) break;
}
if (flag){
if (strlen(Ans)==0 || check(tmpAns,Ans,hl)){
strcpy(Ans,tmpAns);
}else{
printf(“NOT UNIQUE\n”);
return 0;
}
}
flag=2;
memset(tmpAns,’\0′, sizeof(tmpAns));
delta1=0;
delta2=hl;
delta=0;
for (int i=1;i<=hl;i++){
if (str[delta1+i-1]!=str[delta2+i-1+delta]){
flag–;
delta++;
i–;
}else
tmpAns[i-1]=str[delta1+i-1];
if (!flag) break;
}
if (flag){
if (strlen(Ans)==0 || check(tmpAns,Ans,hl)){
strcpy(Ans,tmpAns);
}else{
printf(“NOT UNIQUE\n”);
return 0;
}
}
flag=2;
memset(tmpAns,’\0′, sizeof(tmpAns));
delta1=0;
delta2=hl+1;
delta=0;
for (int i=1;i<=hl;i++){
if (str[delta1+i-1+delta]!=str[delta2+i-1]){
flag–;
delta++;
i–;
}else
tmpAns[i-1]=str[delta2+i-1];
if (!flag) break;
}
if (flag){
if (strlen(Ans)==0 || check(tmpAns,Ans,hl)){
strcpy(Ans,tmpAns);
}else{
printf(“NOT UNIQUE\n”);
return 0;
}
}
if (strlen(Ans)==0)
printf(“NOT POSSIBLE\n”);
else
printf(“%s\n”,Ans);
return 0;
}