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;
}`