P11190 「KDOI-10」反回文串

用户头像 发布于 1 天前 7 次阅读 OI

P11190 「KDOI-10」反回文串

观察到两个特殊性质：

  1. 对于特殊性质 A，易证一定有 ⌊n2⌋\lfloor \frac{n}{2} \rfloor 组长度为 2 或 3 的分配方案。
  2. 对于特殊性质 A 相反的，即有一种字母数量大于 ⌊n2⌋\lfloor \frac{n}{2} \rfloor，可以先把数量小的看成同一种颜色，此时就与特殊性质 B 一样了。设多的字母为 C，少的为 D，那么如果 D=0 或 D=1 且 D 在中心位置，那么这样是一定无解的，否则易证一定有一种分配方式，且这种方式要保证每组中都含有字母 D，所以最多的方案数就是字母 D 的数量。

代码：

#include<bits/stdc++.h>
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<int> 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<=n;i++) cin>>s[i],++t[s[i]];
        for(int i='a';i<='z';i++) if(t[i]>=n+1>>1) key=i;
        
        if(key<0){
            for(int i=1;i<=n;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;j<=sz[i];j++){
                    tmp[++tot]=qu[i][j];
                }
            }
            
            for(int i=1;i<=cnt;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"<<n<<" ";
                for(int i=1;i<=n;i++) cout<<i<<" ";
                cout<<"\n";
                continue;
            }
            
            int l=0,r=0;
            cnt=2;
            for(int i=1;i<=n;i++) if(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;i<=n;i++) if(s[i]==key) ans[1].push_back(i);
            for(int i=1;i<l;i++) if(s[i]==key) ans[2].push_back(i);
            
            for(int i=l+1;i<r;i++){
                if(s[i]!=key){
                    cnt++;
                    ans[cnt].clear();
                    ans[cnt].push_back(i);
                }
            }
            
            for(int i=1;i<=cnt;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"<<cnt<<"\n";
        for(int i=1;i<=cnt;i++){
            sort(ans[i].begin(),ans[i].end());
            cout<<ans[i].size()<<" ";
            for(int j=0;j<ans[i].size();j++) cout<<ans[i][j]<<" ";
            cout<<"\n";
            ans[i].clear();
        }
    }
    return 0;
}