尼姆博弈

这是尼姆博弈的一个模型,尼姆博弈的一般模型为:

有3堆各若干个物品,两个人轮流从某一堆取任意多的物品,规定每次至少取一个,最后取光者获胜胜。

这是nim博弈最简单的情况,我们用(a,b,c)表示某种局势,首先(0,0,0)显然是奇异局势,无论谁面对奇异局势,都必然失败。第二种奇异局势是(0,n,n),只要与对手拿走一样多的物品,最后都将导致(0,0,0)。仔细分析一下,(1,2,3)也是奇异局势,无论对手如何拿,接下来都可以变为(0,n,n)的情形。

那么怎么才能判断一个局势是否为奇异局势呢?答案就是抑或运算。这也算是公平组合博弈的一个原理之一,由于是尼姆博弈的基础于是放到此部分。

最重要的部分是找到奇异局势,尼姆博弈的奇异局势是,所有石堆的异或值为0,证明过程:尼姆博弈(Nimm's Game)

我们举个栗子来说明一下:

假设我们现在有三堆石子,分别是 14 ,21, 39。

那么我们首先算出这些数量的异或值:

14 ^ 21 ^ 39 = 60

我们思考一下怎么可以到达奇异局势,也就是想办法把它们的异或值变成0,有三堆石子,那么分三种情况:

  1. 拿数量为14的石子: 首先60^14=21^39=50,那么14减去50是个负值,所以我们无法从数量为14的石子开始拿
  2. 拿数量为21的石子:首先60^21=14^39=41,那么21减去41是个负值,我们也无法从数量为41的石子开始拿
  3. 拿数量为39的石子:首先60^39=14^21=27,那么39-27=12,所以我们从数量为39的石子中拿走12个就可以达到奇异局势

那么这个题目就很简单了,先算出他们的异或值,然后遍历一下所有的石子,确定一下从哪些堆,拿石子可以到达奇异局势就可以

代码

#include <bits/stdc++.h>
using namespace std;
int a[110];
int main()
{
    int n;
    while(~scanf("%d",&n)&&n)
    {
        int ans=0,cnt=0;
        for(int i=0; i<n; i++)
        {
            scanf("%d",&a[i]);
            ans^=a[i];
        }
        if(ans==0)puts("0");
        else
        {
            for(int i=0; i<n; i++)
            {
                int k=ans^a[i];
                if(a[i]-k>0)
                    cnt++;
            }
            printf("%d\n",cnt);
        }
    }
    return 0;
}

results matching ""

    No results matching ""