《回文构造机》题解

题目

XTX非常喜欢回文串,他认为回文会给自己带来好运,有一天他看到一个字符串突发奇想,如果将这个字符串所有字符打乱,然后每次操作只能挑选若干个能构成回文串的字符组合成一个字符串,XTX最少需要操作几次才能取完所有字符。(输出时,还要输出回文串的取法)

思路

过于简单了。

先求一个理论最小值。先记 x 为字符串, reverse(x) = reverse(x.begin(), x.end()) // 倒过来

不难发现回文串分两类,一类是 x + reverse(x), 一类是 $x + char + reverse(x)$。

那么问题来了,$x$ 和 reverse(x) 总共用掉的字母都是成对的,即用掉的字母都是二的倍数。

那显然输入时有的字母可能只出现了奇数次,那就得要一个一个地使用 x + char + reverse(x) 的形式耗掉它们!!!也就是理论最小值!!!

然而,显然理论最小值是可以取到的。下面构造:

第一次,把所有的能拿出来的字母对子拿出来,凑一个回文数,随便一个出现奇数次的字母放中间;

记下来,只剩下零零散散的字母了,一个一个放得了!

所以,答案就是出现了奇数次的字母个数!啊,等一下。。。

警钟敲烂:如果没有出现了奇数次的字母,那么答案是 1 ,要特判!!!

ACnum++!!!