放牧代码和思想
专注自然语言处理、机器学习算法
    恕不接待索要源码语料者、索求技术方案者、以及不Google的懒人。

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

目录

挑战程序设计竞赛.jpg

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;
}
15354164 hankcs 1740 Accepted 164K 0MS C++ 578B 2016-04-05 02:33:28


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

分享到:更多 ()

评论 欢迎留言

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机