这款CF 613C项链是如何构造的？

本文共计792个文字，预计阅读时间需要4分钟。

为了构建一个由n种颜色珠子组成的连成环的项链，其中每种颜色ai个，我们需要设计一个方案，使得从某个点断开项链后，形成的两段是回文的。

一种可能的方案是：

1.将每种颜色的珠子按照顺序排列，形成一个环。

2.从环的任意位置开始，按照颜色顺序将珠子依次连接，形成一个完整的环。

3.在连接过程中，确保每次连接的珠子颜色与上一段项链的结束颜色相同，以保持回文性质。

例如，如果n=3，每种颜色有2个珠子，我们可以这样排列：

- 红珠子-红珠子-蓝珠子-蓝珠子-绿珠子-绿珠子-红珠子-红珠子

在这个例子中，从任意一个红珠子开始，向任意方向移动，都会得到一个回文串。

给你n (1 ≤ n ≤ 26)种颜色的珠子，每种ai个，你需要把它们全部使用连成环，使其从‘某处’断开后形成的串是回文的，这样的某处尽可能多。求出任意一种方案

构造

#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <functional>
#include <cstdlib>
#include <queue>
#include <stack>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define MEM(s) memset(s,0,sizeof(s));
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define RepD(i,n) for(int i=n;i>=0;i--)
#define pb push_back
const int maxn = 100000 + 10;
int n,a[maxn];
vector<int> v1,v2;
int gcd(int a,int b){if (!b) return a;return gcd(b,a%b);}
void pri(){
For(i,n)
For(j,a[i]) printf("%c",i+'a'-1);
cout<<endl;
}
int main() {
cin>>n;
int tot=0;
For(i,n) {
cin>>a[i];
tot+=a[i];
if (a[i]&1) v1.pb(i);
else if (a[i]) v2.pb(i);
}
int m1=v1.size(),m2=v2.size();
if (m1+m2==1)
{
cout<<tot<<endl;
pri();
return 0;
}
int g=0;
For(i,n) g=gcd(a[i],g);
if (tot&1) {
if (m1>=2) {
cout<<"0"<<endl;
pri();
return 0;
}
cout<<g<<endl;
a[v1[0]]-=g;
For(k,g)
{
For(i,n) For(j,a[i]/g/2) printf("%c",i+'a'-1);
printf("%c",v1[0]+'a'-1);
ForD(i,n) For(j,a[i]/g/2) printf("%c",i+'a'-1);
}
cout<<endl;
} else {
if (m1) {
cout<<"0"<<endl;
pri();
return 0;
}
cout<<g<<endl;
For(k,g)
{

if (k&1) For(i,n) For(j,a[i]/g) printf("%c",i+'a'-1);
else ForD(i,n) For(j,a[i]/g) printf("%c",i+'a'-1);
}
cout<<endl;


}

return 0;
}