博弈问题#

巴士博弈

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堆的话就是

付一下本题代码

# 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;
}