求HACK
查看原帖
求HACK
845394
MYXJWXR楼主2024/5/21 13:36
#include<bits/stdc++.h>
#define int unsigned long long
#define r(x) scanf("%ull",&x);
const int N=1e7+5,M=0xff,mod=47;
using namespace std;
string t,q;
int temp;
int n,f[N],p[M]; 
int g(int x,int y){
	if(x>y) return 0;
	return f[y]-f[x-1]*p[y-x+1];
}
signed main(){
	cin>>n;
	if(n%2==0) 
	{
		cout<<"NOT POSSIBLE";
		return 0;
	}
	cin>>t;
	t='#'+t;
	p[0]=1;
	for(int i=1;i<=n;i++)
	{
		p[i]=p[i-1]*mod;
		f[i]=f[i-1]*mod+(t[i]-'0');
	}
	int cnt=0;
	int mid=(n-1)/2;
	for(int i=1;i<=n;i++)//删除的是字符 t[i] 
	{
		int k1,k2;
		if(i<=mid) 
		{
			k1=p[mid-i+1]*g(1,i-1)+g(i+1,mid+1);
			k2=g(mid+2,n);
		}
		else
		{
			k1=g(1,mid);
			k2=p[n-i]*g(mid+1,i-1)+g(i+1,n);
		}
		if(k1==k2) 
		{
			if(!cnt) 
			{
				if(i<=mid) q=t.substr(mid+2,mid);
				else q=t.substr(1,mid);
			}
			if(temp!=k1)  temp=k1,cnt++;
		}
	}
	if(cnt==0) cout<<"NOT POSSIBLE";
	else if(cnt==1) cout<<q;
	else cout<<"NOT UNIQUE";
	return 0;
} 
2024/5/21 13:36
加载中...