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

Loyal_Soldier · 2026-07-21 15:15:47 · 题解

思路

看到博弈论，而且是公平组合游戏，考虑 \operatorname{SG} 函数

我们注意到，一次合法的放置菌落，会把整个矩阵分成两个矩阵，分成了两个子问题。

设计 dp_{x_1, y_1, x_2, y_2} 表示 x\in[x_1, x_2], y\in [y_1, y_2] 的子矩阵的 \operatorname{SG} 函数值。

考虑转移：

其中 A, B, C 是矩阵，C 可以通过一次合法的放置菌落分成 A, B。

但是判断合法是 O(n)，直接做是 O(n^6) 的（实际上因为这题神秘的时限也可以过），多维护每个格子向左和向上空格子的数量，就可以 O(n^5) 做。

对于答案，枚举分矩阵的第一步，如果合法且子矩阵 \operatorname{SG} 值的异或和是 0，就算进答案，贡献为长度，因为如果是必胜当且仅当后继是必败的。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 50;
int n, m;
int cnt[MAXN];
int upb[MAXN][MAXN], lft[MAXN][MAXN];
string s[MAXN];
int dp[MAXN][MAXN][MAXN][MAXN]; 
void solve(int T) {
    memset(dp, 0, sizeof(dp));
    memset(cnt, 0, sizeof(cnt));
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
        s[i] = ' ' + s[i];
    }
    //预处理 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            upb[i][j] = (s[i][j] == '.') * (upb[i - 1][j] + 1);
            lft[i][j] = (s[i][j] == '.') * (lft[i][j - 1] + 1);
        }
    }
    for (int x1 = n; x1 >= 1; x1--) {
        for (int y1 = m; y1 >= 1; y1--) {
            for (int x2 = x1; x2 <= n; x2++) {
                for (int y2 = y1; y2 <= m; y2++) {
                    memset(cnt, 0, sizeof(cnt));
                    //统计合法子矩阵 dp 的异或和 
                    for (int i = x1; i <= x2; i++)
                        if (lft[i][y2] >= y2 - y1 + 1) cnt[dp[x1][y1][i - 1][y2] ^ dp[i + 1][y1][x2][y2]]++;
                    for (int j = y1; j <= y2; j++)
                        if (upb[x2][j] >= x2 - x1 + 1) cnt[dp[x1][y1][x2][j - 1] ^ dp[x1][j + 1][x2][y2]]++;
                    //mex
                    while (cnt[dp[x1][y1][x2][y2]]) dp[x1][y1][x2][y2]++; 
                }
            }
        }
    }
    int ans = 0;
    //统计答案 
    for (int i = 1; i <= m; i++)
        if (upb[n][i] >= n && (dp[1][1][n][i - 1] ^ dp[1][i + 1][n][m]) == 0) ans += n;
    for (int i = 1; i <= n; i++)
        if (lft[i][m] >= m && (dp[1][1][i - 1][m] ^ dp[i + 1][1][n][m]) == 0) ans += m;
    cout << "Case #" << T << ": " << ans << '\n';
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    for (int i = 1; i <= T; i++) solve(i);
    return 0;
}