题解 POJ 1740 A New Stone Game

题目链接
题意:有n堆石子,两人轮流操作,每次每个人可以从一堆中拿走若干个扔掉(必须),并且可以从中拿走一些分到别的有石子的堆里(可选),当一个人不能拿时这个人输。给定状态,问是否先手必胜。

我们参考普通取石子游戏可知,如果只有一堆,先手必胜。
如果有两堆一样,先手必败,对称博弈,第一个人怎么取,第二个人也可以怎么取,直到第一个人无法取为止。
如果有四堆两两一样,还是先手必败,第一个人无论如何取,第二个人可以再次取成两两一样。
如果有$2 \times k$堆两两一样,还是先手必败。
注意:除了上述情况,都是先手必胜
因为先手无论奇偶总能把最多的那堆匀到其他堆上使之两两相等,(若堆数是奇数那么最多的那堆就不剩了,若堆数是偶数,那么最多的那堆应该剩下和最小的一堆进行匹配)。
证明如下图。设一共有9堆分别是1,2,3,3,5,7,8,9,11(排序后)。
[图片已挂]

最大堆为11,蓝色的为原来高度,绿色的为要补的,可以看出绿色的和总小于最大值(黄色)。

代码:https://gist.github.com/zrt/c12bd88cd2d4689c04f6

评论小助手

评论正在加载...

Tip: 点击下方链接切换到 Disqus 评论框可以获得邮件提醒哦
🗣️ 加载 Disqus 评论框