博弈论(ACM)
in 竞赛相关C笔记 with 0 comment

博弈论(ACM)

in 竞赛相关C笔记 with 0 comment

博弈论

特点

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

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

原题

http://acm.hdu.edu.cn/showproblem.php?pid=4642

题意

有一个 n*m 的矩阵,里面散布着 10 两种字符。现在有两名玩家,轮番选择一个点,每选择一个点,就将这个点和最右下角的点所组成的矩阵全部反转字符(即 1 变成 00 变成 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;
}

扩展

留言: