Codeforces 614E - Necklace - JavaScript

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

614E - Necklace

思路：如果奇数超过1个，那么答案是0；否则，所有数的gcd就是答案。

构造方案：每个数都除以gcd，如果奇数个仍旧不超过1个，找奇数个那个在中间（如果没有奇数默认a），其他的平均分到两边。

如果奇数个数超过1个，为了保证中间点之间的每个字母个数是偶数个，那么就拿上种情况的两个构造一段（两个对称拼成一段）。

代码：

#include<bits/stdc++.h>
using namespace std;
int a[];
const int N=2e6;
char s[N];
int gcd(int a,int b)
{
return b?gcd(b,a%b):a;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie();
int n;
cin>>n;
int cnt=;
for(int i=;i<n;i++)
{
cin>>a[i];
if(a[i]&)cnt++;
}
if(n==)
{
cout<<a[]<<endl;
for(int i=;i<a[];i++)
cout<<'a';
cout<<endl;
return ;
}
if(cnt>=)
{
cout<<<<endl;
for(int i=;i<n;i++)
{
for(int j=;j<a[i];j++)cout<<(char)(i+'a');
}
cout<<endl;
return ;
}
int ans=gcd(a[],a[]);
for(int i=;i<n;i++)
ans=gcd(ans,a[i]);
int l=1e6,r=1e6+;
int index=;
for(int i=;i<n;i++)
{
a[i]/=ans;
if(a[i]&)index=i;
}
cnt=;
for(int i=;i<n;i++)
{
if(a[i]&)cnt++;
}
for(int i=;i<a[index];i++)
{
s[r++]='a'+index;
//cout<<s[r-1]<<endl;
}
bool flag=true;
for(int i=;i<n;i++)
{
if(i==index)continue;
while(a[i]!=)
if(flag)
{
s[l--]='a'+i;
a[i]--;
flag=false;
}
else
{
s[r++]='a'+i;
a[i]--;
flag=true;
}
}
string as;
for(int i=l+;i<r;i++)as+=s[i];
if(cnt>=)for(int i=r-;i>l;i--)as+=s[i];
cout<<ans<<endl;
if(cnt>=)ans/=;
for(int i=;i<ans;i++)
cout<<as;
cout<<endl;
return ;
}