HDU 1850 Being a Good Boy in Spring

Description

尼姆博弈求先手胜出方案数

题目链接： http://acm.hdu.edu.cn/showproblem.php?pid=1850

Analyze

尼姆博弈，每堆数目异或和(flag),若为0则必败，输出0

若flag != 0，则有必胜方案

取 a1 ^ a2 ^ a3 ^ ··· ^ ak ^ ··· ^ an = flag

取 b = a1 ^ a2 ^ a3 ^ ··· ^ a[k - 1] ^ a[k + 1] ^ ··· ^an (略去ak)

则上式改为 b ^ ak = flag

若要从ak中取走c使flag = 0

则(ak - c) == b (两个相同的数字异或结果为0)

上式三者皆为正整数，意味着需满足条件 ak > b

又∵ flag = b ^ ak

∴ flag ^ ak = (b ^ ak) ^ ak = b < ak

如此一来，对于每一个a[i], 若flag ^ a[i] < a[i]， 则有这样一种方案可行

Code

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

int a[1005];

int main()
{
    int n;
    while(~scanf("%d", &n) && n)
    {
        int flag = 0;
        for(int i = 0; i < n; ++i)
        {
            scanf("%d", &a[i]);
            flag ^= a[i];
        }
        if(!flag)
            cout << '0' << '\n';
        else
        {
            int cnt = 0;
            for(int i = 0; i < n; ++i)
                if((flag ^ a[i]) < a[i])
                    cnt++;
            cout << cnt << '\n';
        }
    }
    return 0;
}