C

原题地址:http://code-festival-2017-quala.contest.atcoder.jp/tasks/code_festival_2017_quala_c

Time limit : 2sec / Memory limit : 256MB

Score : 400 points

Problem Statement

We have an H-by-W matrix. Let aij be the element at the i-th row from the top and j-th column from the left. In this matrix, each aijis a lowercase English letter.

Snuke is creating another H-by-W matrix, A', by freely rearranging the elements in A. Here, he wants to satisfy the following condition:

Every row and column in A' can be read as a palindrome.

Determine whether he can create a matrix satisfying the condition.

Note

A palindrome is a string that reads the same forward and backward. For example, a, aa, abba and abcba are all palindromes, while ab, abab and abcda are not.

Constraints

1≤H,W≤100
aij is a lowercase English letter.

Input

Input is given from Standard Input in the following format:

H W
a11a12…a1W
:
aH1aH2…aHW

Output

If Snuke can create a matrix satisfying the condition, print Yes; otherwise, print No.

Sample Input 1

Copy

3 4
aabb
aabb
aacc

Sample Output 1

Copy

Yes

For example, the following matrix satisfies the condition.

abba
acca
abba

Sample Input 2

Copy

2 2
aa
bb

Sample Output 2

Copy

No

It is not possible to create a matrix satisfying the condition, no matter how we rearrange the elements in A.

Sample Input 3

Copy

5 1
t
w
e
e
t

Sample Output 3

Copy

Yes

For example, the following matrix satisfies the condition.

t
e
w
e
t

Sample Input 4

Copy

2 5
abxba
abyba

Sample Output 4

Copy

No

Sample Input 5

Copy

1 1
z

Sample Output 5

Copy

Yes
题目意思:有一个由字母组成的矩阵,对字母重新进行排列使行列都为回文串;判断是否可行;
解题思路:先记录每个字母的个数;因为要使行列都为回文串,则字母的一定使4*n+2*m+(1?)的组合
代码:

#include<iostream>
#include<string>
#include<algorithm>
#include <string.h>
#include <stdio.h>
#include <math.h>
#include <set>
#include <queue>
#include <stack>
#include <map>

using namespace std;
typedef long long LL;
const int INF = int(1e9);

int a[26] = {0};
int N,M;

int main()
{
    cin>>N>>M;
    for(int i = 1;i<=N;i++)
    for(int j = 1;j<=M;j++){
        char temp;
        cin>>temp;
        a[temp-'a']++;
    }
    int t4 = (N/2)*(M/2);
    int flag = 0;
    for(int i = 0;i<26;i++){
        if(a[i]==0)continue;
        if(a[i]>=4){
            if(a[i]/4<t4){
                t4 -= a[i]/4;
                a[i] = a[i]%4;
            }
            else{
                t4 = 0;
                a[i] = a[i] - t4*4;
            }
        }
        if(a[i]>1)
            a[i]%=2;
        if(a[i]==1&&flag==0)
            flag = 1;
        else if(a[i]==1&&flag==1)
            flag = 2;
        
    }
    if(t4<=0&&flag<=1)
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;
    return 0;
}