CODE FESTIVAL 2017 qual A--C - Palindromic Matrix(模拟所有情况，注意细节)

个人心得：其实本来这题是有规律的不过当时已经将整个模拟过程都构思出来了，就打算试试，将每个字符和总和用优先队列

装起来，然后枚举每个点，同时进行位置标志，此时需要多少个点的时候拿出最大的和出来，若不满足就输出No，结果一直卡在三组

数据。比赛完后一想，优先队列虽然用处大，不过当行列存在奇数的时候此时只要2个就可以，而如果你从最大的4个中拿出来，

那么下一层循环中必然有一个位置无法填充，如此就导致了算法的失败。所以后面建立个奇偶判定就好了。

感悟：

多注意思考和细节，从不同的层次看待问题，既可以全面又可以优化所有细节！

题目：

Problem Statement

We have an H-by-W matrix. Let a_ij be the element at the i-th row from the top and j-th column from the left. In this matrix, each a_ij is 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 andabcda are not.

Constraints

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

Input

Input is given from Standard Input in the following format:

H W

a₁₁a₁₂…a_1W

:

a_H1a_H2…a_HW

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

 #include<iostream>

 #include<cstring>

 #include<string>

 #include<cstdio>

 #include<vector>

 #include<cmath>

 #include<stack>

 #include<set>

 #include<queue>

 #include<algorithm>

 using namespace std;

 #define in 1000000007

 int h,w;

 char ch[][];

 int ok=;

 struct mapa

 {

     char x;

     int sum;

     mapa(char m,int n)

     {

         x=m;

         sum=n;

     }

     bool operator <(const mapa &a)const

     {

         return sum<a.sum;

     }

 };

 int sum[];

 priority_queue<mapa >pq;

 int book[][];

 void flag(int i,int j){

       book[i][j]=;

             int t=;

             if(!book[i][w--j])

             {

                 t++;

                 book[i][w--j]=;

             }

             if(!book[h--i][j])

             {

                 t++;

                 book[h--i][j]=;

             }

             if(!book[h--i][w--j])

             {

                 t++;

                 book[h--i][w--j]=;

             }

            mapa a=pq.top();pq.pop();

            if(a.sum<t)

            {

                ok=;

                return false;

            }

            a.sum=a.sum-t;

            if(a.sum)

               pq.push(a);

 }

 bool dfs()

 {

     memset(book,,sizeof(book));

     int p=,q=;

     int i,j;

     if(h%==) p=;

     if(w%==) q=;

     for(i=;i<h;i++){

         if(p&&i==h/) break;

        for(j=;j<w;j++)

        {

            if(q&&j==w/) break;

         if(book[i][j]) continue;

         else

         {

            flag(i,j);

         }

        }

        }

        if(p)

        {

            for(int k=;k<w;k++)

            {

                if(q&&k==w/) break;

                if(book[i][k]) continue;

                book[i][k]=;

             int t=;

             if(!book[i][w--k])

             {

                 t++;

                 book[i][w--k]=;

             }

            mapa a=pq.top();pq.pop();

            if(a.sum<t)

            {

                ok=;

                return false;

            }

            a.sum=a.sum-t;

            if(a.sum)

               pq.push(a);

         }

        }

        if(q)

        {

            for(int k=;k<h;k++)

            {

                if(book[k][j]) continue;

                book[k][j]=;

             int t=;

             if(!book[h--k][j])

             {

                 t++;

                 book[h--k][j]=;

             }

            mapa a=pq.top();pq.pop();

            if(a.sum<t)

            {

                ok=;

                return false;

            }

            a.sum=a.sum-t;

            if(a.sum)

               pq.push(a);

         }

        }

        return true;

 }

 int main()

 {

     cin>>h>>w;

     for(int i=;i<h;i++)

          for(int j=;j<w;j++)

              cin>>ch[i][j];

              memset(sum,,sizeof(sum));

     for(int i=;i<h;i++)

          for(int j=;j<w;j++)

             sum[ch[i][j]-'a']++;

         for(int i=;i<;i++)

             if(sum[i])

             {

                 char t=i+'a';

                 pq.push(mapa(t,sum[i]));

             }

             if(h==||w==)

         {

             int flag=;

             for(int i=;i<;i++)

                 if(sum[i]%!=) flag++;

             if(flag>) cout<<"No"<<endl;

             else

                 cout<<"Yes"<<endl;

         }

         else{

             if(dfs())

                cout<<"Yes"<<endl;

                else

                  cout<<"No"<<endl;

         }

     return ;

 }

巴特西

CODE FESTIVAL 2017 qual A--C - Palindromic Matrix(模拟所有情况，注意细节)

Problem Statement

Note

Constraints

Input

Output

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

Sample Input 4

Sample Output 4

Sample Input 5

Sample Output 5

最新文章

热门文章