每天一道博弈论之“A funny game”(poj 2484)

  题意:

  n枚硬币排成一个环,操作为可以选择一个或相邻的两个取走(相邻指的是最开始相邻,即不会自动补成环)。问先手胜还是后手胜。

  题解:

  首先我们考虑1和2,则明显是先手必胜。

  如果大于等于3,那么先手取后一定是一条链。这时我们一定可以把这一条链变成两条相等的链。(如果链长是奇数就取掉最中间的那个,否则取掉最中间的两个)。那么一个游戏就被分成了两个相同的独立游戏。那么假如对方在某一游戏中进行了一种操作,我们只要在另一游戏中重复该操作即可。那么可以保证我们面临的两个游戏状态一定相同,而对方面临的一定不同。显然终点是两个游戏中的硬币都被取完,即两游戏状态相同,而游戏又一定是会进行完的,所以当n大于等于3时后手必胜。

http://poj.org/problem?id=2484

原文地址:https://www.cnblogs.com/zub23333/p/8538343.html