HDU 5724 Chess

Posted on By 二价氢

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