http://acm.hdu.edu.cn/showproblem.php?pid=5724
题目大意
两人在的棋盘上下棋,每次可以任选一个棋子,将其移动到右边第一个空格子内,无法移动的那一方输,问先手是否必胜?
思路及做法
显然是经典博弈论,需要用到SG函数,这里,我们可以知道,因为任意一步的后继不超过20种,所以SG函数的取值范围在20以内。注意到每行的结果基本上是不相关的,所以暴力枚举每一行的状态,算出对应状态SG函数的取值,然后对于每次询问即可以直接从SG函数内得到答案。
最后利用SG函数的性质来合并不同的行的状态即可。
算法复杂度为,利用状态压缩,空间复杂度为
AC-Code (C++)
Time 546MS, Memory 5680K
https://github.com/erjiaqing/my_solutions/blob/master/hdu/5724.cpp