「EZEC」 Round 6 周年欢乐赛 象棋题解

· · 题解

P0:题外话

这题的原身是不存在博弈的，仅仅是给一个开局，问是否能够操作使得最后只剩两个棋子。但是我觉得博弈可做，于是在群上发了问，结果被神仙 @Forever_Pursuit 搞出来了。

然后还是第一次有人帮我做数据，验题和推广，之前出的题基本上都是我自己出自己验的，果然有神仙在团内就是不一样/cy

P1：基础观察

首先需要证明两个结论

  1. 如果当前局面下红方可以操作，那么黑方必然也可以，反之亦然。

证明：一个可操作的局面仅有以下几种可能。

() 100 ()
() 001 ()
() 011 ()
() 110 ()

其中 () 表示任意数量的棋子。

可以发现，在这四种状态下红黑双方均能行动，故命题得证。

由此引出下一个结论：

  1. 如果当前局面可操作，那么选择操作严格不劣于不操作。

证明：

由于每个操作都只会改变减少对方棋子的数量，而若一方能操作另一方也能操作，那么可以得出若一方不操作，让另一方操作只会减少自己的棋子数量，且不会影响对方之后的操作。故命题得证

P2：题解

对于 n\le3 的数据，出题人良心的给了不会博弈论手动模拟的同学分数，手动模拟后打表输出即可。

对于 n\le6 的数据，考虑爆搜。

暴力 dfs 寻找每一种可能。假设在某个状态下由红方行动，而他的操作会使黑方必败，则红方有必胜策略。若有平局状态，则红方可以选择平局 ，否则当前状态红方必败。（黑方同理）

暴力复杂度 O(n(n!)^2)，足够通过。

对于 n\le 15 的数据，考虑状压打表。

思路跟dfs一样，只不过用二进制记录状态，O(n^2\times2^n) 打表后 O(1) 询问，足以通过。

接下来开始讲正解思路

由于之前证明的结论，我们可以得出，若红方初始棋子数量大于黑方，那么红方必胜。

同理，若红方初始棋子数量小于黑方棋子-1，那么红方必败。

现在仅有两种情况需要讨论：

  1. 红棋数量=黑棋数量
  2. 红棋数量=黑棋数量-1

首先讨论第一种情况：

通过基础观察，我们可以发现若红棋数量=黑棋数量，红棋只可能胜利或者平局。红棋胜利的可能仅有一个：当某一步红棋走完后，黑棋无法再次行动。

考虑什么时候会出现这种情况： 定义 () 集合为一组数字出现任意次数，例如 (101) 可能为 101101，也可能是空集。 对于一个不能动的情况，由于红棋数量大于黑棋，故最后局面必然是 (10)1 这一种情况。

发现仅有两种情况能够转移得到这种情况：

(10)1100(01)\newline (10)0011(01)

由于这两种状态仅仅是 01 的位置反了过来，故我们可以认为他们等价，下面仅对第一种情况进行讨论。

继续考虑，发现仅有以下几种情况能得到上述情况：

(10)11100(01)\newline (10)11001(01)\newline (10)10110(01)

由于初始棋子数量相等，而括号内棋子数量也平衡。根据初始证明，可以得出在出现这种状况时必然轮到黑方操作。

可以发现，对于上述每一种状态，黑棋必然能够使用最佳策略避开必输局面。故如果在这种情况下轮到黑方操作，双方必然平手。

对于这种情况，红方仅有一种赢的可能：当 (10)1100(01) 或 (10)0011(01) 为初始局面。

结论：如果初始局面可以通过一次转移为不可操作局面，则红方必胜，否则必然平手。

接下来讨论第二种情况：

若红棋数量=黑棋数量-1，如果对上面的证明进行分析，那么我们可以发现此时红方的处境等价于黑方的处境。

结论：若初始局面为可操作局面，则必然平局，否则红方必败。

正解证明完成，开始讨论做法

对于 n\le 200 的数据，考虑在红棋=黑棋时暴力枚举每个位置进行操作后判断是否为不可动局面，复杂度 O(\sum n^2)

由于出题人不确定有没有 O(n^3) 做法，而其他做法的复杂度显然过不去这个，故 n 只开到了 200。

对于 n \le 10^6 的数据，考虑暴力上随机化。

发现若有一个位置能够使得变化和局面可操作，则继续判断无意义。

故对于红棋=黑棋时仍然暴力枚举，但是枚举时随机跳位置检索是否不可操作。

复杂度不太会证，但实际效果优秀，可以过 n\le 10^6 的数据。

对于 n \le 10^7 的数据，考虑移动一步后出现平局的可能状态。

上面已经讲过，仅存在 (10)0011(01) 和 (10)1100(01) 两种可能。故我们可以判断数组是否为这种情况，具体写法将在代码中给出。

复杂度 O(\sum n)


const int MAXN = 1e7+5;
const int MAXM = 1e5+5;
const int mod = 1e9+7;
int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};
int n,m,t,pos[MAXN],k,a,b,c,red,black;
inline void case1(){
  int pivot = 0,ab = 0;
  For(i,1,n-1)
    if(pos[i]==pos[i+1]) {
      if (pivot && pos[i]==1) {puts("TIE");return;}
      else if (pos[i]==1) pivot = i;
      if (pos[i]==0) ab++;
    }
  if (!pivot) {puts("TIE");return;}
  if ((pivot == 3 && pos[1] == pos[2]) || (pivot == n-3 && pos[n-1] == pos[n])) {puts("WIN");return;}
  if (ab == 2 && ((pivot > 3 && !pos[pivot-1] && !pos[pivot-2] && !pos[pivot-3]) ||
      (pivot<=n-4 && !pos[pivot+2] &&!pos[pivot+3] &&  !pos[pivot+4]))) {puts("WIN");return;}
  puts("TIE");
}
inline void case2(){
  For(i,1,n-1) if (pos[i]==pos[i+1]) {puts("TIE");return;}
  puts("LOSE");
}
signed main(){
  t = read();pos[0] = -1;
  while(t--){
    n = read();pos[n+1] = pos[n+2] = pos[n+3] = -1;
    red = 0;
    For(i,1,n) pos[i] = (get()=='1'),red+=(pos[i]==1);
    black = n-red;
    if (red>black) puts("WIN");
    else if (red<=black-2) puts("LOSE");
    else if (red==black) case1();
    else case2();
  }
}