CF613C Necklace（字符串 构造）

构造一个环使其成为回文串的切割数最大。

当超过两种颜色的数量为奇数时无法构造出回文串，直接输出。

根据切割的特点，容易想到构造回文串形式的单位循环节，则答案为循环节的数量，其中循环节的最大数量为各颜色数量的 gcd。

这里需要分类讨论一下（记各颜色数量的GCD为 d）：
（1）循环节中存在奇数数量颜色，循环节个数等于d，结果不可能再大于这个数。
（2）循环节中不存在奇数数量颜色，循环节个数等于d/2，但是还可以从循环节的中间切割，例如 baab baab 切割后为 abba abba，答案乘以2，仍为d。

代码如下：

#include<bits/stdc++.h>
using namespace std;
char s[100005];
int a[26],b[26],n;
int main(){
    scanf("%d",&n);
    int sum=0,cnt=0;
    for(int i=0;i<n;++i){
        scanf("%d",a+i),sum+=a[i]; 
        if(a[i]&1)++cnt;
    }
    if(cnt>1){
        puts("0");
        for(int i=0;i<n;++i){
            char c='a'+i;
            while(a[i]--)putchar(c);
        }
        return 0;
    }
    int d=a[0];
    memcpy(b,a,sizeof b);
    for(int i=1;i<n;++i)
        d=__gcd(d,a[i]);
    printf("%d\n",d); 
    for(int i=0;i<n;++i)b[i]/=d;
    cnt=0;
    for(int i=0;i<n;++i)cnt+=b[i]&1;
    if(cnt>1){
        d/=2;
        for(int i=0;i<n;++i)b[i]*=2;
    } 
    int l=0,r=sum/d-1;
    for(int i=0;i<n;++i){
        char c='a'+i;
        if(b[i]&1){
            s[sum/d/2]=c;
            --b[i];
        }
        cnt=b[i]/2;
        for(int j=0;j<cnt;++j)s[l++]=c,s[r--]=c;
    }
    while(d--)printf("%s",s);
}