nim博弈

51 阅读 0 评论 34 点赞

我是靠谱客的博主酷炫项链，最近开发中收集的这篇文章主要介绍nim博弈，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

nim博弈是最基础的博弈之一也是非常重要的博弈。
题目：有n堆石子每堆石头有ai个石头，两个玩家轮流进行操作，每次操作可以从一堆石头里取任意数量的石子（但是不能不取），当一个玩家不能在取时就输了。
我们可以得到一个结论当a1 ^ a2 …… ^ an=0时先手必输，否则先手必赢。
我们也可先设a1 ^ a2 ^ a3 ^ … ^an=x,设x的二进制表示最高位为第k位，那么a1到an中必有一个ai他的第k位为1，我们每次取ai-(ai ^ x)那么ai堆还剩下的元素个数就为ai ^ x个。因为a1 ^ a2 ^ a3 ^ … ^ ai ^…an=x那么先手取了一次后剩下的每堆石头异或值就为a1 ^ a2 ^ a3 ^ … ^ ai ^ x ^… ^ an,
就等于x ^ x=0。所以证明结论等价于我们证明当a1 ^ a2 ^ … ^ an=0时该轮操作的玩家必输就行了。这里我们用反证法假设在该论玩家取了第ai堆石头后每堆石头的异或值仍为0，设取了第ai堆石头后第ai堆石头剩下的石头量为ai’那么就可以得出a1 ^ a2 ^ … ^ ai’ ^ … ^ an=0。进而可以推出该堆石头与原来的那堆石头进行异或后值任为0即a1 ^ a1 ^ a2 ^ a2 ^ … ^ ai ^ ai’ ^ … ^ an ^ an=0，那么ai ^ ai’=0所以可以得出ai=ai’但是题目要求至少要取一枚石头那么就可以证出不存在取一次石头而不改变异或值的方式所以要两个人每次都都取最优解的话每次的异或值都会一次为0一次不为0的改变那么我们就证明出了当a1 ^ a2 …… ^ an=0时先手必输，否则先手必赢。
代码很简单如下

#include<iostream>//如果n个x的异或值为0的话后手必赢反之先手赢 
int main(){
    int x,n,ans=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&x);
        ans^=x;
    }
    if(ans){
        printf("Yesn");
    }else{
        printf("Non");
    }
    return 0;
}