SSOJ2943取石子游戏1
1553+
作者:crxis 发布:2022-03-11 分类:博弈论
题目大意:2个人取n个石子,每次至少取1颗,至多取m颗,无法操作则输,请问先手是否有必胜策略?
有一种有趣的游戏,玩法如下:
玩家: $2$ 人;
道具: $N$ 颗石子;
规则:
1、游戏双方轮流取石子;
2、每人每次取走若干颗石子(最少取 $1$ 颗,最多取 $K$ 颗);
3、石子取光,则游戏结束;
4、最后取石子的一方为胜。
假如参与游戏的玩家都非常聪明,问最后谁会获胜?
【输入】
输入仅一行,两个整数 $N$ 和 $K$ 。
【输出】
输出仅一行,一个整数,若先手获胜输出 $1$,后手获胜输出 $2$。
【输入样例】
23 3
【输出样例】
1
【提示】
数据范围与提示:
对于全部数据, $1≤N≤10^5 ,1≤K≤N$。
解题思路
逐个试一下:0是必败,1~m是必胜,因为可以取1~m颗石子到0,让另一人无法操作。m+1是必败,因为他取完后,另一个人都是必胜状态。之后m个是必胜状态,因为他可以让另一人取的时候只剩下m+1个石子……
小结:能到必败的状态都是必胜状态,因为他可以当对手输;不能到必败状态则必败,因为下一次另一人的状态总是必胜。
程序实现
递推写法:
找到规律:
原来是这样用的 😉