「题解」游戏 game

题目链接:GMOJ 2642

题目

题目描述

Alice 和 Bob 在玩一个游戏,游戏是在一个 $N \times N$ 的矩阵上进行的,每个格子上都有一个正整数。当轮到 Alice/Bob 时,他/她可以选择最后一列或最后一行,并将其删除,但必须保证选择的这一行或这一列所有数的和为偶数。如果他/她不能删除最后一行或最后一列,那么他/她就输了。两人都用最优策略来玩游戏,Alice 先手,问 Alice 是否可以必胜?

输入格式

第一行:$T$,表示数据组数。
对于每组数据的第一行:$N$。
接下来 $N$ 行,每行 $N$ 个数,描述这个矩阵。

输出格式

如果 Alice 必胜输出 W,否则输出 L

样例输入输出

#1

  • Input:
2
2
2 4
6 8
3
5 4 2
1 5 9
7 3 8
  • Output:
L
W

数据范围

$100\%$ 数据满足 $1\leq N\leq 1000$,保证每一行或每一列的和不会超过 $2\times 10^9,1\leq T\leq 5$。
$30\%$ 数据满足 $1\leq N\leq 5$。
$50\%$ 数据满足 $1\leq N\leq 100$。
$70\%$ 数据满足 $1\leq N\leq 500$。

时空限制

$2000\text{ms}/256\text{MiB}$。

题解

我们为了方便,就不说部分分解法了,直接讲正解。

思路

我们设 $f _ {i,j}$ 表示矩阵还剩 $i$ 行 $j$ 列时候的先手必胜必败状态,其中 $f _ {i,j}=1$ 为先手必胜,$f _ {i,j}=0$ 为先手必败。显然,我们可以得出 $f _ {0,0}=0$,此时先手必败。

那么我们再深入一些。

记原数组为 $a _ {i,j}$,定义前缀和数组,设 $\text{sum} _ {i,j}=\sum^i _ {p=1}\sum^j _ {q=1} a _ {p,q}$。

那么我们就可以以 $\Theta(n^2)$ 的时间复杂度,再以 $\Theta(1)$ 的时间复杂度求出任何一行或者任何一列和的值,继而得出它的奇偶性。
更进一步地,我们可以让 $\text{sum} _ {i,j}$ 直接表示前缀和的奇偶性,那么根据整数运算法则,我们可以得出:

$$\text{sum} _ {i,j}=\text{sum} _ {i-1,j}\oplus\text{sum} _ {i,j-1}\oplus\text{sum} _ {i-1,j-1}\oplus a _ {i,j}$$

现在让我们研究一下 $f _ {i,j}$ 的转移。
经过研究可以发现:

f[i][j]=(f[i-1][j]==0&&(sum[i][j]^sum[i-1][j])==0)||(f[i][j-1]==0&&(sum[i][j]^sum[i][j-1])==0);

结论很简单,程序也比较短。

代码

根据结论写出代码,渐进时间复杂度为 $\Theta(n^2)$。

#include<cstdio>
#include<cstring>
const int MAXN=1000+5;
int T,n;
int sum[MAXN][MAXN];
int f[MAXN][MAXN];
int main(void){
    register int i,j;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        for(i=1;i<=n;++i)
            for(j=1;j<=n;++j){
                static int a;
                scanf("%d",&a);
                sum[i][j]=sum[i][j-1]^sum[i-1][j]^sum[i-1][j-1]^(a&1);
            }
        for(i=1;i<=n;++i)
            for(j=1;j<=n;++j)
                f[i][j]=(f[i-1][j]==0&&(sum[i][j]^sum[i-1][j])==0)||(f[i][j-1]==0&&(sum[i][j]^sum[i][j-1])==0);
        puts(f[n][n]?"W":"L");
    }
    return 0;
}