题目链接:http://codeforces.com/problemset/problem/883/H
题目大意:给一段长度为n的字符串s,想让你把s切成几段长度相同的回文串,可以改变s中字符的排列,最少可以出现切成几段。
解题思路:看了大佬写的,自己思维还是有诸多不足,也学到了vector可以用pop_back()删除最后一个元素,还学到了处理字符数量的技巧。首先,每段回文串里肯定都有一个字符是单个的,假设每段回文串都没有字符是单个的,那说明可以合成一串,假设不成立。假设有的回文串中有字符是单个的,有的没有,那长度肯定是一奇一偶不符合题目每段长度都相同的要求,假设不成立。
用vector<char>shuang,vector<char>dan分别统计出现两次和出现一次的字符。
所以可以分为以下几步:
①计算每个字符出现次数,并判奇偶,如果是偶数个就拆分成多个数量为2的字符存入(比如‘c’出现4次,那就存入两次c)shuang。如果是奇数个,就先拿一个存入dan,再把剩下的拆分成多个数量为2的字符存入shuang。
②如果没有出现数量为奇数的字符,那就最少可以只有一个回文串,直接将s输出。
③出现数量为奇数的字符,如果shuang内的字符不能平分给dan内的字符,也就是不能形成长度相同的回文串,那就把双里的字符拆成两次放入dan中,使得shuang能被dan平分。然后直接输出所有回文串即可。
代码:
#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<vector>
using namespace std;
const int N=4e5+; int cnt[];
char ans[N],s[N];
vector<char>dan;
vector<char>shuang; int main(){
int n;
scanf("%d",&n);
scanf("%s",s);
for(int i=;i<n;i++){
cnt[s[i]]++;
}
for(int i=;i<=;i++){
if(cnt[i]){
if(cnt[i]%){
cnt[i]--;
dan.push_back(i);
}
while(cnt[i]){
cnt[i]-=;
shuang.push_back(i);
}
}
}
if(dan.size()==){
for(int i=;i<n/;i++){
ans[i]=ans[n-i-]=shuang.back();
shuang.pop_back();
}
ans[n]='\0';
printf("1\n%s\n",ans);
}
else{
//用偶数单词凑成每段长度相同
while(shuang.size()%dan.size()){
dan.push_back(shuang.back());
dan.push_back(shuang.back());
shuang.pop_back();
}
int len=n/dan.size();
printf("%d\n",dan.size());
for(int i=;i<dan.size();i++){
ans[len/]=dan[i];
for(int j=;j<len/;j++){
ans[j]=ans[len-j-]=shuang.back();
shuang.pop_back();
}
ans[len]='\0';
printf("%s ",ans);
}
}
return ;
}