CF883H

CF883H

题意：

给你一个字符串，需要把它以最小的划分次数划分为x个长度相等的回文串，可以重新排列。

解法：

大模拟一个。

分别统计出现一次的字符和出现两次的字符，如果没有出现一次的字符，那么所有字符出现次数均为偶数，说明本身便可以排列成回文串。

如果某个字符出现次数为偶次，可以拆分为多个 $ \frac{cnt}{2} $ 个相同字符存入，如果出现次数为奇数次，则先存入单个统计并计数减1，再存入双个统计，如果单个字符数量不足，则需要用双个字符填充。

CODE:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>using namespace std; const int N = 4e5 + 100;
char a[N],cnt[N * 2],s[N];
int Hash[300],n;int main() {
    scanf("%d",&n);
    scanf("%s",s+1);
    for(int i = 1 ; i <= n ; i++)
        Hash[s[i]]++;
    int L = 1, R = n;
    for (int i = 1; i <= 200; i++)
        if (Hash[i] & 1)
        a[L++] = (char)i, Hash[i]--;
    for (int i = 1; i <= 200; i++)
        if (Hash[i]) {
        while (Hash[i]--)
            a[R--] = (char)i;
    }
    L--;
    int ans, len;
    for(ans = 1 ; ans <= n ; ans++) {
        if(n % ans) continue;
        len = n / ans;
        if((n - L) / 2 >= ans * (len / 2)) break;
    }
    printf("%d\n",ans);
    L = 1, R = n;
    for(int i = 1 ; i <= ans; i++) {
        int ll = N + 10, rr = N + 10;
        if(len & 1) cnt[rr++] = a[L++];
        for(int j = 1; j <= len/2; j++) {
            cnt[--ll] = a[R--];
            cnt[rr++] = a[R--];
        }
        for(int j = ll; j < rr; j++)
            printf("%c",cnt[j]);
        printf(" ");
    }
//    system("pause");
    return 0;
}