回文构造机
题目大意:XTX非常喜欢回文串,他认为回文会给自己带来好运,有一天他看到一个字符串突发奇想,如果将这个字符串所有字符打乱,然后每次操作只能挑选若干个能构成回文串的字符组合成一个字符串,XTX最少需要操作几次才能取完所有字符。
思路概述:首先我们可以知道一个事情,也就是回文串中的字母数字最多已有一个奇数。这一点是很重要的。那样我们就可以分离,也就是说先统计字母的个数,如果是偶数,那么分一半输出,最中间可以带一个奇数个的字母,然后偶数的呢就搞定了,最后奇数一轮一轮的输出。然后答案其实是取决于奇数个字母的数量。但是,**如果是 0 ,却要输出 1 **,因为偶数自己要走一轮,不然直接错了,其他的话难度没有那么高,分开来写即可。
#include<bits/stdc++.h>
using namespace std;
int cnt[100005];
char s[100005];
int ans;
int main()
{
cin>>s;
int len=strlen(s);
for(int i=0;i<len;i++)
{
cnt[s[i]-'a']++;//统计个数
}
for(int i=0;i<128;i++)
{
if(cnt[i]%2)//记录奇数个数
{
ans++;
}
}
if(ans==0)//千万要注意,偶数必须走一轮
{
ans=1;
}
cout<<ans<<endl;
for(int i=0;i<=127;i++)
{
if(cnt[i]%2==0&&cnt[i]!=0)
{
for(int j=1;j<=cnt[i]/2;j++)
{
cout<<char(i+'a');//前一半
}
cnt[i]/2;
}
}
for(int i=0;i<=127;i++)
{
if(cnt[i]%2==1)
{
for(int j=1;j<=cnt[i];j++)
{
cout<<char(i+'a');//中间加一个奇数
}
cnt[i]=0;//注意直接清零,不然后果很惨。
break;
}
}
for(int i=127;i>=0;i--)
{
if(cnt[i]%2==0&&cnt[i]!=0)
{
for(int j=1;j<=cnt[i]/2;j++)
{
cout<<char(i+'a');//后一半偶数
}
cnt[i]=0;//不要除以2啦。
}
}
cout<<endl;
for(int i=0;i<=127;i++)
{
if(cnt[i])
{
for(int j=1;j<=cnt[i];j++)
{
cout<<char(i+'a');//奇数一轮一轮单走
}
cout<<endl;
}
cnt[i]=0;
}
return 0;
}