10
8
2015
0

3916: [Baltic2014]friends

3916: [Baltic2014]friends

Time Limit: 30 Sec  Memory Limit: 256 MB
Submit: 392  Solved: 142
[Submit][Status][Discuss]

Description

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

 

Input

第一行一个数N,表示U的长度.
第二行一个字符串U,保证U由大写字母组成

 

Output

输出一行,若S不存在,输出"NOT POSSIBLE".若S不唯一,输出"NOT UNIQUE".否则输出S.

 

Sample Input

Sample Input1:
7
ABXCABC


Sample Input2:

6
ABCDEF

Sample Input3:

9
ABABABABA

Sample Output

Sample Output1:

ABC

Sample Output2:

NOT POSSIBLE

Sample Output3:

NOT UNIQUE

HINT

 

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

 

 

 

Source

    暴力。。正反做两次暴力匹配。。然后判断是否存在相同的串。。。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int f1,f2,m,n,pos;
char s[2000100];
int main(){
	scanf("%d",&m);
	scanf("%s",s+1);
	n = m>>1;
	if (m+1&1) return printf("NOT POSSIBLE"),0;
	for (pos=1;pos<=n && s[pos+n]==s[pos];pos++);
	for (;pos<=n && s[pos+n+1]==s[pos];pos++);
	if (pos>n) f1 = 1;
	for (pos=0;pos<n && s[m-pos]==s[m-pos-n];pos++);
	for (;pos<n && s[m-pos]==s[m-pos-n-1];pos++);
	if (pos>=n) f2 = 1;
	if (f1 && f2){
		for (pos=1;pos<=n && s[pos]==s[pos+n+1];pos++);
		if (pos<=n) printf("NOT UNIQUE");
		else for (int i=1;i<=n;i++) printf("%c",s[i]);
	}
	else if (f1) for (int i=1;i<=n;i++) printf("%c",s[i]);
	else if (f2) for (int i=n+2;i<=m;i++) printf("%c",s[i]);
	else printf("NOT POSSIBLE");
}
Category: BZOJ题解 | Tags: | Read Count: 361

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com