首页 > 其他 > 详细

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

时间:2018-03-10 13:06:02      阅读:215      评论:0      收藏:0      [点我收藏+]

  题意:

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

 

  题解:

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

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

 

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

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

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

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!