第一眼看到这道题,其实很容易会联想到经典的bash game问题
这道题并没有巴什博弈那么复杂,但也算一道比较新颖的博弈论题吧
还是很适合作为一道博弈论入门题的
题目大意
有A/B两堆石子,两名玩家进行取石子比赛,玩法很朴素,就两种取法:
①在A堆取1颗,在B堆取2颗
②在A堆取2颗,在B堆取1颗
谁先无法取石子,谁就输了。
对于每组数据A B,问:
先手必胜,还是后手必胜
(A B 都在long long的数据范围内)
保姆级思路解析
一般来说,如果题目中有类似游戏双方都很聪明
这种字眼,
那一定是一道博弈论题,而不是模拟题
那就一定要往先手必胜or后手必胜的角度考虑
那我们再来看看这个游戏过程:
不难发现,每过一个回合相当于:A-3
B-3
然后,两名玩家是不是好像又回到了游戏最开始的状态
此时的状态就等价于开始了一场初始石子数为A-3
和B-3
的游戏
换句话说,对于一组数据(a,b),它的结果和(a-3,b-3)是一样的
这样一想,思维就流淌出来了:这道题肯定和3有关!
接下去我们要考虑,在什么状态下,游戏会结束?
既然要取到不能取为止,玩家就应该把策略聚焦到更少的那一堆上,就会跟容易kill对手
那么取完之后,如果能让更少的一堆数量变为0,就获胜了
(不需要考虑1、1这种终止情况。为什么呢?因为倘若结束时的状态是1、1,那么上一状态换一种取法的结果一定是2、0)
再考虑到:每过一个回合相当于:A-3
B-3
后手必胜的策略就很清晰了,只要较小的数是三的倍数,那么后手必胜
这种情况下,只要先手选①后手选②,先手选②后手选①,那么就能坐等先手完蛋
而当较小数不是3的倍数
先手想要获胜也很简单,如果较小数%3==1,那我先就在这堆取1,
如果%3等于2,那么我就在这堆取2
接下来,此前的先手就变为了较小的数是三的倍数
情况下的后手,就坐等。。。
很简单对吧?