今天封寝室了,无聊看了看电视剧,正好看了天才基本法,看到了如图所示的问题
这个问题可以抽象成 有n个石子,每次可以拿1-3个,问先手是否可以必胜
解题思路
当$n = 1 , 2 , 3$ 时先手必胜 ,$n = 4$ 时 先手必败。
那么 ,$n = 5 , 6 , 7$ 先手还是必胜。
进而我们可以得到一个递推式 , $f[i]$ 表示剩余$i$颗石子时,先手是否必胜
$$
f[1] = f[2] = f[3] = 1
$$
$$
f[i] = (!f[i - 1])\ |\ (!f[i - 2]) \ |\ (!f[i - 3])
$$
其实就是当时 $n \% 4 == 0$,先手必败,否者先手必胜,因为可以拿$1-3$颗,那么我必然能够走到先手必败态,显然电视剧是在欺负人啊!
还好,看了后续,主角没那么傻,反而拓展到$n$个物品,每次可以拿$1-m$个物品的情况,
那么 $n\%(m+1)==0$时 ,先手必败,否则先手必胜。