原创 校园生活 大学生活 竞赛相关 码农笔记 C笔记 ACM

博弈论

特点

博弈论的题目有如下特点：

1. 有两名选手
2. 两名选手交替操作，每次一步，每步都在有限的合法集合中选取一种进行
3. 在任何情况下，合法操作只取决于情况本身，与选手无关
4. 游戏败北的条件为：当某位选手需要进行操作时，当前没有任何可以执行的合法操作

原题

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