本文主要是介绍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
1
思路
这是尼姆博弈的一个模型，尼姆博弈的一般模型为：
有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;
}
这篇关于HDU1850 Being a Good Boy in Spring Festival(尼姆博弈)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
