题解归档 - cf613C

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf613C
• 本地来源：problems/cf613C/idea.md
• 题目链接：https://codeforces.com/contest/613/problem/C
• 原始标题：613C Necklace

思路

613C Necklace

题意

用全部珠子串成环形项链。在某两颗相邻珠子之间切开，若剩余链是回文，则该切口「美丽」。求美丽切口数量的最大值，并输出一种方案。

关键观察

美丽切口具有对称性：若某处切口美丽，则相对该回文中心的对称位置也是美丽切口。反复分割后，整条项链被分成若干等长片段；片段数只能是 0 或 gcd(a_1,…,a_n) 的约数。

记 g = gcd(a_i)，奇数颜色个数 odd（a_i 为奇数的颜色数）。

构造

1. 基块 block（长度 sum/g）：颜色 i 放 a_i/g 颗；奇数放中间，偶数左右对称分配。
2. ans = g：交替拼接 block 与 reverse(block)，共 g 段。
3. ans = 1：输出 block。
4. ans = 0：任意合法排列（如按颜色顺序输出）。

样例

• 4 2 1：g=1，odd=1 → 答案 1，如 aabcbaa（即 abacaba 的旋转）。
• 4（单色）：答案 4，aaaa。
• 1 1：odd=2 → 0。

复杂度

O(sum) 输出。

代码

来源：problems/cf613C/solution.cpp

/* Author: likely
 * Time: 2026-06-08 06:11:53
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=100005;
ll a[maxn+5];
string s,t,blk,ans;
ll gcdll(ll x,ll y){
    while(y){
        x%=y;
        swap(x,y);
    }
    return x;
}
int main(){
    ll n,i,j,k,zc,cnt,g,ansc,oddc;
    char ch;
    cin>>n;
    g=a[1];
    oddc=0;
    for(i=1;i<=n;i++){
        cin>>a[i];
        g=gcdll(g,a[i]);
        if(a[i]%2) oddc++;
    }
    if(n==1) ansc=a[1];
    else if(oddc>=2) ansc=0;
    else if(oddc==0) ansc=g;
    else ansc=1;
    if(n==1){
        ans="";
        for(i=1;i<=a[1];i++) ans+='a';
        cout<<ansc<<endl<<ans<<endl;
        return 0;
    }
    for(i=1;i<=n;i++){
        ch=(char)('a'+i-1);
        cnt=a[i]/g;
        for(j=1;j<=cnt/2;j++) s+=ch;
        if(cnt%2) t+=ch;
    }
    for(i=n;i>=1;i--){
        ch=(char)('a'+i-1);
        cnt=a[i]/g;
        for(j=1;j<=cnt/2;j++) blk+=ch;
    }
    blk=s+t+blk;
    if(ansc==0){
        ans="";
        for(i=1;i<=n;i++){
            ch=(char)('a'+i-1);
            for(j=1;j<=a[i];j++) ans+=ch;
        }
        cout<<ansc<<endl<<ans<<endl;
        return 0;
    }
    if(ansc==1){
        cout<<ansc<<endl<<blk<<endl;
        return 0;
    }
    ans="";
    for(i=0;i<g;i++){
        if(i%2==0) ans+=blk;
        else{
            t=blk;
            reverse(t.begin(),t.end());
            ans+=t;
        }
    }
    cout<<ansc<<endl<<ans<<endl;
    return 0;
}