CF883H

男娘i 2024-04-20 10:27 46阅读 0赞

##  ##

CF883H

### 题意： ###

> 给你一个字符串，需要把它以最小的划分次数划分为x个长度相等的回文串，可以重新排列。

### 解法： ###

> 大模拟一个。  
> 分别统计出现一次的字符和出现两次的字符，如果没有出现一次的字符，那么所有字符出现次数均为偶数，说明本身便可以排列成回文串。  
> 如果某个字符出现次数为偶次，可以拆分为多个 $ \\frac\{cnt\}\{2\} $ 个相同字符存入，如果出现次数为奇数次，则先存入单个统计并计数减1，再存入双个统计，如果单个字符数量不足，则需要用双个字符填充。

### CODE: ###

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N = 4e5 + 100; char a[N],cnt[N * 2],s[N]; int Hash[300],n; int main() { scanf("%d",&n); scanf("%s",s+1); for(int i = 1 ; i <= n ; i++) Hash[s[i]]++; int L = 1, R = n; for (int i = 1; i <= 200; i++) if (Hash[i] & 1) a[L++] = (char)i, Hash[i]--; for (int i = 1; i <= 200; i++) if (Hash[i]) { while (Hash[i]--) a[R--] = (char)i; } L--; int ans, len; for(ans = 1 ; ans <= n ; ans++) { if(n % ans) continue; len = n / ans; if((n - L) / 2 >= ans * (len / 2)) break; } printf("%d\n",ans); L = 1, R = n; for(int i = 1 ; i <= ans; i++) { int ll = N + 10, rr = N + 10; if(len & 1) cnt[rr++] = a[L++]; for(int j = 1; j <= len/2; j++) { cnt[--ll] = a[R--]; cnt[rr++] = a[R--]; } for(int j = ll; j < rr; j++) printf("%c",cnt[j]); printf(" "); } // system("pause"); return 0; }

转载于:https://www.cnblogs.com/Repulser/p/11396865.html

发表评论取消回复

表情：

评论列表（有 0 条评论，46人围观）

还没有评论，来说两句吧...

相关阅读

相关 CF883H

CF883H 题意： > 给你一个字符串，需要把它以最小的划分次数划分为x个长度相等的回文串，可以重新排列。解法： > 大模拟一个。 > 分别...

男娘i/ 2024年04月20日 10:27/ 0 赞/ 47 阅读

相关【简单图论】CF898 div4 H

[Problem - H - Codeforces][] 题意： ![4b37a99e5b464ba681c364f7b47a7a52.png][] 思路：手玩一下样

爱被打了一巴掌/ 2024年03月01日 01:46/ 0 赞/ 80 阅读

相关【组合计数】CF1866 H

[Problem - H - Codeforces][] 题意 ![ae0ad641c2c842abbdd97f19e7c95ea2.png][] 思路不知道这种tr

末蓝、/ 2024年02月20日 09:05/ 0 赞/ 35 阅读

相关【React】883- React hooks 之 useEffect 学习指南

![format_png][] 摘要如果你不想阅读整篇文章，可以快速浏览这份摘要。要是某些部分不容易理解，你可以往下滚动寻找相关的内容去阅读。

灰太狼/ 2022年11月04日 00:53/ 0 赞/ 177 阅读

相关 CF - A. Fraction

-------------------- 题目连接：[http://codeforces.com/contest/854/problem/A][http_codeforces

系统管理员/ 2022年06月08日 03:50/ 0 赞/ 192 阅读

相关 CF#263

昨天没打，今天写了一下，前三题都没有难度吧。 A. Appleman and Easy Task time limit per test 1 second memory

冷不防/ 2022年03月31日 10:38/ 0 赞/ 206 阅读

相关 CF1081A

CF1081A > 题意: > > > 从 ? 开始每次减去一个不是 ?的约数的数，问最小能得到多少? > > 做法： > > > 因为 $ n $ 一

叁歲伎倆/ 2021年12月22日 13:25/ 0 赞/ 186 阅读

相关 CF1090H Linearization 位运算、前缀和

[传送门][Link 1] -------------------- 有点神仙的题目首先注意到对于串\\(s\\)，\\(b=s\_0\\)一定会比\\(b = s\_

小灰灰/ 2021年11月26日 09:42/ 0 赞/ 218 阅读

相关 cf 1179 C

目录 A B C A 模拟出A不是最大值的情况，存起来。最多有n个。当A为最大值的时候，后面n-1个数开始循环。查询分两种情况讨论就行了

比眉伴天荒/ 2021年11月01日 10:20/ 0 赞/ 267 阅读

相关 CF611H New Year and Forgotten Tree

题目描述给定你一棵树，可是每个节点上的编号看不清了，只能辨别它的长度。现在用问号的个数代表每个节点编号那个数字的长度，请你还原这一颗树，任意输出一个方案，有SPJ来检验

古城微笑少年丶/ 2021年10月19日 01:20/ 0 赞/ 228 阅读