HDU1850 Being a Good Boy in Spring Festival(尼姆博弈)

March 08, 2016

题目链接

中文题。

当尼姆游戏的某个位置:(x1,x2,x3),当且仅当其 x1⊕x2⊕x3 = 0(也就是各部分的异或为 0))当前位置为必败点,这对于多个堆的情况同样适用。

我们先求出所有堆异或后的值,再用这个值去对每一个堆进行异或,令 res = x1⊕sum(sum 为所有堆的或异值)(这时相当于没有考虑 x1 这堆)

如果 res < x1 的话,当前玩家就从 x1 中取走(x1-res)个,使 x1 剩下 res 这样必然导致所有的堆的异或值为 0,也就是必败点,这就是一种方案 遍历每一个堆,进行上面的断判就可以得到总的方案数。 注意一个必败点不可能导致另一个必败点,因为如果这样的话当前这个必败点就不是必败点了,所以这里对于每个堆的操作至多只有一种方法可以导败必败点,如果 res > x1 的话就无论从这个堆取走多少都不可能导致必败点。

#include<cstring>
#include<cstdio>
#include<cstring>
#include<cmath>
#include <vector>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
int a[102];
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 s, ans = 0;
        for(int i = 0; i < n; i++){
            s = sum^a[i];
            if(s<a[i]) ans++;
        }
        cout << ans << endl;
    }
    return 0;
}

Profile picture

Written by Armin Li , a venture capitalist. [Weibo] [Subscribe]