POJ 2975 Nim 题解《挑战程序设计竞赛》

POJ 2975 Nim 

Nim招数：在经典Nim游戏中，先手有多少种取胜方法？

4.2找出游戏的必胜策略 

Nim与Grundy数

经典算法中，XOR=k₀^k₁^…^k_n-1，若为0，则先手必败，否则必胜。在必胜态时，先手要做的就是拿走某堆石头中的m个，使得XOR变为0，将必败态转嫁给后手，题目就是在问有几种使XOR变为0的方法。

假设从第i堆石头拿走m块就是这些方法中的一种，则有(k_i-m)^(XOR^k_i)=0。这里(k_i-m)代表第i堆石头拿走m块剩余的部分，(XOR^k_i)代表从XOR中去掉k_i这一项，因为一个数连续异或两遍任意数都保持不变。

再来看(k_i-m)^(XOR^k_i)=0，若两个数异或后结果为0，则说明这两个数相等（每一个比特都相等）。于是k_i-m=XOR^k_i，也即m=k_i-XOR^k_i。同时m必须满足1≤m≤k_i，所以k_i＞XOR^k_i，如此才能为第i堆石头带来一个可行解。

#include <iostream>
#define MAX_N  1000

int n;
int k[MAX_N];

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    while (scanf("%d", &n), n)
    {
        for (int i = 0; i < n; ++i)
        {
            scanf("%d", k + i);
        }

        int XOR = 0;
        for (int i = 0; i < n; ++i)
        {
            XOR ^= k[i];
        }

        int result = 0;
        for (int i = 0; i < n; ++i)
        {
            if (k[i] > (XOR ^ k[i]))
            {
                ++result;
            }
        }
        printf("%d\n", result);
    }
#ifndef ONLINE_JUDGE
    fclose(stdin);
#endif
    return 0;
}

 知识共享署名-非商业性使用-相同方式共享：码农场 » POJ 2975 Nim 题解《挑战程序设计竞赛》