题解：P16023 [ICPC 2021 NAC] Token Game

lailai0916 · 2026-08-30 13:55:02 · 题解

题意简述

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

解题思路

先构造一维辅助游戏。状态 (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)

每个非终止状态都能一步到达终止状态。因此，其 SG 值一定非零。

回到二维游戏，记横纵坐标差分别为 d_x,d_y。

若 d_x+d_y=1，两枚棋子相邻。后手可以关于两枚棋子的中点模仿先手，因此这是必败态。
若 d_x\le1 或 d_y\le1，但两枚棋子不相邻，先手可以直接走到相邻状态。这是必胜态。
若 d_x,d_y\ge2，留在该区域内的操作等价于两个一维辅助游戏的和。进入边界的操作只会到达上一类必胜态。SG 值为零的目标也不可能进入边界。否则一维 SG 值为零，另一维却非零，与异或为零矛盾。因此，当前局面必败当且仅当：

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

预处理所有 1\le i,j\le300 的 f_{i,j}。每组询问枚举四个坐标的减小值。排除非法操作，再统计走入必败态的操作数。

SG 表的预处理复杂度为 O(M^3)，每组询问的复杂度为 O(M)，其中 M=300；空间复杂度为 O(M^2)。

参考代码

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

const int N=305;
const int mx=300;
int f[N][N];
bool vis[N*2];
bool lose(int x1,int y1,int x2,int y2)
{
    int dx=abs(x1-x2),dy=abs(y1-y2);
    if(dx+dy==1)return 1;
    if(dx<=1||dy<=1)return 0;
    return f[x1][x2]==f[y1][y2];
}
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]++;
        }
    }
    int q;
    cin>>q;
    while(q--)
    {
        int x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        int ans=0;
        for(int i=1;i<x1;i++)
        {
            if(y1==y2&&i<=x2&&x2<x1)continue;
            ans+=lose(i,y1,x2,y2);
        }
        for(int i=1;i<y1;i++)
        {
            if(x1==x2&&i<=y2&&y2<y1)continue;
            ans+=lose(x1,i,x2,y2);
        }
        for(int i=1;i<x2;i++)
        {
            if(y1==y2&&i<=x1&&x1<x2)continue;
            ans+=lose(x1,y1,i,y2);
        }
        for(int i=1;i<y2;i++)
        {
            if(x1==x2&&i<=y1&&y1<y2)continue;
            ans+=lose(x1,y1,x2,i);
        }
        cout<<ans<<'\n';
    }
    return 0;
}