[原创]hdu 1847 Nim博弈

Tabris

CSDNPOJ博弈ZOJ

发布于：2016年3月6日

次浏览

[原创]hdu 1847 Nim 博弈

2016-03-06 15:28:21 Tabris_ 阅读数：441

博客爬取于 2020-06-14 22:44:58
以下为正文

版权声明：本文为 Tabris 原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/50813592

博弈问题 #

巴士博弈

HDU1846<-点击此处进入链接

威尔夫博弈

HDU1527<-点击此处进入链接

斐波那契博弈

HDU2516<-点击此处进入链接

尼姆博弈

HDUXXX<-点击此处进入链接

题目链接：poj zoj
题意：有 N 堆石子，两人轮流从任一堆中取任意个石子（至少一个），最后一个取石子的人为胜利者。若先取者胜利，则输出第一次拿走石头的方法一共可以有多少种。
分析：
求出一个必胜局面有多少种方式可以导出必败局面。
也就是求由 S 态到 T 态有多少种路径。
一个 S 态要转化成为 T 态，
令 C = k1^k2^k3...^kn.
C 的二进制表示最高位为 1.
假设 ki 的二进制表示最高位与 C 的二进制表示最高位相同，那么可以通过将 ki 的某些二进制位上的 0 置为 1,1 置为 0 来使得 C' = 0，也就是使 S 态转化为 T 态。
所以问题就是寻找有多少个 ki，其最高位和 C 的最高位相同。

看本题前后 可以做一下斐波那契博弈 在思维上有些相关性
**斐波那契博弈** <-点击这里进入链接

先声明一下 每一个数 都可以用 2 的 N 次幂的数的集合里元素加起来表示 （联想 2 进制数把每位的数换成他所等价的 10 进制的值）
标准的 Nim 博弈是要求可以取任意个石子 因为这个任意的数能够用 2 的 N 次幂的数的集合里元素加起来表示 所以只取 2^n(n=0,1,2.3……)个数的石子就可以了
而且相对后面判断奇异局势，比较好理解

还是和所有博弈一样 找到它的必败态也就是奇异局势
假设 n 堆为 3 堆
**1.(0,0,0)是理所当然的奇异局势 **
2.(0,n,n)也是奇异局势，只要先手拿多少，后手在另一堆里拿相同个数的石子 就总保持(0,n,n)等先手最后一次拿光的时候，后手就可以把最后一堆剩下的全部拿光了
**3.(a,b,c)满足奇异局势的时候，和(2)的情况一样先手拿多少后手就拿多少，这个时候假定每一次先手拿的石子个数是 a[i]，那么只要保证在(a,b,c)中保证 a[i]均成对即可 这样对方拿出来多少你就拿多少 就能保证赢 **
举个例子(4,9,13)

如果先手拿 8,4,1 后手也这样拿 那么先手一定输
当然 先手也可能拿 2 不管拿那个数里的 2 都可分解出来 成对的
如果说拿的是 4 里的 2 可以拿 13 中的 2 可以拿 13 中的 2 保证接下来的是成对的
可以划成这样
如果说拿的是 9 里的 2 也可以拿 13 中的 2 保证接下来的是成对的
可以划成这样
如果说拿的是 13 里的 2 也可以拿 9 或 13 中的 2 保证接下来的是成对的
划分之后的和上两个图片是一样了
知道了上述这些 那么无论是 3 堆还是多少堆 都是这样凑成对就好了

**刚刚解释的就是 Nim 博弈的过程了 那么怎么用代码实现的呢 **
其实自习观察上几张图片 会发现点什么 先想一想再看下文
如果把出了 0 的数均换成 1 并按照顺序呢列出 就会发现这就是一个二进制数
想到了而进制数 那就应该想到位运算
Ps: 如果想多了解一下位运算 <-点击此处进入链接
那么只要用“^”异或运算就可以判断局势是不是奇异局势了

对于三堆的满足 a^b^c=0 就是奇异局势
N 堆的话就是

付一下本题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# include <iostream>  
# include <cstdio>  
using namespace std;  
int main()  
{  
    int n;  
    while (scanf("%d", &n), n)  
    {  
        int stone[1001], ans = 0, i;  
        for (i=0; i<n; i++)  
        {  
            scanf("%d", &stone[i]);  
            ans ^= stone[i];  
        }  
        int total = 0;  
        for (i=0; i<n; i++)  
        {  
            if (stone[i] > (stone[i]^ans))  
                total ++;  
        }  
        printf("%d\n", total);  
    }  
    return 0;  
}  

本页文档最后更新于：2021年5月16日

CSDN

poj

博弈

zoj

Nim博弈

Nim