Necklace CodeForces - 613C (构造)
2024-09-01 01:14:17
大意: 给定n种珠子, 第i种有$a_i$个, 求将珠子穿成项链, 使得能使切开后的项链回文的切口尽量多
若有一种以上珠子为奇数, 显然不能为回文, 否则最大值一定是$gcd(a_1,a_2,...,a_n)$
若有一个奇数, 直接分成$gcd(a_1,a_2,...,a_n)$块, 每块内奇数放中间, 其余对称分
无奇数的话, $gcd(a_1,a_2,...,a_n)$一定是2的倍数, 可以将2块和为1块, 两块间对称分即可
#include <iostream>
#include <algorithm>
#include <cstdio>
#define PER(i,a,n) for(int i=n;i>=a;--i)
#define REP(i,a,n) for(int i=a;i<=n;++i)
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;} const int N = 4e5+10, INF = 0x3f3f3f3f;
int n, cnt, ans, sum;
int a[N];
char buf[N]; int main() {
scanf("%d", &n);
REP(i,1,n) {
scanf("%d", a+i);
ans = gcd(ans, a[i]);
cnt += a[i]&1;
sum += a[i];
}
if (cnt>1) {
puts("0");
REP(i,1,n) REP(j,1,a[i]) putchar(i-1+'a');
return puts(""),0;
}
if (cnt) {
int len = sum/ans, cur = len/2+1;
REP(i,1,n) if (a[i]&1) {
buf[cur] = i-1+'a';
++cur; break;
}
REP(i,1,n) REP(j,1,a[i]/ans/2) buf[cur]=buf[len-cur+1]=i-1+'a',++cur;
printf("%d\n", ans);
REP(i,1,ans) REP(j,1,len) putchar(buf[j]);
return puts(""),0;
}
int len = sum/ans*2, cur = len/2+1;
REP(i,1,n) REP(j,1,a[i]/ans) buf[cur]=buf[len-cur+1]=i-1+'a',++cur;
printf("%d\n", ans);
REP(i,1,ans/2) REP(j,1,len) putchar(buf[j]);
puts("");
}
最新文章
- Android 监听ScrollView的滑动
- 工具 cocoapods和插件
- Spring aop 原始的工作原理的理解
- iOS游戏截图或广告图尺寸要求
- 提高生产性工具(四) - XML数据库的尝试
- Ubuntu修改文件关联
- ACM题目————Robot Motion
- web api 跨域请求,ajax跨域调用webapi
- 【2013南京区域赛】部分题解 hdu4802—4812
- cocos2d-x游戏开发系列教程-坦克大战游戏启动界面的编写
- [array] leetcode - 41. First Missing Positive - Hard
- Linq GroupJoin
- C++ 初步
- [Swift]LeetCode652. 寻找重复的子树 | Find Duplicate Subtrees
- alias命令详解:给命令设置别名
- 用python优雅打开文件及上下文管理协议
- mvc 文件下载
- 1118 Birds in Forest (25 分)
- 3G开发遇到的问题
- ArrayList初始化的4种方法