新石器游戏:有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 题解《挑战程序设计竞赛》