【每日一题】12月18日题目精讲

题号 NC111227
名称 Necklace
来源 CF613C
戳我进入往期每日一题汇总贴~
往期每日一题二期题单



如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情
每日一题QQ群:659028468

题解

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

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

总复杂度： $O(26+sum\{a\})$
参考代码：

#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);
            }
        }
    }
}

欢迎各位大佬来做题写题解，也欢迎大家踊跃在当日讨论贴中提问！