hdu 4642 Fliping game

本文从WordPress迁移而来, 查看全部WordPress迁移文章

博弈

【2013多校联合训练第四场】

题意:给出一个n*m矩阵,只有0,1分别表示向下和向上的箭头。每次从矩阵中找一个格子(x,y),从(x,y)-(n,m)这个子矩阵全部翻过来,即箭头方向取反,但是选的(x,y)格子要求是箭头必须向上的才能选

这题,想清楚了是个很简单的题目。只需要看(n,m)这个格子的箭头方向。因为是A先玩,如果(n,m)为向上,那么无论怎么翻(是选(n,m)直接翻,还是选其他向上的箭头翻),(n,m)在翻完后必定是向下的。到B玩的时候,(n,m)已经向下了,那么他只能选别的格子,他翻完后,(n,m)这个格子必定又向上。那么也就是说。到A玩的时候,(n,m)一定是向上的,A肯定可以翻。但是到B玩的时候,(n,m)是向下。游戏总有结束的一刻。但是A玩的始终至少有一个(n,m)能让他翻,他肯定不输,而输的人就是B
如果一开始(n,m)就是向下的,同理,输的人一个是A

所以读完数据,只需要判断最后一个格子的方向即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define N 110

int a[N][N],r,c;

int main(){
int cas;
scanf("%d",&cas);
while(cas--){
scanf("%d%d",&r,&c);
for(int i = 0; i < r; i++)
for(int j = 0; j < c; j++)
scanf("%d",&a[i][j]);
if(a[r-1][c-1] == 1)
puts("Alice");
else
puts("Bob");
}
return 0;
}