博弈论
特点
博弈论的题目有如下特点:
- 有两名选手
- 两名选手交替操作,每次一步,每步都在有限的合法集合中选取一种进行
- 在任何情况下,合法操作只取决于情况本身,与选手无关
- 游戏败北的条件为:当某位选手需要进行操作时,当前没有任何可以执行的合法操作
原题
http://acm.hdu.edu.cn/showproblem.php?pid=4642
题意
有一个 n*m
的矩阵,里面散布着 1
和 0
两种字符。现在有两名玩家,轮番选择一个点,每选择一个点,就将这个点和最右下角的点所组成的矩阵全部反转字符(即 1
变成 0
,0
变成 1
)。当矩阵全变成 0
后,下一名玩家判为失败。
思路
典型博弈论题
我们来假设一个矩阵
1 0 1 0
0 1 0 1
1 1 1 1
第一名玩家假设选择(0,0)这个点
那么矩阵将变为
0 1 0 1
1 0 1 0
0 0 0 0
我们注意一下最右下角这个点
当它为 1 时,反转后变为 0 ,为 0 时,反转后变为 1
而且它在每一次操作中必定反转
因此,如果最开始,这个点为 1 ,那么先选点的人必定将这个点变为 0
后操作的人必定将这个点变为 1
因此,先操作的人必定赢
反之亦然。
代码
#include<stdio.h>
int main (){
int t ,n ,m ,i ,j ,tmp;
scanf("%d" ,&t);
while(t--){
scanf("%d %d" ,&n ,&m);
for(i = 1 ;i <= n ;i ++)
for(j = 1 ;j <= n ;j ++)
scanf("%d" ,&tmp);
if(tmp) printf("Alice\n");
else printf("Bob\n");
}
return 0;
}
扩展
本文由 小但 创作
全文共:957个字
采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载,均为作者原创,转载前请务必署名
最后编辑时间为: Oct 7, 2020 at 12:40 pm
博主太厉害了!