题解：AT_cf17_final_e Combination Lock

lfg123456 · 2025-10-30 19:41:59 · 题解

include <bits/stdc++.h>

define int long long

define maxm 200005

using namespace std; int n,m,len,l,r,d[maxm],fa[maxm]; bool flag=true; string s; void init(){ for(int i=0;i<=len;i++){ fa[i]=i; d[i]=s[i]-s[i-1]; } } int getfa(int x){ if(fa[x]==x)return x; return fa[x]=getfa(fa[x]); } void merge(int l,int r){ int x=getfa(l); int y=getfa(r); if(x!=y){ fa[x]=y; d[x]=d[y]=d[x]+d[y]; } return; } signed main(){ cin>>s; cin>>n; len=s.length(); init(); for(int i=0;i<=len;i++){ merge(i,len-i); } for(int i=1;i<=n;i++){ cin>>l>>r; merge(l-1,r); } for(int i=0;i<=len;i++){ if(d[i]%26==0||getfa(i)!=i)continue; flag=false; } if(flag==true)cout<<"YES\n"; else cout<<"NO\n"; return 0; }