P6814 题解

· · 题解

首先注意到如果存在连续三个或更多同种颜色的棋子，且它们之间至少有一个空位，那么这个玩家永远也不会输，因为它在这一段内部移动永远都是合法的。这启发我们对一段颜色相同的棋子将它们合起来考虑。

对于一段极长的同色棋子，我们只关心棋子的个数、第一个与最后一个的位置差、以及这一段与下一段的距离，至于第一个和最后一个之间棋子是怎么排列的我们并不关心。因此我们可以使用一个三元组 (t,n,d,l) 来表示一段长为 d 的格子中有 n 个颜色为 t 的棋子（第一个和第 d 个格子均有棋子），这一段格子后有 l 个空位，空位后面是另一种颜色的棋子。

发现 n=2 的情况是比较关键的，因为这种情况下不会出现能永远合法的操作，所以两个人都想尽可能占用对方的格子。同时在 n=1 的时候会出现被夹住的点，这个点的决策并不是很好考虑，因为它没有围住一段区域。所以我们先假定所有段都有 n=2。

此时如果我们让两个人的策略都是一直进攻，即永远不会将一段的两个点向内移动，那么这个游戏就是以所有 l 为每一堆棋子数的 NIM 游戏，直接计算异或和即可求出谁必胜。但现在玩家仍然可以选择向回退，那么结果又会如何呢？我们发现这个操作不会影响答案，这是一个类似于 Northcott Game 的博弈，简单来说就是一个 NIM 游戏，但是可以做有限次在一堆中添加棋子的操作。不难发现在原游戏中有必胜策略的一方不会选择添加棋子，而如果另一方添加了棋子，他可以一步把这些棋子删掉。由于只能添加有限次，所以原来必败的一方还是无法取得胜利。回到这道题中，如果一个人一直向前就能获胜，他一定不会后退。另一方面，如果必败者向后退了，则另一个人将相邻的棋子向前进同样的距离即可回到原来的状态。显然后退的次数是有限的，所以这个操作不改变获胜者。

现在我们解决了 n=2 的情况，然后我们尝试加入 n>2 的情形，即此时 n\ge 2。称满足 n>2 且 d>n 的一段为必胜段（即可以无限在内部操作的段）。我们容易求出每个人有几个必胜段，以及有几种本质不同的操作之后可以使一段变成必胜段。这里本质不同的操作指的是操作不同的段或者向不同的方向拓展，但向同一方向拓展不同的步数不是本质不同的。因此一个人可以做的事情是将自己的一个即将成为必胜段的段变成必胜段，或者去堵住一个对方的能形成必胜段的操作（直接贴住这一段的端点，就可以直接断绝这个方向上的所有操作）。

如果后手有一个必胜段，或至少存在两种不同的变成必胜段的方式，那么先手无法阻止后手形成必胜段，此时后手必然不败。如果先手有必胜段或能形成必胜段，则先手也不败，此时是平局。否则后手第一步形成一个必胜段之后先手永远无法形成必胜段，最后必然会慢慢被后手逼死，所以后手必胜。

否则如果后手没有必胜段，也没有变成必胜段的方式，那么如果先手可以形成必胜段，则先手必胜。否则就是 n=2 的情况，根据 NIM 值即可判断。

最后一种情况就是后手没有必胜段，但是存在恰好一种方式变出一个必胜段。此时先手有两种决策：去堵住这个变成必胜段的方式以争取胜利，或者自己变出一个必胜段保住平局。如果先手选择堵住对方，那么其操作是唯一的，可以做这步操作之后交换先后手，然后就成为了一个新的子问题。注意在这个子问题中原来的后手失去了形成必胜段的方法，且显然任何一个玩家都不会让对手产生新的必胜段的机会，因此至多递归两次之后两个人都没有必胜段了，所以不会继续递归。除了这种情况，如果先手有一个必胜段或可以变出来一个，则他也可以选择平局结束，两种情况选更优的即可。

最后我们只需要解决 n 可以 =1 的问题。我们发现 1 其实没什么太大的用处，因为它迟早会被两边的点堵死。但有些时候它可能可以用来在外部局面会输掉的情况下在内部搞一些事情让对方破坏掉外部的局面。所以我们的想法是能不能将这些 n=1 的段变成一些等价的 n>1 的段。

首先全是 n=1 的段以及只有一个 n>1 的这些情况都容易特判。下面假设有至少两个 n>1 的段。考虑若干个连续的段 p_0=(t_0,n_0,d_0,l_0),p_1,p_2,\cdots,p_k，其中 p_0,p_k 满足 n>1，而其它段都有 n=1。先考虑 t_0=t_k 的情形。此时中间的所有段全是没用的，因为两侧的段都有至少两个棋子，此时可以使用内部的棋子向内逼近，所以中间这片区域其实都是属于 t_0 这个玩家的，他可以自由活动。但棋子毕竟还是会占据一个格子，所以有可能会出现直接堵死这片区域的情况，因此我们对这一段的处理是把中间的棋子全变成和外部颜色相同的棋子，然后把这些段合并成一个段。

对于 t_0\ne t_k 的情形，中间的棋子不再属于某一个固定的人。不妨设 t_0=0,t_k=1，此时观察可以发现，对于中间的某个颜色为 0 的棋子，只有向右移动才是一步有效移动，而一个颜色为 1 的棋子只有向左移动才是有效移动。这是因为每个颜色为 0 的棋子后面都紧跟一个颜色为 1 的棋子，所以如果他选择向左移动后者可以立刻跟进，所以这样的操作没有任何意义（虽然扩大了这个颜色为 1 的棋子右侧的距离，但这个距离只是更方便后面的棋子向左移动了，还是没有意义）。因此这个问题和前文 n=2 情形下的 Northcott Game 是极为类似的，可以看作相邻的一对 (0,1) 之间形成一堆棋子，对这些棋子做 Northcott Game，增加棋子的操作就是向左移动 0 或向右移动 1，这样的操作只会进行有限步。不过这整个局面是位于大的 Northcott Game 的，所以决策者不一定要现在这里做决策，而是可以基于整个局面进行决策。所以将相邻的 (0,1) 之间的距离保留，其它的 l 全部变成 0，然后直接扔回原来的序列，将这些段当作普通的 n=2 的段即可。

综上所述，整个过程的复杂度就是线性的，如果一开始不做归并排序直接排序带一个 \log，但影响不大。

代码