题意
给出一个小写字母组成的字符矩阵,问能否通过重排其中的字符使得每行每列都是回文串.
分析
简化版:给出一个字符串,问能否通过重排其中的字符使得它是回文串.那么如果字符串长度为偶数,就需要a到z的个数都是2的倍数,如果长度是奇数,就需要恰好有一种字母的个数不是2的倍数.
那么拓展到二维的情况也差不多.
假设行数为n,列数为m.
1.n和m均为偶数:
最简单的情况,只需要所有字母的个数都是4的倍数
2.n为偶数,m为奇数:(n为奇数m为偶数的情况相同)
那么在刨掉一个长度为n的回文串之后所有字母的个数都是4的倍数.
于是所有字母的个数还都得是偶数,我们不妨先把所有字母的个数都除以2...
那么除以2之后要有(m-1)n/2个字母可以分成两两一组,还有n/2个字母可以分成每个字母单独一组...
于是数一数除以2之后有多少个字母是奇数个,如果这个数目大于n/2那么没戏,如果这个数目和n/2的奇偶性不同也没戏,否则一定行.
3.n为奇数,m为奇数
首先必然会有一种字母是奇数个,其他字母是偶数个,不满足这个条件就GG了.
如果满足这个条件,为了简化问题再把所有字母个数除以2...
那么还要有(m-1)(n-1)/2个字母可以两两一组,(n-1)/2+(m-1)/2个字母可以每个字母单独一组,然后的判断和2相同.
打比赛的时候中途走神这题50分钟才过
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m;
int cnt[30];
int main(){
scanf("%d%d",&n,&m);
int N=n*m;
char ch;
for(int i=1;i<=N;++i){
while(ch=getchar(),ch>'z'||ch<'a');
cnt[ch-'a']++;
}
if(n%2==0&&m%2==0){
bool flag=true;
for(int i=0;i<26;++i)if(cnt[i]%4!=0)flag=false;
printf("%s
",flag?"Yes":"No");
}else if(n%2==0||m%2==0){
if(m%2==0)swap(n,m);
//n even m odd
// 4*((m-1)*n/4),2*(n/2)
bool flag=true;
for(int i=0;i<26;++i){
if(cnt[i]&1)flag=false;
}
// 2*((m-1)*n/4),1*(n/2)
for(int i=0;i<26;++i)cnt[i]/=2;
int cnt2=0,cnt1=0;
for(int i=0;i<26;++i)cnt2+=cnt[i]/2,cnt1+=cnt[i]&1;
if(cnt1>n/2||(cnt1&1)!=((n/2)&1))flag=false;
printf("%s
",flag?"Yes":"No");
}else{
//n odd m odd
// 4*[(n-1)*(m-1)/4] 2*[(n-1)/2 +(m-1)/2] 1*1
int cnt1=0;
for(int i=0;i<26;++i){
if(cnt[i]&1)cnt1++;
}
bool flag=true;
if(cnt1!=1){
flag=false;
}else{
for(int i=0;i<26;++i){
cnt[i]/=2;
}//2*[(n-1)*(m-1)/4] 1*[(n-1)/2 +(m-1)/2]
cnt1=0;
for(int i=0;i<26;++i){
if(cnt[i]&1)cnt1++;
}
if(cnt1>(n-1)/2+(m-1)/2||((cnt1&1)!=(((n-1)/2 +(m-1)/2)&1)))flag=false;
}
printf("%s
",flag?"Yes":"No");
}
return 0;
}