hash求调
查看原帖
hash求调
302888
algorith楼主2023/2/3 18:18
#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
const int N=2000005;
string s,ans="";
map<ull,bool>mp;
ull p[N],sum[N];
bool usd=false;
int main(){
	p[0]=1;
	for(int i=1;i<=30;++i)p[i]=p[i-1]*28;
	int n;cin>>n;
	if(n%2==0){
		printf("NOT POSSIBLE");
		return 0;
	}
	cin>>s;
	for(int i=1;i<=n;++i)sum[i]=sum[i-1]*28+s[i-1]-'A';
	for(int i=0;i<n;++i){
		if(i<n/2){
			if(sum[n/2+1]-sum[i+1]*p[n/2-i]+sum[i]*p[n/2-i]==sum[n]-sum[n/2+1]*p[n/2]){
				if(usd&&!mp[sum[n]-sum[n/2+1]*p[n/2]]){
//					cout<<i<<" 1 "<<ans<<endl;ans="";
//					for(int j=0;j<=n/2;++j)if(i!=j)ans+=s[j];
//					cout<<ans<<endl;
					printf("NOT UNIQUE");
					return 0;
				}
				mp[sum[n]-sum[n/2+1]*p[n/2]]=1;
				if(!usd)
				for(int j=0;j<=n/2;++j)if(i!=j)ans+=s[j];
				usd=true;
			}
		}else if(i==n/2){
			if(sum[n/2]==sum[n]-sum[n/2+1]*p[n/2]){
				if(usd&&!mp[sum[n/2]]){
//					cout<<i<<" 2 "<<ans<<endl;ans="";
//					for(int j=0;j<n/2;++j)ans+=s[j];
//					cout<<ans<<endl;
					printf("NOT UNIQUE");
					return 0;
				}
				
				mp[sum[n/2]]=1;
				if(!usd)
				for(int j=0;j<n/2;++j)ans+=s[j];
				usd=true;
			}
		}else{
			if(sum[n/2]==sum[n]-sum[i+1]*p[n-i-1]+(sum[i]-sum[n/2]*p[i-n/2])*p[n-i-1]){
				if(usd&&!mp[sum[n/2]]){
//					cout<<i<<" 3 "<<ans<<endl;ans="";
//					for(int j=0;j<n/2;++j)ans+=s[j];
//					cout<<ans<<endl;
					printf("NOT UNIQUE");
					return 0;
				}
				mp[	sum[n/2]]=1;
				if(!usd)
				for(int j=0;j<n/2;++j)ans+=s[j];
				usd=true;
			}
		}
	}
	if(ans!="")cout<<ans;
	else cout<<"NOT POSSIBLE";
	return 0;
}
2023/2/3 18:18
加载中...