CF600C题解

题意

有一串字符串 \(S\)，设改变 \(S\) 中的任意一个字符称为 1 次转变（交换任意 2 个字符不算转变次数），求在操作最少的情况下可得到的回文字符串

正文

♦ 算法：找规律
♦ 准备知识：桶排序

对于一个回文串，有两种情况：

1. 回文串字符数为偶数，如 assddssa，易得其中每种字符数量都是偶数。

2. 回文串字符数为奇数，如 asdfdsa，易得其中除了最中间的字符数量为奇数，其余都是偶数。

再想到排序是不算转变次数的，很容易想到桶排序。

将 \(S\) 中的每个字符对应的桶加 1，通过上述规律可以知道，每个为偶数的桶不需要转变，每个为奇数的桶执行以下操作：

去掉一个字符使桶为偶数，将去除的字符留下备用，而接下来就是对这些字符进行转变，见例子。

字符串：
aesdffdaa
桶排后：
31122
aesdf
操作后的桶：
20022
aesdf
剩余字符：
aes

设剩下的字符按字典序排序后组成的字符串为 \(B\)，长度为 \(a\)。

1. 若 \(a\) 为偶数，则将靠后的字符变成靠前的字符，由于要使转变次数最少，容易发现一个方法：令 \(B_i\) 和 \(B_{a-i+1}\) 配对，将 \(B_{a-i+1}\) 变成 \(B_i\)，最后把获得的字符串加入桶，按照字典序输出。这可以在最少次数的转变下将 \(S\) 变成一个字典序最小的回文串。

2. 若 \(a\) 为奇数，方法和上一个差不多，只对最中间的字符不操作并保存即可。

当然，可能会有人对 2 有疑惑，为什么不选择排头的字符或末尾的呢？

请看（红名请略过）：

字符串：
asdfghgfd
桶排后：
112221
asdfgh
剩余字符（按字典序排）：
ahs
若选择排头：
 转换：ahh
 回文串：dfghahgfd
若选择末尾：
 转换：aas
 回文串：adfgsgfda
若选择中间：
 转换：aha
 回文串：adfghgfda

很显然，选中间所得的回文串字典序更小。

输出是这样的：

1. 若回文串长度为偶数，由于回文串是先后对应的，只需要在所有桶中先从头到尾输出一半，再从尾到头输出剩下的即可。

2. 若为奇数，先在所有桶中从头到尾输出一半，再输出中间的字符，最后再从头到尾输出剩下的即可。

理论讲了一大堆，上代码：

#include<bits/stdc++.h>
using namespace std;
int c[205],num;
queue<char>q;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	char a;
	while(cin>>a){
		++c[a];//桶排
	}
	for(int i=1;i<=200;++i){
		if(c[i]%2==0)	continue;//若为偶数，略过
		++num;//统计字符串长度
		q.push(i);//若为奇数，保存
		//由于所有桶是按字典序排的，所以保存的字符也是按字典序排列的
		//队列的特性
	}
	
	if(num%2==0){//其实无需计算设下的字符数，易得若S长度为偶数，则剩下的字符数也是偶数
		for(int i=1;i<=num/2;i++){
			c[q.front()]+=2;//将靠后的转变为靠前的，并加入桶
			q.pop();
		}
		for(int i=1;i<=200;++i){
			for(int j=1;j<=c[i]/2;j++){
				cout<<(char)i;//输出
			}
		}
		for(int i=200;i>=1;--i){
			for(int j=1;j<=c[i]/2;j++){
				cout<<(char)i;
			}
		}
		return 0;
	}
	else{
		for(int i=1;i<=num/2;i++){
			c[q.front()]+=2;
			q.pop();
		}
		for(int i=1;i<=200;++i){
			for(int j=1;j<=c[i]/2;j++){
				cout<<(char)i;
			}
		}
		cout<<q.front();//输出中间的
		for(int i=200;i>=1;--i){
			for(int j=1;j<=c[i]/2;j++){
				cout<<(char)i;
			}
		}
		return 0;
	}
}//撒花

提交记录，华丽结束。

后附

日志

v1.0 on 2022.09.30: 发布

蒟蒻的话

这么良心的博主，怎么不点赞呢？