CF1365A Matrix Game题解

AzureMist · 2022-08-23 18:29:28 · 题解

引用楼下的一句话：

Vivek 和 Ashish 不能在已使用的至少一个单元格的行和列中声明单元格。因此，我们需要查看最初没有使用的任何单元格的行和列的最小数量的奇偶性。

为什么呢？因为一个 1 可以影响一行和一列，所以如果在某一时刻所有的行或列都被占领了，那么下一个人肯定得输。每次把一个位置设置为 1 都需要当前的行和列没有其他的 1，对方把所有的行或列都占领了，你不就没地方放置 1 了吗？因为空的行和列的数量是一起减少的，所以最开始的时候哪个更少，游戏的结果就取决于哪个。

其实，不用 STL 容器也能做。

我们先定义两个数组 acnt 和 bcnt，用来记录每行和每列的状态。然后再看 acnt 和 bcnt 里面有哪几个是 0，也就是这行或者这列最初没有使用任何单元格。游戏的结果就取决于最初没有使用任何单元格的行或列的奇偶性。最后不要忘了清空 acnt 和 bcnt 这两个数组，十年多测一场空，忘记 memset 见祖宗！

AC Code:

#include<bits/stdc++.h>
using namespace std;
int acnt[55],bcnt[55];
int min(int a,int b){
    return a<b?a:b;
}
int main()
{
    int t;
    cin>>t;
    for(int i=1;i<=t;i++)
    {
        int n,m;
        cin>>n>>m;
        for(int j=1;j<=n;j++)
        {
            for(int k=1;k<=m;k++)
            {
                char c;
                cin>>c;
                if(c=='1')
                {
                    acnt[j]++;
                    bcnt[k]++;//当前的行和列有1
                }
            }
        }
        int r=0,c=0;//因为char c是在循环当中定义的，所以不会撞车
        for(int j=1;j<=n;j++)
            if(acnt[j]==0)
                r++;
        for(int j=1;j<=m;j++)
            if(bcnt[j]==0)
                c++;//找符合要求的行和列
        if(min(r,c)%2==0) cout<<"Vivek"<<endl;
        else cout<<"Ashish"<<endl;
        memset(acnt,0,sizeof(acnt));
        memset(bcnt,0,sizeof(bcnt));//多测很糟糕
    }
    return 0;
}