POJ 2975 Nim【nim博弈的理解】

题意：

$n$堆石子，两人进行nim博弈，问可以从哪堆石子开始先取能保证先手必胜。

思路：

nim博弈中先手必胜的条件是所有石子个数异或值不为0，原因是先手总可以通过取一些石子使得现有石子达到平衡态，平衡态之后通过模仿前者的操作就能必胜。

那么第一步就能使当前状态达到平衡态的条件又是什么呢？很容易想到就是剩余石子堆个数的异或值小于这一堆的石子数(即通过取走一定数量使得总堆数达到平衡态)。

MyCode：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 1111;

int n, res, cnt, a[N];
int main()
{
    while(scanf("%d", &n) && n)
    {
        res = cnt = 0;
        for(int i = 0; i < n; ++i)
        {
            scanf("%d", &a[i]);
            res ^= a[i];
        }
        for(int i = 0; i < n; ++i)
        {
            if(a[i] > (a[i] ^ res))
                ++cnt;
        }
        printf("%d\n", cnt);
    }
    return 0;
}