题意
有一串字符串 \(S\),设改变 \(S\) 中的任意一个字符称为 1 次转变(交换任意 2 个字符不算转变次数),求在操作最少的情况下可得到的回文字符串
正文
♦ 算法:找规律
♦ 准备知识:桶排序
对于一个回文串,有两种情况:
-
回文串字符数为偶数,如
assddssa
,易得其中每种字符数量都是偶数。 -
回文串字符数为奇数,如
asdfdsa
,易得其中除了最中间的字符数量为奇数,其余都是偶数。
再想到排序是不算转变次数的,很容易想到桶排序。
将 \(S\) 中的每个字符对应的桶加 1,通过上述规律可以知道,每个为偶数的桶不需要转变,每个为奇数的桶执行以下操作:
去掉一个字符使桶为偶数,将去除的字符留下备用,而接下来就是对这些字符进行转变,见例子。
字符串:
aesdffdaa
桶排后:
31122
aesdf
操作后的桶:
20022
aesdf
剩余字符:
aes
设剩下的字符按字典序排序后组成的字符串为 \(B\),长度为 \(a\)。
-
若 \(a\) 为偶数,则将靠后的字符变成靠前的字符,由于要使转变次数最少,容易发现一个方法:令 \(B_i\) 和 \(B_{a-i+1}\) 配对,将 \(B_{a-i+1}\) 变成 \(B_i\),最后把获得的字符串加入桶,按照字典序输出。这可以在最少次数的转变下将 \(S\) 变成一个字典序最小的回文串。
-
若 \(a\) 为奇数,方法和上一个差不多,只对最中间的字符不操作并保存即可。
当然,可能会有人对 2 有疑惑,为什么不选择排头的字符或末尾的呢?
请看(红名请略过):
字符串:
asdfghgfd
桶排后:
112221
asdfgh
剩余字符(按字典序排):
ahs
若选择排头:
转换:ahh
回文串:dfghahgfd
若选择末尾:
转换:aas
回文串:adfgsgfda
若选择中间:
转换:aha
回文串:adfghgfda
很显然,选中间所得的回文串字典序更小。
输出是这样的:
-
若回文串长度为偶数,由于回文串是先后对应的,只需要在所有桶中先从头到尾输出一半,再从尾到头输出剩下的即可。
-
若为奇数,先在所有桶中从头到尾输出一半,再输出中间的字符,最后再从头到尾输出剩下的即可。
理论讲了一大堆,上代码:
点击查看代码
#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: 发布
蒟蒻的话
这么良心的博主,怎么不点赞呢?
标签:字符,输出,int,题解,偶数,字符串,CF600C,回文 From: https://www.cnblogs.com/wanguan/p/16745745.html