题解：P16023 [ICPC 2021 NAC] Token Game

· · 题解

题意简述

棋盘上有两枚棋子。每次选择一枚棋子，将它的一个坐标严格减小，且不能越过或落到另一枚棋子上。求第一步能走到必败态的合法操作数量。

解题思路

先考虑一维辅助游戏。状态 (i,j) 表示两枚棋子在某一维的坐标。当 |i-j|\le1 时，将它视为终止状态；否则可以任意减小其中一个坐标。记其 SG 函数为 f_{i,j}，则：

f_{i,j}=\operatorname{mex}\left(\set{f_{k,j}\mid1\le k<i}\cup\set{f_{i,k}\mid1\le k<j}\right)

按 i,j 递增的顺序即可计算。若 |i-j|\ge2，总能把较大的坐标减到较小坐标加一，从而到达 SG 值为 0 的终止状态，所以此时 f_{i,j}\ne0。

回到二维游戏，令：

\begin{aligned} d_x & = |x_1-x_2| \\ d_y & = |y_1-y_2| \end{aligned}

首先分类讨论靠近边界的局面。

剩下 d_x,d_y\ge2。此时两枚棋子既不同行也不同列，减小任意坐标都不会被另一枚棋子阻挡。只保留仍满足两维差均至少为 2 的操作时，横纵两维恰好是两个独立的一维辅助游戏。

若一步走到边界，但没有相邻，则目标已经由上一类证明为必胜态。另一方面，异或为零的目标不可能只有某一维进入终止状态，因为另一维的 SG 值非零。因此当前局面必败当且仅当：

f_{x_1,x_2}\mathbin{\operatorname{xor}}f_{y_1,y_2}=0

直接枚举每组询问的所有移动已经可以通过，但还可以预处理目标坐标，将询问降为对数时间。

考虑把某一坐标从 x 减小到 v。另一枚棋子在同一维的坐标为 y，两枚棋子在另一维的坐标为 a,b。合法目标形成区间 [l,x-1]；若 a=b 且另一枚棋子位于左侧，还需令 l=y+1，从而排除落到或越过另一枚棋子的操作。

记 d=|a-b|，必败目标可以分为三类。

对每个 y 和 SG 值 g，预先保存所有满足 |v-y|\ge2 且 f_{v,y}=g 的 v。这些坐标天然递增。第三类目标数便可用两次二分统计，前两类只需常数次判断。

四种移动分别调用一次相同的计数函数。设棋盘边长为 M=300，SG 预处理需要 O(M^3) 时间，单组询问需要 O(\log M) 时间，空间复杂度为 O(M^2)。

正确性证明

相邻局面中，后手始终可以把先手移动后的另一枚棋子移到对应相邻位置。这个应对不会越过棋子，并且每两步都严格减小坐标，所以相邻局面为必败态。任何满足某一维差至多为 1 的非相邻局面都能一步进入相邻局面，因此为必胜态。

在两维差均至少为 2 的区域内，横纵坐标的合法减小互不影响，局面 SG 值等于两维辅助游戏 SG 值的异或。离开该区域却不相邻只会到达已证明的必胜态，不会增加新的必败目标。因此异或为零恰好刻画全部内部必败态。

calc 首先构造所有不越界、不穿过另一枚棋子的目标区间。另一维差为 0 或 1 时，它逐一检查全部可能的相邻必败目标；另一维差至少为 2 时，预处理表又精确保存全部 SG 值相等的内部目标。三类互斥且覆盖所有必败态，所以四次 calc 之和就是第一步必胜操作数。

参考代码

#include <bits/stdc++.h>
using namespace std;

const int N=305;
const int mx=300;
int f[N][N];
bool vis[N*2];
vector<int> pos[N][N*2];
int calc(int x,int y,int a,int b)
{
    int l=1,r=x-1;
    if(a==b&&y<x)l=y+1;
    if(l>r)return 0;
    int d=abs(a-b);
    if(d==0)return (l<=y-1&&y-1<=r)+(l<=y+1&&y+1<=r);
    if(d==1)return l<=y&&y<=r;
    auto &v=pos[y][f[a][b]];
    return upper_bound(v.begin(),v.end(),r)-lower_bound(v.begin(),v.end(),l);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    for(int i=1;i<=mx;i++)
    {
        for(int j=1;j<=mx;j++)
        {
            if(abs(i-j)<=1)continue;
            memset(vis,0,sizeof vis);
            for(int k=1;k<i;k++)vis[f[k][j]]=1;
            for(int k=1;k<j;k++)vis[f[i][k]]=1;
            while(vis[f[i][j]])f[i][j]++;
        }
    }
    for(int i=1;i<=mx;i++)
    {
        for(int j=1;j<=mx;j++)if(abs(i-j)>=2)pos[j][f[i][j]].push_back(i);
    }
    int q;
    cin>>q;
    while(q--)
    {
        int x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        int ans=calc(x1,x2,y1,y2)+calc(y1,y2,x1,x2)+calc(x2,x1,y2,y1)+calc(y2,y1,x2,x1);
        cout<<ans<<'\n';
    }
    return 0;
}