求hack
查看原帖
求hack
333855
int233楼主2024/7/16 11:06

RT,目前WA一个测试点

// LUOGU_RID: 166305941
#include<iostream>
using namespace std;
string s;
int n,m,l,r,sum[100005],c[100005],tag[100005],d[100005],bel[100005],fa[100005];
int find(int x){
	if(x==fa[x]){
		return x;
	}
	return fa[x]=find(fa[x]);
}
int main(){
	cin>>s;
	n=(int)s.size();
	if(n==2){
		if(s[0]==s[1]){
			cout<<"YES";
			return 0;
		}
		cin>>m; 
		for(int i=1;i<=m;i++){
			cin>>l>>r;
			if(l==r){
				cout<<"YES"; 
				return 0; 
			}
		}
		cout<<"NO";
		return 0; 
	}
	for(int i=1;i<=n;i++){
		c[i]=s[i-1]-'a';
		if(i>=2){
			d[i]=(c[i]-c[i-1]+26)%26;
		//	cout<<d[i]<<" ";
		}
		else{
			d[i]=c[i];
	//		cout<<d[i]<<" ";
		}
	}
//	cout<<endl;
	for(int i=1;i<=n-i+2;i++){
		if(i==n-i+2){
			tag[i]=1;
		}
		d[i]=(d[i]+d[n-i+2])%26;
	//	cout<<d[i]<<" ";
		fa[i]=i;
		bel[i]=bel[n-i+2]=i;
	}
	cin>>m;
	for(int i=1;i<=m;i++){
		cin>>l>>r;
		if(bel[l]&&bel[r+1]){
		//	cout<<l<<" "<<r<<" "<<bel[l]<<" "<<bel[r+1]<<" "<<bel[2]<<" "<<bel[4]<<" MODIFIED UP!\n";
			fa[find(bel[l])]=find(bel[r+1]);
		}
	}
	tag[1]=1;
	for(int i=1;i<=n-i+2;i++){
		tag[find(i)]|=tag[i];
		sum[find(i)]=(sum[find(i)]+d[i])%26;
	}
	for(int i=1;i<=n-i+2;i++){
		if(find(i)==i){
			if(!tag[i]&&sum[i]){
				cout<<"NO";
				return 0;
			}
		} 
	}
	cout<<"YES";
	return 0;
} 
2024/7/16 11:06
加载中...