2023NOIP A层联测17 游戏

联测17 游戏"/>

2023NOIP A层联测17 游戏

题目大意

有一个 n × m n\times m n×m的网格图，开始时有三种格子，分别为障碍，棋子和空格。

小 A A A和小 B B B在这个网格图上玩游戏，双方轮流行动，小 A A A先行动。每次行动中，当前玩家选择一枚棋子移动，设棋子所在的格子为 ( r , c ) (r,c) (r,c)，则移动规则如下：

• 可将格子移到 ( r + 1 , c ) (r+1,c) (r+1,c)（如果 r + 1 ≤ n r+1\leq n r+1≤n）、 ( r , c − 1 ) (r,c-1) (r,c−1)（如果 c > 1 c>1 c>1）、 ( r , c + 1 ) (r,c+1) (r,c+1)（如果 c < m c<m c<m）。特殊地，可以从 ( r , 1 ) (r,1) (r,1)移到 ( r , m ) (r,m) (r,m)，也可以从 ( r , m ) (r,m) (r,m)移到 ( r , 1 ) (r,1) (r,1)，也就是可以将每一行看作一个环。
• 棋子不能被移动到包含障碍的格子
• 一个格子可以包含多个棋子
• 棋子不能被移动到它曾经到过的格子（所有棋子各不相同，也就是到过的格子是对每个棋子分别记录的）

无法行动的玩家算负。

求在双方都采用最优策略的情况下，最终谁会获胜。

有 T T T组数据。

1 ≤ n , m ≤ 1000 , 1 ≤ ∑ n , ∑ m ≤ 4000 1\leq n,m\leq 1000,1\leq \sum n,\sum m\leq 4000 1≤n,m≤1000,1≤∑n,∑m≤4000

时间限制 2000 m s 2000ms 2000ms，空间限制 512 M B 512MB 512MB。

题解

由于每个格子上可以有多个棋子，且每个棋子走过的路径单独记录，所以每个棋子是独立的。因此，我们可以先计算出每个位置有棋子时的 S G SG SG值，最后再将其异或在起来，即可得到总游戏的 S G SG SG值。

我们考虑 D P DP DP，设 s g [ x ] [ y ] sg[x][y] sg[x][y]表示当前棋子一开始在 ( x , y ) (x,y) (x,y)时的 S G SG SG值，然后从下往上处理。我们分两种情况考虑。

当前行有至少一个包含障碍的格子

在这种情况下，每行都被障碍分成若干段。那么，对于走到这一行的棋子，它的状态只会有三种：

• 刚从上面走下来，此时可以往左右两边走
• 从右边走过来，只能往左边走
• 从左边走过来，只能往右边走

假设当前行为第 t t t行，设 f [ 0 / 1 ] [ i ] f[0/1][i] f[0/1][i]表示当前是从左边或右边走过来，走到当前行的位置 i i i时的 S G SG SG值。我们分别处理从左往右走的 f f f值和从右往左走的 f f f值，对于每个位置 i i i，我们用 s g [ t + 1 ] [ i ] sg[t+1][i] sg[t+1][i]， f [ 0 ] [ i − 1 ] f[0][i-1] f[0][i−1]， f [ 1 ] [ i + 1 ] f[1][i+1] f[1][i+1]三个数求 m e x mex mex来更新 s g [ t ] [ i ] sg[t][i] sg[t][i]。

当前行没有包含障碍的格子

在这种情况下，当一个棋子从上一行来到这一行时，假设来到了 ( x , y ) (x,y) (x,y)，若选择往左走，来到 ( x , y − 1 ) (x,y-1) (x,y−1)，则 ( x , y ) (x,y) (x,y)就相当于变成了一个包含障碍的格子，这就转化为了包含障碍格子的情况。

我们考虑如何计算 S G SG SG值。当从 ( x , y ) (x,y) (x,y)走到 ( x , y − 1 ) (x,y-1) (x,y−1)时，只能往左或往下走，也就是说我们要用 ( x + 1 , y − 1 ) (x+1,y-1) (x+1,y−1)的 S G SG SG值和 ( x , y − 2 ) (x,y-2) (x,y−2)的 S G SG SG值来更新 ( x , y − 1 ) (x,y-1) (x,y−1)的 S G SG SG值。而 ( x + 1 , y − 1 ) (x+1,y-1) (x+1,y−1)的 S G SG SG值在之前已经求出，所以我们需要求的就是 ( x , y − 2 ) (x,y-2) (x,y−2)的 S G SG SG值。以此类推，我们一路向左推，最终要求的就是 ( x , y + 1 ) (x,y+1) (x,y+1)的 S G SG SG值。此时只能往下走，可以直接求出 S G SG SG值，再一路回推。

这样的话，求每个位置的 S G SG SG值的时间复杂度都是 O ( m ) O(m) O(m)的。我们考虑优化。

我们可以注意到，每个位置的 S G SG SG值是由三个数求 m e x mex mex得来，也就是说 S G SG SG值只会取 0 , 1 , 2 , 3 0,1,2,3 0,1,2,3四个数。

假设当前行为第 t t t行，设 g [ 0 / 1 / 2 / 3 ] [ j ] [ i ] g[0/1/2/3][j][i] g[0/1/2/3][j][i]的意义如下：

• g [ 0 ] [ j ] [ i ] g[0][j][i] g[0][j][i]表示当位置 ( t , 1 ) (t,1) (t,1)的 S G SG SG值为 j j j时，一路往右回推到 i i i（也就是从棋子从 i i i往左走到 1 1 1），此时位置 ( t , i ) (t,i) (t,i)的 S G SG SG值
• g [ 1 ] [ j ] [ i ] g[1][j][i] g[1][j][i]表示当位置 ( t , m ) (t,m) (t,m)的 S G SG SG值为 j j j时，一路往左回推到 i i i（也就是从棋子从 i i i往右走到 m m m），此时位置 ( t , i ) (t,i) (t,i)的 S G SG SG值
• g [ 2 ] [ j ] [ i ] g[2][j][i] g[2][j][i]表示位置 ( t , i ) (t,i) (t,i)的 S G SG SG为 j j j时， i i i是从 ( t , 1 ) (t,1) (t,1)向左回推过来的，此时位置 ( t , 1 ) (t,1) (t,1)的值
• g [ 3 ] [ j ] [ i ] g[3][j][i] g[3][j][i]表示位置 ( t , i ) (t,i) (t,i)的 S G SG SG为 j j j时， i i i是从 ( t , m ) (t,m) (t,m)向右回推过来的，此时位置 ( t , m ) (t,m) (t,m)的值

那么，我们分别将 g [ 0 ] [ j ] [ i ] g[0][j][i] g[0][j][i]， g [ 1 ] [ j ] [ i ] g[1][j][i] g[1][j][i]， g [ 2 ] [ j ] [ i ] g[2][j][i] g[2][j][i]， g [ 3 ] [ j ] [ i ] g[3][j][i] g[3][j][i]求出来，然后用他们来 O ( 1 ) O(1) O(1)更新每个点的 S G SG SG值即可。

可以参考代码方便理解。

两种情况处理每行的时间复杂度都为 O ( m ) O(m) O(m)，所以总时间复杂度为 O ( n m ) O(nm) O(nm)。

code

#include<bits/stdc++.h>
using namespace std;
const int N=1000;
int T,n,m,ans,sg[N+5][N+5],f[2][N+5],g[4][4][N+5];
char s[2*N+5][2*N+5];
int mex(int v1,int v2,int v3){for(int i=0;i<=3;i++){if(i!=v1&&i!=v2&&i!=v3) return i;}
}
int gt(int i){return (i-1)%m+1;
}
void solve1(int t){memset(f,0,sizeof(f));for(int i=1;i<=m;i++) s[t][i+m]=s[t][i];int fst=1;while(s[t][fst]!='#') ++fst;for(int l=fst,r;l<m+fst;l=r){r=l+1;while(r<m+fst&&s[t][r]!='#') ++r;if(r==l+1) continue;f[0][l+1]=mex(sg[t+1][gt(l+1)],-1,-1);for(int i=l+2;i<r;i++) f[0][i]=mex(f[0][i-1],sg[t+1][gt(i)],-1);f[1][r-1]=mex(sg[t+1][gt(r-1)],-1,-1);for(int i=r-2;i>l;i--) f[1][i]=mex(f[1][i+1],sg[t+1][gt(i)],-1);for(int i=l+1;i<=r-1;i++){int v1=-1,v2=-1;if(i>l+1) v1=f[0][i-1];if(i<r-1) v2=f[1][i+1];sg[t][gt(i)]=mex(v1,v2,sg[t+1][gt(i)]);}}
}
void solve2(int t){if(m==1){sg[t][1]=mex(sg[t+1][1],-1,-1);return;}memset(g,0,sizeof(g));for(int j=0;j<=3;j++){g[0][j][1]=j;g[1][j][m]=j;g[2][j][1]=j;g[3][j][m]=j;}for(int i=2;i<=m;i++)for(int j=0;j<=3;j++) g[0][j][i]=mex(g[0][j][i-1],sg[t+1][i],-1);for(int i=m-1;i>=1;i--)for(int j=0;j<=3;j++) g[1][j][i]=mex(g[1][j][i+1],sg[t+1][i],-1);for(int i=2;i<=m;i++)for(int j=0;j<=3;j++) g[2][j][i]=g[2][mex(j,sg[t+1][i-1],-1)][i-1];for(int i=m-1;i>=1;i--)for(int j=0;j<=3;j++) g[3][j][i]=g[3][mex(j,sg[t+1][i+1],-1)][i+1];for(int i=1;i<=m;i++){int v1=-1,v2=-1,now;int nxt=gt(i+1),ed=g[3][mex(sg[t+1][nxt],-1,-1)][nxt];if(i==1) v1=ed;else{if(i==m) now=mex(sg[t+1][1],-1,-1);else now=mex(sg[t+1][1],ed,-1);v1=g[0][now][i-1];}int lst=gt(i-1+m),bg=g[2][mex(sg[t+1][lst],-1,-1)][lst];if(i==m) v2=bg;else{if(i==1) now=mex(sg[t+1][m],-1,-1);else now=mex(sg[t+1][m],bg,-1);v2=g[1][now][i+1];}sg[t][i]=mex(v1,v2,sg[t+1][i]);}
}
int main()
{freopen("game.in","r",stdin);freopen("game.out","w",stdout);scanf("%d",&T);while(T--){scanf("%d%d",&n,&m);memset(sg,-1,sizeof(sg));for(int i=1;i<=n;i++) scanf("%s",s[i]+1);for(int i=n;i>=1;i--){int fl=0;for(int j=1;j<=m;j++){if(s[i][j]=='#'){fl=1;break;}}if(fl) solve1(i);else solve2(i);}ans=0;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(s[i][j]=='B') ans^=sg[i][j];}}if(ans) printf("A\n");else printf("B\n");}return 0;
}