免费家政网站建设,张家界建设网站制作,建设一个网站需要条件,百度发广告需要多少钱题目大意
有一个 n m n\times m nm的网格图#xff0c;开始时有三种格子#xff0c;分别为障碍#xff0c;棋子和空格。
小 A A A和小 B B B在这个网格图上玩游戏#xff0c;双方轮流行动#xff0c;小 A A A先行动。每次行动中#xff0c;当前玩家选择一枚棋子移动开始时有三种格子分别为障碍棋子和空格。
小 A A A和小 B B B在这个网格图上玩游戏双方轮流行动小 A A A先行动。每次行动中当前玩家选择一枚棋子移动设棋子所在的格子为 ( r , c ) (r,c) (r,c)则移动规则如下
可将格子移到 ( r 1 , c ) (r1,c) (r1,c)如果 r 1 ≤ n r1\leq n r1≤n、 ( r , c − 1 ) (r,c-1) (r,c−1)如果 c 1 c1 c1、 ( r , c 1 ) (r,c1) (r,c1)如果 c m cm cm。特殊地可以从 ( 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[t1][i] sg[t1][i] f [ 0 ] [ i − 1 ] f[0][i-1] f[0][i−1] f [ 1 ] [ i 1 ] f[1][i1] f[1][i1]三个数求 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 ) (x1,y-1) (x1,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 ) (x1,y-1) (x1,y−1)的 S G SG SG值在之前已经求出所以我们需要求的就是 ( x , y − 2 ) (x,y-2) (x,y−2)的 S G SG SG值。以此类推我们一路向左推最终要求的就是 ( x , y 1 ) (x,y1) (x,y1)的 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
#includebits/stdc.h
using namespace std;
const int N1000;
int T,n,m,ans,sg[N5][N5],f[2][N5],g[4][4][N5];
char s[2*N5][2*N5];
int mex(int v1,int v2,int v3){for(int i0;i3;i){if(i!v1i!v2i!v3) return i;}
}
int gt(int i){return (i-1)%m1;
}
void solve1(int t){memset(f,0,sizeof(f));for(int i1;im;i) s[t][im]s[t][i];int fst1;while(s[t][fst]!#) fst;for(int lfst,r;lmfst;lr){rl1;while(rmfsts[t][r]!#) r;if(rl1) continue;f[0][l1]mex(sg[t1][gt(l1)],-1,-1);for(int il2;ir;i) f[0][i]mex(f[0][i-1],sg[t1][gt(i)],-1);f[1][r-1]mex(sg[t1][gt(r-1)],-1,-1);for(int ir-2;il;i--) f[1][i]mex(f[1][i1],sg[t1][gt(i)],-1);for(int il1;ir-1;i){int v1-1,v2-1;if(il1) v1f[0][i-1];if(ir-1) v2f[1][i1];sg[t][gt(i)]mex(v1,v2,sg[t1][gt(i)]);}}
}
void solve2(int t){if(m1){sg[t][1]mex(sg[t1][1],-1,-1);return;}memset(g,0,sizeof(g));for(int j0;j3;j){g[0][j][1]j;g[1][j][m]j;g[2][j][1]j;g[3][j][m]j;}for(int i2;im;i)for(int j0;j3;j) g[0][j][i]mex(g[0][j][i-1],sg[t1][i],-1);for(int im-1;i1;i--)for(int j0;j3;j) g[1][j][i]mex(g[1][j][i1],sg[t1][i],-1);for(int i2;im;i)for(int j0;j3;j) g[2][j][i]g[2][mex(j,sg[t1][i-1],-1)][i-1];for(int im-1;i1;i--)for(int j0;j3;j) g[3][j][i]g[3][mex(j,sg[t1][i1],-1)][i1];for(int i1;im;i){int v1-1,v2-1,now;int nxtgt(i1),edg[3][mex(sg[t1][nxt],-1,-1)][nxt];if(i1) v1ed;else{if(im) nowmex(sg[t1][1],-1,-1);else nowmex(sg[t1][1],ed,-1);v1g[0][now][i-1];}int lstgt(i-1m),bgg[2][mex(sg[t1][lst],-1,-1)][lst];if(im) v2bg;else{if(i1) nowmex(sg[t1][m],-1,-1);else nowmex(sg[t1][m],bg,-1);v2g[1][now][i1];}sg[t][i]mex(v1,v2,sg[t1][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 i1;in;i) scanf(%s,s[i]1);for(int in;i1;i--){int fl0;for(int j1;jm;j){if(s[i][j]#){fl1;break;}}if(fl) solve1(i);else solve2(i);}ans0;for(int i1;in;i){for(int j1;jm;j){if(s[i][j]B) ans^sg[i][j];}}if(ans) printf(A\n);else printf(B\n);}return 0;
}
