CF883H

男娘i 2024-04-20 10:27 61阅读 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 条评论，61人围观）

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

相关阅读

相关 CF883H

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

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

相关 CF790 div4 F(双指针） H（逆序对）

乐，被div4薄纱了没想到把所有出现次数>=k的数放一个数组里然后双指针还有H，连逆序对都没看出来，嘻感觉以后还是写写div4算了，写什么div2啊，caibi

- 日理万妓/ 2024年03月27日 10:24/ 0 赞/ 81 阅读

相关【二分+滑动窗口优化DP】CF883 I

[Problem - 883I - Codeforces][] 题意： ![8cbfe31eb3c0466a951b35362970764b.png][] ![d1200

Myth丶恋晨/ 2024年03月23日 17:23/ 0 赞/ 43 阅读

相关【状态设计优化DP+位运算】CF871div4 H

[Problems - Codeforces][] 题意：给定一个序列，问有多少子序列，使得子序列的元素之与的位数是K ![3fff87c32c8d4316adbbb0

阳光穿透心脏的1/2处/ 2024年03月22日 13:26/ 0 赞/ 46 阅读

相关【简单图论】CF898 div4 H

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

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

相关【组合计数】CF1866 H

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

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

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

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

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

相关 CF#263

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

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

相关 CF1090H Linearization 位运算、前缀和

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

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

相关 CF611H New Year and Forgotten Tree

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

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