hdoj1850 Being a Good Boy in Spring Festival

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

中文：

题目就是中文，有M堆扑克牌，现在两个人轮流在桌子上拿牌，每个人每次选择一堆牌最少拿一个，问先手胜出的情况下，有多少种拿牌方法。

代码：

#include<iostream>
using namespace std;
int main()
{int n,a[101],temj,count;int i,j;while(~scanf("%d",&n),n){for(i=1;i<=n;i++)scanf("%d",&a[i]);count=0;for(i=1;i<=n;i++){temj=0;for(j=1;j<=n;j++){if(j==i)continue;temj^=a[j];}if(a[i]-temj>0)count++;}printf("%d\n",count);}return 0;
}

代码2：

#include<bits/stdc++.h>
using namespace std;int a[101];
int main()
{ios::sync_with_stdio(false);int m;while(cin>>m,m){int ans = 0, cnt = 0;for (int i=0;i<m;i++){cin>>a[i];ans = ans ^ a[i];}if (ans){for (int i=0;i<m;i++){if((ans^a[i]) <= a[i]){cnt++;}}}cout<<cnt<<endl;}return 0;
}

解答：

好久没看过博弈的问题了，从大学毕业到现在，差不多快10年，岁月匆匆。前不久在知乎上看到有人讨论SG函数的问题，基本上都忘干净了，再从头学一下。

博弈问题主要是三个基本模型
威佐夫博弈，巴什博弈和Nim博弈，有一篇论文叫一类取石子问题，作者是张一飞，是很好的参考材料。

这道题目是非常简单的Nim博弈问题，如果题目提问的是先手胜出或者是后手生成，那么就看这N个数的异或结果是否为0，如果为0则后手必胜，否则先手必胜。但是题目中询问的是如果先手胜出，有多少种拿石子的方法，这里需要了解一下Nim博弈使用异或计算的原理。

先说结论，设N堆石子的数量为$A_1,A_2,...,A_n$,如果$A_{1}xor{A}_{2}xor...A_n=0$
此时有先手必败状态，例如有两堆石子，两堆石子的异或结果为0的情况，必然是两堆石子的数量相同，此时如果先手在其中一堆石子拿取x个，那么后手可以通过在另外一堆石子拿取得x个石子，使游戏状态变为初始的状态，最后石子拿光，先手无石子可拿，导致失败。

如果是N堆石子，且初始的N堆石子在前后手都使用优策略下可以达到先手必败，如果想要达到先手必败的状态，那么就需要后手每次能够在先手拿完石子后将游戏的局面恢复至“平衡”，这里的平衡是指在前后手都使用最佳策略的情况下，后手可以正好拿完最后一堆石子的局面。
即先手在某一堆拿了x个石子，后手需要在其中一堆拿y颗石子，使得最后剩余的石子仍然能够达到先手必败，后手必胜。

这里，游戏的“平衡”态，使用通俗的语言来表示，即在偶数次最优策略操作后，可以达到所有石子全是0的一个状态，这种操作的状态与异或运算的性质是相符合的。即所有石子异或结果为0的情况，为一个“平衡”状态，此时先手必败。

如果是一个非“平衡”状态，那么异或结果不为0，假设此时异或结果为k。此时，在这N堆石子中有一堆石子的数量是大于等于K的（异或计算的性质，想想二进制就明白了），那么可以在这堆石子中拿走k个，使状态变为平衡状态。

本题目中，如果需要计数有多少种先手必胜的方案，那么只需要考虑起始条件下，有多少堆石子是大于等于k，那么就有多少种拿法，起始条件拿取k个后，变为“平衡”态，后面的石子拿法按照最佳策略，都是固定的。

这篇关于hdoj1850 Being a Good Boy in Spring Festival的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---