题意
给出一个小写字母组成的字符矩阵,问能否通过重排其中的字符使得每行每列都是回文串.
分析
简化版:给出一个字符串,问能否通过重排其中的字符使得它是回文串.那么如果字符串长度为偶数,就需要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相同.#include#include #include 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\n",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\n",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\n",flag?"Yes":"No"); } return 0;}