链接

大意: 给定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("");
}

最新文章

  1. Android 监听ScrollView的滑动
  2. 工具 cocoapods和插件
  3. Spring aop 原始的工作原理的理解
  4. iOS游戏截图或广告图尺寸要求
  5. 提高生产性工具(四) - XML数据库的尝试
  6. Ubuntu修改文件关联
  7. ACM题目————Robot Motion
  8. web api 跨域请求,ajax跨域调用webapi
  9. 【2013南京区域赛】部分题解 hdu4802—4812
  10. cocos2d-x游戏开发系列教程-坦克大战游戏启动界面的编写
  11. [array] leetcode - 41. First Missing Positive - Hard
  12. Linq GroupJoin
  13. C++ 初步
  14. [Swift]LeetCode652. 寻找重复的子树 | Find Duplicate Subtrees
  15. alias命令详解:给命令设置别名
  16. 用python优雅打开文件及上下文管理协议
  17. mvc 文件下载
  18. 1118 Birds in Forest (25 分)
  19. 3G开发遇到的问题
  20. ArrayList初始化的4种方法

热门文章

  1. $好玩的分词——python jieba分词模块的基本用法
  2. linux常用命令(替换)
  3. MySQL笔记(三)由txt文件导入数据
  4. label语句、break语句和continue语句
  5. MIME协议(详解范例)
  6. python函数作用域LEGB
  7. Python3基础 str format 位置参数与关键字参数
  8. 浅入浅出JS中的eval及json
  9. JavaScript 时间格式
  10. BZOJ5131: [CodePlus2017年12月]可做题2