尼姆游戏的规则：

有n堆石子，数量分别是{a₁,a₂,a₃,…,a_n},两个玩家轮流拿石子，每次从任意一堆中拿走任意数量的石子，拿到最后一个石子的玩家获胜。

尼姆游戏有个极为简单的判断胜负的方法，即做异或运算

（在这之前要了解一下巴什游戏中的P-position和N-position）

定理：

若a₁⊕a₂⊕a₃⊕…⊕a_n！=0则先手必胜，此时是N-position
若a₁⊕a₂⊕a₃⊕…⊕a_n==0则先手必败也就是后手胜，此时是P-position
简单的说有俩堆石头，每堆里面有3个石头 {3,3}，无论先手拿几个，后手跟着拿几个，就能保证后手赢。反之，若有俩堆石头，每堆里面分别有3个，4个石头 {3,4}，先手只要从第二堆中拿走多余的1个石头，与之前{3,3}的情况就相同了，但是此时变成了后手去拿，所以先手胜。

例如

题目：

Nim is a 2-player game featuring several piles of stones. Players alternate turns, and on his/her turn, a player’s move consists of removing one or more stones from any single pile. Play ends when all the stones have been removed, at which point the last player to have moved is declared the winner. Given a position in Nim, your task is to determine how many winning moves there are in that position.

A position in Nim is called “losing” if the first player to move from that position would lose if both sides played perfectly. A “winning move,” then, is a move that leaves the game in a losing position. There is a famous theorem that classifies all losing positions. Suppose a Nim position contains n piles having k1, k2, …, kn stones respectively; in such a position, there are k1 + k2 + … + kn possible moves. We write each ki in binary (base 2). Then, the Nim position is losing if and only if, among all the ki’s, there are an even number of 1’s in each digit position. In other words, the Nim position is losing if and only if the xor of the ki’s is 0.

Consider the position with three piles given by k1 = 7, k2 = 11, and k3 = 13. In binary, these values are as follows:

0111
1011
1101

There are an odd number of 1’s among the rightmost digits, so this position is not losing. However, suppose k3 were changed to be 12. Then, there would be exactly two 1’s in each digit position, and thus, the Nim position would become losing. Since a winning move is any move that leaves the game in a losing position, it follows that removing one stone from the third pile is a winning move when k1 = 7, k2 = 11, and k3 = 13. In fact, there are exactly three winning moves from this position: namely removing one stone from any of the three piles.

输入：

The input test file will contain multiple test cases, each of which begins with a line indicating the number of piles, 1 ≤ n ≤ 1000. On the next line, there are n positive integers, 1 ≤ ki ≤ 1, 000, 000, 000, indicating the number of stones in each pile. The end-of-file is marked by a test case with n = 0 and should not be processed.

输出：

For each test case, write a single line with an integer indicating the number of winning moves from the given Nim position.

样例：

3
7 11 13
2
1000000000 1000000000
0

结果：

3
0

这题没有直接让求出是先手胜还是后手胜，而是问的是输出先手胜利第一步可行的方案数。通过异或可以知道总的是谁胜，对于第一步来说，选择的那一堆(第i堆)数量为k，则剩下的n-1堆做异或运算，结果为H，如果H比k小，就把第i堆石头减少到H，这样H⊕H=0，后手必败。
同时n-1堆做异或运算可以由n堆的异或运算结果⊕选中的第i堆得到。

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int a[1005];
int main()
{
    int n;
    while(scanf("%d",&n),n){
        int sum=0,ans=0;
        for(int i=0;i<n;i++){
            scanf("%d",&a[i]);
            sum=sum^a[i];
        }
        if(sum==0) cout<<"0"<<endl;
        else{
            for(int i=0;i<n;i++){
                if((sum^a[i])<a[i]){//异或优先级比<低
                    ans++;
                }
            }
            cout<<ans<<endl;
        }
    }
    return 0;
}

没有加括号wa了几次…

最后

以上就是风趣红牛为你收集整理的Nim(尼姆游戏)例如的全部内容，希望文章能够帮你解决Nim(尼姆游戏)例如所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。