1. 首页
  2. 博弈

HDU 5754 Life Winner Bo (博弈)

题目链接:点我~~

题意:~~

思路:

我们依次分析每一种棋子。

①王。

首先注意一个3*3的棋盘,开始在(1,1),问走到(3,3)谁有必胜策略。

穷举所有情况,容易发现这是后手赢。

对于NM更大的情况,我们把横坐标每隔3、纵坐标每隔3的点都画出来,这些点都是符合后手胜的。
(因为无论先手怎么移动,后手都能重新移动到这些格子,直到到了终点)

如果初始点不在这些点上,就必然是先手胜。因为先手可以立刻移动到上述的点。

②车。

注意到,如果目前的位置距离终点的xy坐标差相等,一定是后手胜。
(因为先手只能向下或者向右走一段路;无论他往哪里走,后手往另一维走相同的步数,依然保持这一样一种状态。)

反之,先手必然能走到一处相等的位置,转化为上述问题,所以一定是先手胜。

③马。

同样还是画图可以得到规律。

在大多数情况下都是平局。在模3域下,某些地方会存在先后手赢。

④皇后。

画画图后,我们可以将问题转化为:

“有两堆石子,每次可以在一堆里取任意(非空)颗(相当于是车的走法),或者在两堆里取相同(非空)颗(相当于是象的走法),取到最后一颗石子的人获胜,问先后手谁有必胜策略。”
此题中N1000,可以直接用DP的方法解决。
设f[x][y]为横坐标距离终点x步,纵坐标距离终点y步时,必胜的是先手还是后手。

直接转移的话,可以枚举先手的下一步决策进行转移,这样是O(N^3)的。

注意到转移只是一行、一列或者斜着一列,这些都可以通过前缀和,做到最终O(N^2)

其实对于更大的N也是可以做的。

由于叙述起来比较麻烦,具体的结论和证明可以参见:

https://en.wikipedia.org/wiki/Wythoff\%27s\_game

评分 0, 满分 5 星
0
1
看完收藏一下,下次也能找得到
  • 版权声明:本文基于《知识共享署名-相同方式共享 3.0 中国大陆许可协议》发布,转载请遵循本协议
  • 文章链接:http://www.carlstedt.cn/archives/1071 (转载时请注明本文出处及文章链接)
上一篇:
:下一篇

发表评论

gravatar

快来吐槽一下吧!

  1. .01 4:06
  2. .02 1:47
  3. .03 3:39
  4. .04 1:40