题解 POJ 2484 A Funny Game

题目链接
题意:有n个硬币排成一圈,两个人轮流操作,每次可以取走一个或者相邻的连个硬币(只算最开始相邻的,取之后才相邻的不算),问先手必胜还是必败。


这个题可以证明若n>=3,则先手必败。
对称博弈
n>=3,先手第一次必然把这个环拆成一个链,然后无论这条链长度的奇偶,后手总是可以把这条链分成两条相等的链,于是先手在一条链上做什么,后手就可以做什么。知道先手无法操作,后手胜。

代码:https://gist.github.com/zrt/871be6eb3ca6bf14ed8a

评论小助手

评论正在加载...

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