POJ 2975 -Nim

[mathjax]
题目链接:POJ 2975

题意: 问从给定局面,先手有多少种方法使其转换为必败态.

思路:典型的NIM博弈,但不是求谁必胜必败. 检查每个位置是否可以拿走若干个石子使所有堆的异或值为0,即当某一堆的石子数大于其他堆石子数的异或值时,可以通过拿走该堆石子若干,使其与其他堆石子数异或值相等,这样所有堆石子数异或值就为0了,也就是必败态.

code:

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <string>
#include <vector>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

int A[1005];

int main() {
  int n;
  while (cin >> n && n) {
    for (int i = 1; i <= n; ++i) {
      cin >> A[i];
    }
    int x = A[1];
    for (int i = 2; i <= n; ++i) {
      x = x ^ A[i];
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
      if (A[i] > (A[i] ^ x)) ans++;
    }
    cout << ans << endl;
  }

  return 0;
}