P11190 「KDOI-10」反回文串 观察到两个特殊性质： 对于特殊性质 A，易证一定有 ⌊n2⌋\lfloor \frac{n}{2} \rfloor 组长度为 2 或 3 的分配方案。 对于特殊性质 A 相反的，即有一种字母数量大于 ⌊n2⌋\lfloor \frac{n}{2} \rfloor，可以先把数量小的看成同一种颜色，此时就与特殊性质 B 一样了。设多的字母为 C，少的为 D，那么如果 D=0 或 D=1 且 D 在中心位置，那么这样是一定无解的，否则易证一定有一种分配方式，且这种方式要保证每组中都含有字母 D，所以最多的方案数就是字母 D 的数量。 代码： #include using namespace std; const int N=1e5+5; const int M=150; int n,cnt,key; char s[N]; int t[M]; int qu[M][N],sz[M]; vector ans[N]; int tmp[N]; int main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); int c,q; cin>>c>>q; while(q--){ cin>>n; key=-1,cnt=0; for(int i='a';i>s[i],++t[s[i]]; for(int i='a';i=n+1>>1) key=i; if(key>1; int tot=0; for(int i='a';i=1;i--) if(s[i]!=key){r=i;break;} ans[1].clear(); ans[2].clear(); ans[1].push_back(l); ans[2].push_back(r); for(int i=l+1;i2){ ans[i].push_back(ans[1].back()); ans[1].pop_back(); } else if(ans[2].size()>2){ ans[i].push_back(ans[2].back()); ans[2].pop_back(); } } } } cout `#include using namespace std; const int N=1e5+5; const int M=150; int n,cnt,key; char s[N]; int t[M]; int qu[M][N],sz[M]; vectorint> ans[N]; int tmp[N]; int main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); int c,q; cin>>c>>q; while(q--){ cin>>n; key=-1,cnt=0; for(int i='a';i'z';i++) t[i]=0,sz[i]=0; for(int i=1;i>s[i],++t[s[i]]; for(int i='a';i'z';i++) if(t[i]>=n+1>>1) key=i; if(key0){ for(int i=1;i int ch=s[i]; qu[ch][++sz[ch]]=i; } cnt=n>>1; int tot=0; for(int i='a';i'z';i++){ for(int j=1;jsz[i];j++){ tmp[++tot]=qu[i][j]; } } for(int i=1;i ans[i].push_back(tmp[i]); ans[i].push_back(tmp[i+cnt]); } if(n&1){ ans[1].push_back(tmp[n]); } } else{ if(t[key]==n){ cout"Shuiniao\n"; continue; } if(t[key]==n-1){ if((n&1)&&s[(n+1)/2]!=key){ cout"Shuiniao\n"; continue; } cout"Huoyu\n1\n"" "; for(int i=1;i" "; cout"\n"; continue; } int l=0,r=0; cnt=2; for(int i=1;iif(s[i]!=key){l=i;break;} for(int i=n;i>=1;i--) if(s[i]!=key){r=i;break;} ans[1].clear(); ans[2].clear(); ans[1].push_back(l); ans[2].push_back(r); for(int i=l+1;iif(s[i]==key) ans[1].push_back(i); for(int i=1;iif(s[i]==key) ans[2].push_back(i); for(int i=l+1;i if(s[i]!=key){ cnt++; ans[cnt].clear(); ans[cnt].push_back(i); } } for(int i=1;i if(ans[i].size()2){ if(ans[1].size()>2){ ans[i].push_back(ans[1].back()); ans[1].pop_back(); } else if(ans[2].size()>2){ ans[i].push_back(ans[2].back()); ans[2].pop_back(); } } } } cout"Huoyu\n""\n"; for(int i=1;i sort(ans[i].begin(),ans[i].end()); coutans[i].size()" "; for(int j=0;jans[i].size();j++) coutans[i][j]" "; cout"\n"; ans[i].clear(); } } return 0; }`
P11190 「KDOI-10」反回文串
笔记