POJ 2975 Nim（尼姆博弈的变形）

本文主要是介绍POJ 2975 Nim（尼姆博弈的变形），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目大意

有 n(1≤n≤1000) 堆石子，每堆石子数量为 1 到 1,000,000,000 之间的一个整数。两人玩游戏。每回合，游戏者必须从某堆中取走至少一个石子，取走最后一个石子的人获胜。问先手第一步有多少种走法使得他/她获胜

解题思路

Nim 游戏的简单变形

说明：下面的 '^' 符号表示 “异或” 的意思

先求出所有的石子数量的 Nim 和，设为 sum。

对于某一堆石子，设石子数量为 Ai，sum^Ai 就得到了除去该堆石子，其余石子数量的异或和。假设先手第一步在这一堆中取石子，如果取走石子后，这一堆剩余石子 Bi 个，要保证先手必胜，必然下一个局面是后手必胜，于是有：sum^Ai^Bi=0，也就是说：

　　　　sum^Ai=Bi

看到上面的式子，不难得出结论：在 Ai 中取走 Ai-(sum^Ai) 个石子是第一步在 Ai 中取石子的唯一获胜方式，当然前提是：

　　　　Ai≥sum^Ai

于是利用上面的结论对每一堆石子判断一下即可

注意的是：^的优先级比<的低

代码：

#include<cstdio>
#include<cstring>int main(){int n,num[1005];while(scanf("%d",&n),n){int sum=0;for(int i=0; i<n; i++){scanf("%d",&num[i]);sum=sum^num[i];}if(sum==0){printf("0\n");continue;}int ans=0;for(int i=0; i<n; i++){if((sum^num[i])<=num[i]) ans++;}printf("%d\n",ans);}return 0;
}

这篇关于POJ 2975 Nim（尼姆博弈的变形）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---