给定一张无向图,上面有一些棋子,两个顶尖聪明的人在做游戏,每人每次必须将可以移动的棋子进行移动,不能移动的人输
题目中的要求实际是“不论前面输与否,只要最后一个棋子胜利,那么就算胜利”
这样的话,能赢得游戏必须赢
因为两个人都顶尖聪明,因此当一个人知道某一个游戏一定会输的话,它一定会尽力缩短游戏的时间,当它知道某一个游戏一定会赢的话,一定会尽力延长游戏的时间(毕竟都是为了追求最终的胜利嘛233)
但是!我们怎么来处理时间的?暴力枚举博弈树肯定是不可取的,so我们来研究一下这个问题
定义Every-SG游戏
Every-SG游戏与普通SG游戏最大的不同就是它多了一维时间
对于$SG$值为$0$的点,我们需要知道最少需要多少步才能走到结束,
对于$SG$值不为$0$的点,我们需要知道最多需要多少步结束
这样我们用$step$变量来记录这个步数
$step(u) = \begin{cases} 0, & \text{$u为终止状态$}\ max{step(v)}, & \text{ $sg(u)\neq 0\land v为u的后继\land sg(v)=0$ }\ min{step(v)}, & \text{$sg(u)=0\land v为u的后继$} \end{cases}$
对于Every-SG游戏先手必胜当且仅当单一游戏中最大的step为奇数。
定理是显然的:最大的单一游戏步数如果是奇数的话那么肯定是先手取得进行最后一步,否则一定是对手取走最后一个棋子。
这种题目不怎么好找,到现在也就找到一道
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。