题解 POJ 2425 A Chess Game

[题目链接][1]
题意:给定一个有向无环图(DAG),上面放有一些旗子,旗子可以重合,两个人轮流操作,每次可以把一个旗子从一个位置移动到相邻的位置,无法移动时输,询问先手是否必胜。

这道题可以把每个旗子看作单独的一个游戏,那么所有这些旗子的状态SG值,就是这些旗子各自SG值的Xor和,可以记忆化搜索dfs,暴力算SG值判断即可。

代码:https://gist.github.com/zrt/f08a73ad348ec4a20286
[1]: http://poj.org/problem?id=2425

评论小助手

评论正在加载...

Tip: 点击下方链接切换到 Disqus 评论框可以获得邮件提醒哦
🗣️ 加载 Disqus 评论框