POJ2975 Nim（尼姆博弈）

题目链接

题意：n 个数分别代表每堆的石子数，问获胜的取法有多少种。

和HDU1850一样的代码。。

简单的再总结下，就是用异或的和 sum 先异或 ai 这堆，由于 a^b^b=a，那么就相当于没考虑这一堆，所以只要把 ai 这堆剩下 sum^ai 个石子，那么所有堆就变成了(sum^ai)^(sum^ai)=0，对手就面临着必败态。所以让 sum^ai 小于 ai，ans++就可以。也就是说每堆最多只有一种取法。

#include<cstring>
#include<cstdio>
#include<cstring>
#include<cmath>
#include <vector>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
int a[1005];
int main(){
    //freopen("a.txt", "r", stdin);
    int n;
    while(cin >> n && n){
        int sum = 0;
        for(int i = 0; i < n; i++){
            scanf("%d", &a[i]);
            sum ^= a[i];
        }
        int ans = 0;
        for(int i = 0; i < n; i++){
            if((sum^a[i]) < a[i])
                ans++;
        }
        cout << ans << endl;
    }
    return 0;
}