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;
}
Zhao Li /
Published under (CC) BY-NC-SA in categories 算法  tagged with 博弈  尼姆博弈