• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

CF1365A 题解

开发技术 开发技术 1周前 (05-04) 12次浏览

Luogu-CF1365A

题目分析

如果当前玩家想要在网格图上找一个位置设置为 (1),条件式这一个位置所在的行以及列上都没有其它的 (1)

观察到数据范围只有 $1 leq n,m leq 50 $,我们可以考虑直接在网格图上操作。

在读入的时候,只要读入到当前位置的数为 (1),我们可以在网格图上将该行和该列上的所有数都标记为 (1)

之后我们可以模拟玩家操作的过程,记录下当前回合谁在操作。每次遍历一遍网格图,如果发现网格图中有 (0),就把这个位置变为 (1),并且将该行和该列上的每一个数都变为 (1)

以此不断循环,直到遍历网格图时没有 (0),就说明一个玩家要输了,此时输出当前不是谁在操作即可。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;

ll n, T, m;
bool a[100][100], ok = 0;

void change(ll x, ll y){ 
    for (int i = 1; i <= n; ++i) a[i][y] = 1;
    for (int j = 1; j <= m; ++j) a[x][j] = 1;
} //将该位置的每一行和每一列都该为1

void CLEAR(){ 
    ok = 0;
    memset(a, 0, sizeof a);
} //初始化

int main()
{
    T = read();
    while (T--)
    {
        CLEAR(); //初始化
        n = read(), m = read();
        for (int i = 1; i <= n; ++i){
            for (int j = 1; j <= m; ++j){
                bool x;
                cin >> x;
                if (x == 1)
                    change(i, j); //修改
            }
        }

        while (1)
        {
            bool f = 0; //为遍历表之后没有找到0而弹出做准备
            for (int i = 1; i <= n; ++i){
                for (int j = 1; j <= m; ++j){
                    if (a[i][j] == 0){
                        change(i, j);
                        if (ok == 0) ok = 1; //更换谁在操作
                        else ok = 0; //更换谁在操作
                        f = 1; //代表找到了0
                        break;
                    }
                }
                if (f == 1)
                    break;
            }
            if (f == 0){ //表里全是1,输出答案
                if (ok == 0) puts("Vivek");
                else puts("Ashish");
                break;
            }
        }
    }
    return 0;
}

程序员灯塔
转载请注明原文链接:CF1365A 题解
喜欢 (0)