题目链接：http://codeforces.com/problemset/problem/883/H
暴力简化技巧
H. Palindromic Cut
Kolya has a string s of length n consisting of lowercase and uppercase Latin letters and digits.
He wants to rearrange the symbols in s and cut it into the minimum number of parts so that each part is a palindrome and all parts have the same lengths. A palindrome is a string which reads the same backward as forward, such as madam or racecar.
Your task is to help Kolya and determine the minimum number of palindromes of equal lengths to cut s into, if it is allowed to rearrange letters in s before cuttings.
Input
The first line contains an integer n (1 ≤ n ≤ 4·105) — the length of string s.
The second line contains a string s of length n consisting of lowercase and uppercase Latin letters and digits.
Output
Print to the first line an integer k — minimum number of palindromes into which you can cut a given string.
Print to the second line k strings — the palindromes themselves. Separate them by a space. You are allowed to print palindromes in arbitrary order. All of them should have the same length.
Examples
input
6
aabaac
output
2
aba aca
input
8
0rTrT022
output
1
02TrrT20
input
2
aA
output
2
a A
题目意思，把一个串可以任意交换字母位置，切割成最小数目且长度都相等的回文串
做法：暴力模拟
首先找落单的字母（即字母个数是奇数的），如果找不到，就直接打印，否则找到的落单字母如果不符合题目长度相等的要求，就是进行优化，因为最坏情况是将每一个字母分开，即成双的字母个数一共有ss对，落单的有sum个，每次优化将ss–,sum+=2,直至符合题目要求位置，或者ss
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int main()
{
char a[999999];
int n;
cin>>n;
cin>>a;
n = strlen(a);
int book[300]= {0};
for(int i=0; i<n; i++)
book[a[i]]++;
int sum =0,ss=0;
vector<int>o,oo;
for(int i=1; i<=200; i++)
if(book[i]%2!=0)
{
sum++;
o.push_back(i);
ss+=book[i]/2;
}
else
ss+=book[i]/2;
//cout<<o.size()<<"*"<<endl;
// cout<<sum<<endl;
if(sum==0)
{
cout<<"1"<<endl;
stack<int>ll;
for(int i=1; i<=200; i++)
for(int j=1; j<=book[i]/2; j++)
{
printf("%c",i);
ll.push(i);
}
while(!ll.empty())
{
int hh = ll.top();
printf("%c",hh);
ll.pop();
}
}
else if(sum==1)
{
cout<<"1"<<endl;
stack<int>ll;
for(int i=1; i<=200; i++)
for(int j=1; j<=book[i]/2; j++)
{
printf("%c",i);
ll.push(i);
}
printf("%c",o[0]);
while(!ll.empty())
{
int hh = ll.top();
printf("%c",hh);
ll.pop();
}
}
else if(n%sum!=0|| ( ((n-sum)/sum)%2!=0) )
{
int psum = sum;
// cout<<sum<<" "<<ss<<endl;
while(ss%sum!=0)
{
ss--;
sum+=2;
if(sum>ss)
break;
}
//cout<<sum<<" "<<ss<<endl;
if(sum>ss)
{
cout<<n<<endl;
int top = 1;
for(int i=0; i<n; i++)
{
if(top)top = 0;
else printf(" ");
printf("%c",a[i]);
}
}
else
{
for(int i=1; i<=200; i++)
{
while(book[i]>1)
{
book[i]-=2;
o.push_back(i);
o.push_back(i);
psum+=2;
if(psum>=sum)
break;
}
if(psum>=sum)
break;
}
int yy = n/sum;
cout<<sum<<endl;
int oo = (yy-1)/2;
//cout<<oo<<"*"<<endl;
// cout<<book['a']<<endl;
int top = 1;
for(int p=1; p<=sum; p++)
{
if(top)top = 0;
else printf(" ");
int ji = 0;
stack<int>ll;
for(int i=1; i<=200; i++)
{
if(book[i]!=0)
if(book[i]%2==0||book[i]>1)
{
int y = (book[i]/2);
for(int k=1; k<=y; k++)
{
ji++;
//cout<<ji<<endl;
ll.push(i);
book[i]-=2;
printf("%c",i);
if(ji>=oo)
break;
}
if(ji>=oo)
break;
}
}
printf("%c",o[p-1]);
while(!ll.empty())
{
int hh = ll.top();
printf("%c",hh);
ll.pop();
}
}
//cout<<sum<<" "<<" *"<<ss<<endl;
}
}
else
{
int yy = n/sum;
cout<<sum<<endl;
int oo = (yy-1)/2;
// cout<<book['a']<<endl;
int top = 1;
for(int p=1; p<=sum; p++)
{
if(top)top = 0;
else printf(" ");
int ji = 0;
stack<int>ll;
for(int i=1; i<=200; i++)
{
if(book[i]!=0)
if(book[i]%2==0||book[i]>1)
{
int y = (book[i]/2);
for(int k=1; k<=y; k++)
{
ji++;
//cout<<ji<<endl;
ll.push(i);
book[i]-=2;
printf("%c",i);
if(ji>=oo)
break;
}
if(ji>=oo)
break;
}
}
printf("%c",o[p-1]);
while(!ll.empty())
{
int hh = ll.top();
printf("%c",hh);
ll.pop();
}
}
}
return 0;
}下面是简化后的代码
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
const int maxn = 4e5;
char A[maxn+10];
char C[maxn*2+10];
int main()
{
char a[999999];
int book[300]={0};
int n;
cin>>n>>a;
for(int i=0;i<n;i++)
book[a[i]]++;
int L = 1,R = n;
for(int i=1;i<=200;i++)
if(book[i]&1)
A[L++] = (char)i,book[i]--;
for(int i=1;i<=200;i++)
if(book[i])
{
while(book[i]--)
A[R--] = (char)i;
}
L--;
//通过下标变换，把字母按照落单+成双的顺序排列，便于输出
int ans,len;
//ans 为枚举的最终答案
for(ans=1;ans<=n;ans++)
{
if(n%ans)continue;
//假如分成ans段有余数直接跳过
len = n/ans;
//从小到到大枚举，然后判断答案是否正确
if((n-L)/2>=ans*(len/2))break;
}
cout<<ans<<endl;
L =1,R = n;
for(int i=1;i<=ans;i++)
{
if(i!=1)printf(" ");
int ll = maxn+10,rr = maxn+10;
if(len&1)C[rr++] = A[L++];
//如果分成的每个小回文串是奇数，那么在中间打印一个
//落单的字母
for(int j=1;j<=len/2;j++)
{
C[--ll] = A[R--];
C[rr++] = A[R--];
}
for(int j=ll;j<rr;j++)printf("%c",C[j]);
}
return 0;
}
京公网安备 11010502036488号