首页 > 其他 > 详细

CF1161C

时间:2020-05-23 23:53:52      阅读:72      评论:0      收藏:0      [点我收藏+]

题意

2n堆石子,两个人博弈,每次选择n堆,将每堆石子减少(每堆减少的量可以不相等),轮到某人时不足\(n\)堆则输了。求是否先手必胜

做法

显然谁先取走至少一堆石子谁就输了
我们发现数量为\(1\)的石子堆数量若\(\in(n,2n]\)就输了;否则就可以将其他石子数量取到\(1\),然后使得数量为\(1\)的石子堆\(\in(n,2n]\)
受次启发,猜结论:最小值数量的石子堆数量若\(\in(n,2n]\)则先手必败,否则先手必胜

证明:
若现在处必胜态,则最小值数量\(\in[1,n]\),可以对其他堆操作使得转移到必败态
若现在处必败态,则\(\in(n,2n]\),无论如何操作都转移到必胜态

CF1161C

原文:https://www.cnblogs.com/Grice/p/12945093.html

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