【每日一题】12月18日题目Necklace题解

知识点：构造算法
题意：已知每个字母的出现次数，让你构造一个环，使得存在尽可能多的切法保证切开后为一个回文串。
思路：

1. 对于所有的字母的次数而言，如果存在不小于两个奇数，那么显然无论如何也不可能构成回文串。因此输出0即可。
2. 如果奇数只有1个或者全部是偶数，那么可以构造出回文串。怎样构造让断点尽可能多呢？可以这样思考：若存在至少两个断点，即对于回文串仍有断点，不妨设回文串中的断点形成了 和 两个子串，那么由新断点生成的回文串则是 。
   例如：对于字符串 "abcbaabcbaabcba" 而言，总共有3个断点： "abcba abcba abcba" ，经过切断、平移的操作，生成的新串仍然是回文串。
   对于给定的出现次数，求出所有的出现次数的最大公约数 。
   ① 若奇数次数的个数为1，这样可以构造出 个相等的回文串 。每个回文串的右端可以提供一个断点（显然这样切断是有效的，因为切断后平移和原串相等），这样总共有 个断点。
   ② 若奇数次数的个数为0，也就是说字母出现次数均为偶数，这样可以构造出 个相等的回文串，每个回文串可以提供两个有效断点（回文串的中间和右端）。例如对于字符串 "abba abba abba"而言，这是三个回文串abba的连接，其中每个右端点切断的有效性显而易见，而每个回文串的中间也是可以切断的，切断重组后形成 "baab baab baab"，也是合法的回文串。这样总共断点的个数也是 个。
   显然这样构造是最优的，因为不可能构造出超过 个断点，每个子段要么长度为1不可继续分割（例如"aaa"，三个断点后每个子段长度都是1），要么存在至少一个奇数，这也是不可分割的。

总复杂度：
参考代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int a[33];
int main(){
    int n,i,j,cnt=0,mark;
    cin>>n;
    for(i=0;i<n;i++)
        cin>>a[i],cnt+=a[i]&1,mark=(a[i]&1)?i:mark;
    if(cnt>=2){
        cout<<0<<endl;
        for(i=0;i<n;i++){
            while(a[i]--)printf("%c",'a'+i);
        }
        return 0;
    }
    int g=a[0];
    for(i=0;i<n;i++){
        g=__gcd(g,a[i]);
    }
    cout<<g<<endl;
    if(cnt==1){
        for(i=0;i<n;i++)a[i]/=g;
        while(g--){
            for(i=0;i<n;i++){
                for(j=0;j<a[i]/2;j++)printf("%c",'a'+i);
            }
            printf("%c",'a'+mark);
            for(i=n-1;i>=0;i--){
                for(j=0;j<a[i]/2;j++)printf("%c",'a'+i);
            }
        }
    }
    if(cnt==0){
        for(i=0;i<n;i++)a[i]/=g,a[i]*=2;
        g/=2;
        while(g--){
            for(i=0;i<n;i++){
                for(j=0;j<a[i]/2;j++)printf("%c",'a'+i);
            }
            for(i=n-1;i>=0;i--){
                for(j=0;j<a[i]/2;j++)printf("%c",'a'+i);
            }
        }
    }
}