题解：P13114 [GCJ 2019 #1C] Bacterial Tactics

· · 题解

P13114 [GCJ 2019 #1C] Bacterial Tactics 题解

前言

神仙题目一道，时间限制 30s，内存限制 1G，数据范围 N,M \le 15 , T \le 100，结果正解时间 O(T \times n^5)，空间 O(N^4)，完全没有必要（然后我交了四发全 RE 是何意味）。

题意

两个人摆菌落，每次可以摆 H 型的或 V 型的，H 型的摆了之后会向左右扩散，V 型的摆了之后会向上下扩散，直到撞到边缘或其他菌落停止，但如果在扩散的过程中遇到了放射性物质，摆放该菌落的人就输了，或者如果没有地方可以摆放菌落，那么这个无处可摆的人就输了。两个人智商都是正无穷大，求先手是否必胜，如果必胜，求有多少种必胜开局。

思路

这是博弈论中的公平组合游戏，所以想到 SG 秒了。

SG 定理

多个独立子游戏的 SG 值等于各子游戏 SG 值的异或。

状态设计

注意到每次摆放菌落，都相当于是将矩阵分为两个子矩阵，所以我们用 DP，考虑设 f_{x,y,a,b} 为以 (x,y) 为左上角，(a,b) 为右下角的子矩阵 SG 函数值。

预处理

为了方便判断每行的空格数，我们设两个数组 h 和 v，h_{x,y} 表示从 (x,y) 往左的连续空格数，v_{x,y} 表示从 (x,y) 往上的连续空格数，所以我们得到：

  1. 判断第 i 行从 j 到 y 是否全为空格：h_{i,y} - h_{i,j-1} = y - j + 1。
  2. 判断第 j 列从 i 到 x 是否全为空格：v_{x,j} - v_{i-1,j} = x - i + 1。

状态转移

对于当前矩形 (i,j) 到 (x,y)：

枚举 H 型菌落

选择第 k 行（i \le k \le x），要求该行从 j 到 y 全是空格。

菌落把矩形分成上下两部分：

SG 值为：

sg_1 = f_{i,j,k - 1,y} \oplus f_{k + 1,j,x,y}

枚举 V 型菌落

选择第 k 列 (j \le k \le y)，要求该列从 i 到 x 全是空格。

菌落把矩形分成左右两部分：

SG 值为：

sg_2 = f_{i,j,x,k - 1} \oplus f_{i,k + 1,x,y}

计算总 SG 值

f_{i,j,x,y} = \operatorname{mex}\{sg_1,sg_2,\ldots\}

统计答案

先手必胜的开局，肯定是操作完之后先手必败的情况（这里指的先手必败，是指先手操作后的新的先手，也就是后手，换言之，就是分成的子矩阵的 SG 值的异或为 0），所以我们枚举整个棋盘的第一手：

复杂度分析

状态数 O(n^4)，每个状态转移 O(n)，总复杂度 O(T \times n^5)，最大也才 10^8，然后注意到时间限制 30s。 。 。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int t,n,m,f[25][25][25][25],s[305],ans,h[25][16],v[25][25];
char c[25][25];
//f[i][j][x][y]: 左上角(i,j)到右下角(x,y)这个子矩形的SG值
//h[i][j]:从(i,j)向左连续空格的个数
//v[i][j]:从(i,j)向上连续空格的个数
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>t;
    for(int Case=1;Case<=t;Case++){
        cin>>n>>m;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                cin>>c[i][j];
                if(c[i][j]=='#'){                       //放射性格子，连续长度归零
                    h[i][j]=0;
                    v[i][j]=0;
                }
                else{                                   //空格子，长度加一
                    h[i][j]=h[i-1][j]+1;
                    v[i][j]=v[i][j-1]+1;
                }
            }
        }
        memset(f,0,sizeof f);
        ans=0;
        for(int lenx=1;lenx<=n;lenx++){                 //子矩形的长度
            for(int leny=1;leny<=m;leny++){             //子矩形的宽度
                for(int i=1;i+lenx-1<=n;i++){           //子矩形左上角行号
                    for(int j=1;j+leny-1<=m;j++){       //子矩形左上角列号
                        int x=i+lenx-1,y=j+leny-1;      //计算右下角坐标
                        memset(s,0,sizeof s);           //清空mex标记数组
                        for(int k=i;k<=x;k++){          //在当前子矩形中放置H型菌落
                            if(v[k][y]-v[k][j-1]==leny){//这一段全是空格
                                s[f[i][j][k-1][y]^f[k+1][j][x][y]]=1;
                            }
                        }
                        for(int k=j;k<=y;k++){
                            if(h[x][k]-h[i-1][k]==lenx){//这一段全是空格
                                s[f[i][j][x][k-1]^f[i][k+1][x][y]]=1;
                            }
                        }
                        int mex=0;
                        while(s[mex]){
                            mex++;
                        }
                        f[i][j][x][y]=mex;
                    }
                }
            }
        }
        for(int i=1;i<=n;i++){
            if(v[i][m]==m){                             //第i行全部是空格
                if(!(f[1][1][i-1][m]^f[i+1][1][n][m])){
                    ans+=m;
                }
            }
        }
        for(int j=1;j<=m;j++){
            if(h[n][j]==n){                             //第j列全部是空格
                if(!(f[1][1][n][j-1]^f[1][j+1][n][m])){
                    ans+=n;
                }
            }
        }
        cout<<"Case #"<<Case<<": "<<ans<<'\n';
    }
    return 0;
}

注意事项

  1. 多测不清空，爆零两行泪。
  2. 不要使用 while(t--)，因为要输出测试点编号。
  3. 数组千万不能太小，因为有加一。
  4. 不要把 n 和 m 弄反。
  5. 要注意边界问题，不要多加或者少加。

以上注意事项均经过验证。