HDU1850 Being a Good Boy in Spring Festival(尼姆博弈)

本文主要是介绍HDU1850 Being a Good Boy in Spring Festival(尼姆博弈)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Problem Description

一年在外父母时刻牵挂春节回家你能做几天好孩子吗寒假里尝试做做下面的事情吧

陪妈妈逛一次菜场悄悄给爸爸买个小礼物主动地强烈地要求洗一次碗某一天早起给爸妈用心地做回早餐

如果愿意你还可以和爸妈说咱们玩个小游戏吧 ACM课上学的呢～

下面是一个二人小游戏：桌子上有M堆扑克牌；每堆牌的数量分别为Ni(i=1…M)；两人轮流进行；每走一步可以任意选择一堆并取走其中的任意张牌；桌子上的扑克全部取光，则游戏结束；最后一次取牌的人为胜者。
现在我们不想研究到底先手为胜还是为负，我只想问大家： ——“先手的人如果想赢，第一步有几种选择呢？”

Input

输入数据包含多个测试用例，每个测试用例占2行，首先一行包含一个整数M(1

Output

如果先手的人能赢，请输出他第一步可行的方案数，否则请输出0，每个实例的输出占一行。

Sample Input

3
5 7 9
0

Sample Output

思路

这是尼姆博弈的一个模型，尼姆博弈的一般模型为：

有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，有三堆石子，那么分三种情况：

拿数量为14的石子：首先60^14=21^39=50,那么14减去50是个负值，所以我们无法从数量为14的石子开始拿
拿数量为21的石子：首先60^21=14^39=41,那么21减去41是个负值，我们也无法从数量为41的石子开始拿
拿数量为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;
}