A5072.构造回文串 题解

思路

这个题对于锰锌来说可能有些困难，这个题还是有思维难度的，但不多。

题目就是给出一个字符串 $s$，把 $s$ 拆了选字符重排，且重排过后这个字符串是回文串，求能组成这个回文串的最大长度是什么。

我们首先研究一下样例 bcdaca，我们把他拆成 [b,c,d,a,c,a]，有一种做法是选出 [b,c,a,c,a] 组成 acbca 字符串，即可得到样例输出的 5。

怎么搞的呢？令一个字符在这个字符串出现次数是 $a$，在最左右两边分别加上 $\lfloor \frac{a}{2}\rfloor$ 个这样的字符，那么两边的回文部分搞定了。

那么中间的那个字符怎么搞呢？这时候要分类讨论。

• 如果每一个字符出现的次数均为偶数，那么无法添加中心字符。

• 如果有一个字符出现的次数是奇数，把他那个字符拿一个下来，放在中间。

最后把组成的字符串求长度就可以了。

我的题解挺绕的，我也说不清楚，可能我表达有问题吧。

代码

分类讨论一定要讨论清楚。

我的代码没有直接组成字符串再求长度。

#include <iostream>
#include <unordered_map>
using namespace std;
int main(){
	char c;
	unordered_map<char,int> m;
	while ((c=getchar())!=EOF){
		++m[c];
	}
	int sm=0;
	int t=0;
	for (const auto &item : m){
		int te=item.second;
		if (te&1){
			t=1;
		}
		te/=2;
		sm+=te;
	}
	cout<<(sm<<1)+t<<endl;
	return 0;
}