hdu 1730 Northcott Game (二维sg函数)

hdu 1730

题意:n行格子,每行m个,每行有一黑一白两个棋子,给定初始位置,先手执黑棋,后手执白棋,每次可以在同一行内向左移动,不能超过边界,且不能越过对方的棋子,同一个格子只能有一个棋子。问先手是否必赢。

 

思路:可以看成n个独立的游戏的 叠加。。。所以最后异或和一下就好。。

我们来求sg函数。。。一开始的是想把点对hash成一个数。。。然后发现其实没必要。。。直接二维就好了。。

由于初始化的时候要考虑最大。。。所以sg函数的值会有一个便宜。。。和设定N有关。。减去偏移就好了。。。(我的代码里这个偏移是11026)

1A蛤蛤蛤

 

 

 

 

 

 

 

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz