Description
给你一个正整数 $n$ 和一个 $n \times n$ 的矩阵 $a$，有两个人轮流对这个矩阵进行操作，每次可以删掉最后一行或最后一列，但必须要保证所删的行或列的和是偶数。当一个人无法操作时这个人就输了。
现在请你求出在双方都使用最优策略的情况下，先手是否有必胜策略，有则输出 $W$ ，否则输出 $L$ 。
$1 \leq n \leq 1000,1 \leq T \leq 5$ 。
$\text{保证每一行或每一列的和不会超过};2 \times 10^9$ 。
Solution
考虑使用 DP 来解题。
设 $f[i][j]=0/1$ 表示当剩下 $i$ 行 $j$ 列时先手 必败/必胜 。
为了方便，然后显然有转移方程：
$f[i][j]=f[i][j]|(!f[i-1][j])\quad\quad\quad((\sum_{k=1}^{j}a_{i,k});\mod;2=0)$
$f[i][j]=f[i][j]|(!f[i][j-1])\quad\quad\quad((\sum_{k=1}^{i}a_{k,j});\mod;2=0)$
。
求和那里可以初始化一下。
然后这道题目就做完了，时间复杂度 $O(Tn^2)$ 。
考虑使用 DFS 来解题。
先将整个图的横向和纵向做一遍前缀和，用 DFS 做一遍游戏过程即可。
时间复杂度 $O(Tn^2)$ ,具体的细节见 代码 部分。
然后这道题目就做完了。
Code
1 | #include <cstdio>
|
2 | #include <cstring>
|
3 | int f[1001][1001],a[1001][1001];
|
4 | int sumx[1001][1001],sumy[1001][1001];
|
5 | int main()
|
6 | {
|
7 | int T=0;
|
8 | scanf("%d",&T);
|
9 | while(T--)
|
10 | {
|
11 | int n=0;
|
12 | scanf("%d",&n);
|
13 | for(int i=1;i<=n;i++)
|
14 | {
|
15 | for(int j=1;j<=n;j++)
|
16 | {
|
17 | int x=0;
|
18 | scanf("%d",&x);
|
19 | a[i][j]=x;
|
20 | sumx[i][j]=sumx[i][j-1]+x;
|
21 | sumy[j][i]=sumy[j][i-1]+x;
|
22 | }
|
23 | }
|
24 | memset(f,0,sizeof(f));
|
25 | for(int i=1;i<=n;i++)
|
26 | {
|
27 | for(int j=1;j<=n;j++)
|
28 | {
|
29 | if( sumx[i][j]%2==0 )
|
30 | {
|
31 | f[i][j]= f[i][j] | (!f[i-1][j]) ;
|
32 | }
|
33 | if( sumy[j][i]%2==0 )
|
34 | {
|
35 | f[i][j]= f[i][j] | (!f[i][j-1]) ;
|
36 | }
|
37 | }
|
38 | }
|
39 | printf("%c\n",f[n][n]==1?'W':'L');
|
40 | }
|
41 | return 0;
|
42 | }
|
1 | #include<cstdio>
|
2 | int t,n,a[1001][1001],sum[1001][1001][2];
|
3 | inline bool dfs(int nx,int x,int y)
|
4 | {
|
5 | if(nx==1)
|
6 | {
|
7 | if(x==0||y==0)return false;
|
8 | if(!sum[x][y][1])
|
9 | if(dfs(2,x-1,y)==true)return true;
|
10 | if(!sum[x][y][0])
|
11 | if(dfs(2,x,y-1)==true)return true;
|
12 | return false;
|
13 | }
|
14 | else
|
15 | {
|
16 | if(x==0||y==0)return true;
|
17 | if(!sum[x][y][1])
|
18 | if(dfs(1,x-1,y)==false)return false;
|
19 | if(!sum[x][y][0])
|
20 | if(dfs(1,x,y-1)==false)return false;
|
21 | return true;
|
22 | }
|
23 | }
|
24 | int main()
|
25 | {
|
26 | scanf("%d",&t);
|
27 | while(t--)
|
28 | {
|
29 | scanf("%d",&n);
|
30 | for(int i=1;i<=n;i++)
|
31 | {
|
32 | for(int j=1;j<=n;j++)
|
33 | {
|
34 | scanf("%d",&a[i][j]);
|
35 | sum[i][j][1]=(sum[i][j-1][1]+a[i][j])%2;
|
36 | sum[i][j][0]=(sum[i-1][j][0]+a[i][j])%2;
|
37 | }
|
38 | }
|
39 | if(dfs(1,n,n)==true)
|
40 | {
|
41 | printf("W\n");
|
42 | }
|
43 | else
|
44 | {
|
45 | printf("L\n");
|
46 | }
|
47 | }
|
48 | return 0;
|
49 | }
|
