Chequer

· · 题解

Chequer

订了就写一下。

一个 H\times W 的棋盘上有若干个障碍和棋子。Alice 和 Bob 轮流行动，每次移动一颗棋子，可以在行内（一行视为一个环）移动或移动到下一行，不能走障碍。允许多颗棋子走到相同的位置。每颗棋子不能走到自己走过的位置。不能行动者输。

据说是原，不知道出处。

每颗棋子显然是独立的游戏，所以求出 sg函数，最后异或一下就行了。

行内由于是环，所以看起来像是环形的 dp，但其实看一下就发现一旦走了一侧就不能回头（不能走重复的地方），所以是行内线性的。

然后注意这样的话是三种情况，不是两种；另一种情况是刚进入这一行，方向不定。

设 f(i,j,0/1/2) 表示在第 i 行，第 j 列，向左/随意/向右。

转移的时候，如果有障碍，就用相邻的障碍划分区间，然后从两边开始分别推一次。

例：f(i,j,1)=\operatorname{MEX}(f(i,j-1,0),f(i,j+1,2),f(i+1,j,1))，请注意子局面的关系。

不难发现只有 f(i,j,1) 对上一行转移有用，所以只存这个也行。

没有障碍的话，不难发现 把本身作为障碍 即可；此时需要整个序列推一遍，W 次下来这一行就是 \mathcal{O(W^2)} 的。

不过稍加观察发现重复部分很多，所以就有一个预处理加速的动机。

以选择向左走的集散过程为例，本质是用 -1 从 j+1 走到 W，再走到 j-1，每次和下一行对应位进行 \operatorname{MEX}。

那也就是前后缀的 \operatorname{MEX}，但是前缀查询时 初始值不同。

又由于 值域很小（三个数参加 \operatorname{MEX} 运算，不可能超过 2），就可以对所有的初始值处理出前缀。

对称地处理选择向右走的部分，一共处理这些数组：

后两个处理的时候，可以写成 to(st,j)，然后用 to(\operatorname{MEX}(st,f(i+1,j,1)),nxt) 转移。

预处理的部分是线性的，同时转移优化到了 O(1)；注意特殊判断 m=1。

时间复杂度 O(HW)，有点卡常（指，\operatorname{MEX} 不要用 std::set）。

Code:

constexpr int N=1005;
int n,m;
char mp[N][N];
int f[N][N];
int lst(int x){return x==1?m:x-1;}
int nxt(int x){return x==m?1:x+1;}
int mex(const std::initializer_list<int> &L){
    int x=-1;
    bool vis[4]={};
    for(int it:L) if(~it) vis[it]=true;
    for(;vis[++x];);
    return x;
}
void _main_(){
    std::scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i) std::scanf("%s",mp[i]+1);
    int ans=0;
    __builtin_memset(f[n+1]+1,-1,sizeof(f[n+1][0])*m);
    for(int i=n;i;--i){
        static int V[N];
        int tot=0;
        for(int j=1;j<=m;++j) if(mp[i][j]=='#') V[++tot]=j;
        if(tot!=0){
            //g[j] 对应 f[i][j][0]，h[j] 对应 f[i][j][2]
            static int g[N],h[N];
            for(int j:V) g[j]=h[j]=f[i][j]=-1;
            for(int it=1,ot,j;it<=tot;++it)
                for(j=nxt(V[it]),ot=it==tot?V[1]:V[it+1];j!=ot;j=nxt(j))
                    g[j]=mex({g[lst(j)],f[i+1][j]});
            for(int it=1,ot,j;it<=tot;++it)
                for(j=lst(it==tot?V[1]:V[it+1]),ot=V[it];j!=ot;j=lst(j))
                    h[j]=mex({h[nxt(j)],f[i+1][j]});
            for(int j=1;j<=m;++j) if(mp[i][j]!='#')
                f[i][j]=mex({g[lst(j)],h[nxt(j)],f[i+1][j]});
        }
        else if(m==1) f[i][1]=mex({f[i+1][1]});
        else{
            //3 是无初始值（-1）
            static int from_pre[4][N],to_pre[4][N],from_suf[4][N],to_suf[4][N];
            for(int sg:{0,1,2,3}){
                from_pre[sg][0]=from_suf[sg][m+1]=sg==3?-1:sg;
                for(int j=1;j<=m;++j) from_pre[sg][j]=mex({from_pre[sg][j-1],f[i+1][j]});
                for(int j=m;j;--j) from_suf[sg][j]=mex({from_suf[sg][j+1],f[i+1][j]});
                to_pre[sg][0]=to_suf[sg][m+1]=sg==3?-1:sg;
            }
            for(int j=1;j<=m;++j) for(int sg:{0,1,2,3})
                to_pre[sg][j]=to_pre[mex({(sg==3?-1:sg),f[i+1][j]})][j-1];
            for(int j=m;j;--j) for(int sg:{0,1,2,3})
                to_suf[sg][j]=to_suf[mex({(sg==3?-1:sg),f[i+1][j]})][j+1];
            f[i][1]=mex({to_suf[3][2],from_suf[3][2],f[i+1][1]});
            f[i][m]=mex({to_pre[3][m-1],from_pre[3][m-1],f[i+1][m]});
            for(int j=2;j<m;++j)
                f[i][j]=mex({from_pre[to_suf[3][j+1]][j-1],from_suf[to_pre[3][j-1]][j+1],f[i+1][j]});
        }
    }
    for(int i=1;i<=n;++i) for(int j=1;j<=m;++j)
        if(mp[i][j]=='B') ans^=f[i][j];
    std::puts(ans?"A":"B");
}