POJ 1740 A New Stone Game 题解《挑战程序设计竞赛》

POJ 1740 A New Stone Game 

新石器游戏：有n堆石头，两个人轮流选择一个堆，拿走任意石头并将任意石头移至其他堆。拿走最后一块石头的人获胜，问先手赢还是后手赢？

4.2找出游戏的必胜策略 

推理与动态规划算法

难点在于提出与证明一个基本推理。

假设石头堆是对称的，即每堆石头数量的出现次数都是偶数。则后手可以复制先手的所有操作而维持状态不变（偶数状态，先后手顺序状态都不变），或取胜（取完所有石头）。当然后手也可以选择不取胜，并且改变状态。但双方都出全力的情况下，后手不会如此放水，不必考虑这种情况。所以偶数态是后手必胜。

假设石头堆不是对称的，即每堆石头数量的出现次数至少有一个奇数。则先手可以拿光最大的奇数堆，如果仍然存在奇数堆，则用这堆石头将这些奇数堆填为偶数堆（这么做是一定可能的吗？是的，假设第i种奇数堆为a[i]，a[i].m 为石头个数，a[i].n为堆的个数等于2k+1，顺序按石头个数增序排列。既然我们的目的是配成偶数，那么就不考虑2k了。去掉所有的2k，反正这部分一定是偶数。这样a[i].n=1。我们拿光a[a.length].m，于是最后一个奇数堆不存在了，变为0，也就是偶数。考虑剩下的奇数堆，对任意序列x1,x2,…xn，相邻两项之差的和等于x2-x1 + x3-x2 + … + xn – x_n-1 = xn – x1，一定小于xn，所以拿光的那堆石子一定足够将这些奇数堆填平，具体填平方法是a[i].m += a[i+1].m-a[i].m， i += 2，循环k次。项数为2k都能填平，项数为k肯定能填平）。如此做后，状态等效于偶数态，但先后手交换了顺序，所以奇数态是先手必胜。

#include <iostream>

#define MAX_N 100
#define MAX_N_1 MAX_N + 1
int count[MAX_N_1];

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    int n, m, i;
    while (scanf("%d", &n), n)
    {
        memset(count, 0, sizeof(count));
        for (i = 0; i < n; ++i)
        {
            scanf("%d", &m);
            ++count[m];
        }
        for (i = 1; i <= MAX_N; ++i)
        {
            if (count[i] & 1)
                break;
        }
        printf("%d\n", i != MAX_N_1);
    }
#ifndef ONLINE_JUDGE
    fclose(stdin);
#endif
    return 0;
}

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