本文主要是介绍博弈——混合（尼姆）HDU 4388 Stone Game II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Stone Game II
1.题目含义：
一共有n堆石子，每堆石子个数用x表示。现在你可以选择一堆移除某些石子，但要剩余k个石子，确保k在[1,n-1]这个区间内。
移除石子后，还要加入一些石子，加入石子的个数为：k^x，当然你也可以使用技能使得加入的石子个数变为(2k)^x。不过每个人每局游戏只能使用一次技能。问最后先手是否可以取得胜利，可以的话输出Yes，否则输出No。
2.思路：
2.1 先不考虑技能，其实每轮的操作就是将一个大小为x的堆分成大小为k和(x^k)的堆，这里很关键的一点是要能发现分堆之前x中二进制1的个数与分堆之后k与(x^k)的二进制1个数和的奇偶性是相同的。这个结论可以这样想，考虑x的某一位p，就会有四种情况：
2.1.1. 如果x的第p位为1且k的第p位也为1，那么(x^k)的第p位就是0. ——开始1的个数为2，拆分后1的个数还是2
2.1.2. 如果x的第p位为1且k的第p位也为0，那么(x^k)的第p位就是1.——开始1的个数为1，拆分后1的个数还是1
2.1.3. 如果x的第p位为0且k的第p位也为1，那么(x^k)的第p位就是1.——开始1的个数为1，拆分后1的个数还是1
2.1.4. 如果x的第p位为0且k的第p位也为0，那么(x^k)的第p位就是0.——开始1的个数为1，拆分后1的个数还是0
可以发现无论哪种情况，奇偶性都不会发生变化，这是本题的关键。
2.2考虑N堆的情况，总共可操作次数为奇数先手赢，否则先手输。
2.3考虑技能的情况，技能不会增加1的个数
2.4另外考虑游戏什么时候结束，很显然当一个堆x的二进制1的个数只有1个的时候，就不能再分了，那么如果所有的堆都这样，游戏就结束了。
2.5 当n+cnt(n堆石子二进制1的个数)为奇数时，先手取得胜利。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cstdio>
using namespace std;
int t;
int count(int num)
{int cnt=0;while(num){cnt=cnt+num&1;num>>=1;}return cnt;
}
int main()
{int j;int num;cin>>t;for(j=1;j<=t;j++){int n;int ans=0;cin>>n;for(int i=0;i<n;i++){cin>>num;ans=ans+count(num);}ans=ans+n;if(ans&1)cout<<"Case "<<j<<": "<<"Yes"<<endl;elsecout<<"Case "<<j<<": "<<"No"<<endl;}return 0;
}
这篇关于博弈——混合（尼姆）HDU 4388 Stone Game II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
