E2. 子矩阵游戏（困难版）详细题解

问题重述

给定一个长度为 $l$ 的数组 $a$ 和一个 $n \times m$ 的矩阵 $b$。两人轮流在矩阵中按顺序寻找数组 $a$ 中的元素，Tsovak 先手。当前玩家选择格子 $(r,c)$ 后，下一个玩家必须在子矩阵 $(r+1,c+1)$ 到 $(n,m)$ 中寻找下一个元素。无法找到所需元素或子矩阵为空或数组已结束时，当前玩家输。双方最优，判断胜者。

与简单版的区别：约束更大（$l,n,m \le 1500$，$n \cdot m$ 总和 $\le 3 \times 10^6$），需要更高效的算法。

关键观察

观察 1：重复数字的处理（与简单版相同）

当数组 $a$ 中某个数字出现多次时，第一次出现该数字的玩家会选择最优策略。

重要结论：当玩家遇到某个数字 $x$ 在数组 $a$ 中第二次出现时，他必然输掉游戏。

证明：与简单版相同。

结论：我们可以将数组 $a$ 截断到每个数字最多出现一次。由于 $l \le 1500$，截断后 $l$ 可能仍然很大，但每个数字只出现一次。

观察 2：状态表示的优化

在简单版中，我们使用 $dp[k][i][j]$ 表示状态，空间复杂度为 $O(l \cdot n \cdot m)$，在困难版中不可行（$l$ 和 $n \cdot m$ 都很大）。

优化思路：我们不需要存储所有 $k$ 的完整信息。对于每个格子 $(i,j)$，我们只需要知道：

• 最小的偶数索引 $k$，使得从该状态开始当前玩家（轮到 Tsovak 或 Narek）能赢
• 最小的奇数索引 $k$，使得从该状态开始当前玩家能赢

观察 3：新状态定义

定义：

• $dp0[i][j]$：从格子 $(i,j)$ 开始，当前轮到偶数索引（Tsovak 的回合，即 $k$ 为奇数？注意索引从 1 开始）时，能赢的最小 $k$ 值
• $dp1[i][j]$：从格子 $(i,j)$ 开始，当前轮到奇数索引（Narek 的回合）时，能赢的最小 $k$ 值

但标程中的定义略有不同。根据代码分析：

• $dp0[i][j]$：从格子 $(i,j)$ 开始，当前轮到偶数步（即 $a_k$ 中 $k$ 为偶数？需要仔细理解）
• 实际上，标程中 $dp0$ 和 $dp1$ 存储的是最小的索引 $k$，使得从该状态开始当前玩家能赢
• 其中 $dp0$ 对应 $k$ 为偶数的情况，$dp1$ 对应 $k$ 为奇数的情况

更准确的理解：

• 当需要寻找 $a_k$ 且 $k$ 为奇数时，轮到 Tsovak
• 当需要寻找 $a_k$ 且 $k$ 为偶数时，轮到 Narek
• $dp0[i][j]$ 表示：在格子 $(i,j)$，如果当前需要寻找的 $a_k$ 中 $k$ 为偶数，能获胜的最小 $k$
• $dp1[i][j]$ 表示：在格子 $(i,j)$，如果当前需要寻找的 $a_k$ 中 $k$ 为奇数，能获胜的最小 $k$

状态转移

对于格子 $(i,j)$，当前玩家可以选择：

选择 1：跳过当前格子

• 向右移动：如果 $j < m$，可以转移到 $(i, j+1)$
• 向下移动：如果 $i < n$，可以转移到 $(i+1, j)$

因此：

$$dp0[i][j] = \min(dp0[i+1][j], dp0[i][j+1])$$ $$dp1[i][j] = \min(dp1[i+1][j], dp1[i][j+1])$$

选择 2：选择当前格子

只有当 $b[i][j]$ 在数组 $a$ 中出现时，才能选择。设 $ind = index(a, b[i][j])$，即 $b[i][j]$ 在 $a$ 中的位置（$1 \le ind \le l$）。

如果选择当前格子：

• 当前玩家选择了 $a_{ind}$
• 下一个玩家需要在子矩阵 $(i+1, j+1)$ 中寻找 $a_{ind+1}$
• 当前玩家获胜的条件是：下一个玩家在子矩阵 $(i+1, j+1)$ 中无法获胜

关键判断：

• 如果 $ind$ 是偶数，当前轮到 Narek（因为偶数索引对应 Narek？需要确认）
• 实际上，根据标程：
  • 当 $ind$ 为偶数时，更新 $dp0[i][j]$
  • 当 $ind$ 为奇数时，更新 $dp1[i][j]$

选择当前格子后，当前玩家获胜的条件是：

• 下一个玩家在 $(i+1, j+1)$ 中，从 $ind+1$ 开始无法获胜
• 即：$dp?[i+1][j+1] > ind+1$（其中 $?$ 取决于下一个玩家的奇偶性）

具体来说：

• 如果 $ind$ 是偶数，当前玩家是 Narek，下一个玩家是 Tsovak（对应 $ind+1$ 为奇数）

• 需要 $dp1[i+1][j+1] > ind+1$，表示 Tsovak 无法从 $ind+1$ 获胜

• 此时 $dp0[i][j] = \min(dp0[i][j], ind)$

• 如果 $ind$ 是奇数，当前玩家是 Tsovak，下一个玩家是 Narek（对应 $ind+1$ 为偶数）

• 需要 $dp0[i+1][j+1] > ind+1$，表示 Narek 无法从 $ind+1$ 获胜

• 此时 $dp1[i][j] = \min(dp1[i][j], ind)$

标程中的条件是 ind + 3 <= dp1[i+1][j+1]，这是因为：

• 如果 $dp1[i+1][j+1] \ge ind+3$，说明从 $ind+1$ 开始无法获胜（因为最小获胜索引更大）
• 等价于 $dp1[i+1][j+1] > ind+1$

初始化

• $dp0[i][j] = dp1[i][j] = \infty$（用一个很大的数，如 $10^9$）
• 边界外（$i = n+1$ 或 $j = m+1$）保持为 $\infty$

最终答案

• 从 $(1,1)$ 开始，轮到 Tsovak（对应 $k=1$，奇数）
• 如果 $dp1[1][1] = 1$，表示 Tsovak 能从 $k=1$ 获胜
• 输出 "T" 否则 "N"

算法步骤

1. 预处理数组 $a$：

   • 使用数组 $ind$ 记录每个数字在 $a$ 中的位置
   • 遇到重复数字时截断 $l$（每个数字只保留第一次出现）

2. 动态规划计算：

   • 从 $i = n$ 到 $1$，$j = m$ 到 $1$ 逆序循环
   • 先通过移动更新 $dp0[i][j]$ 和 $dp1[i][j]$
   • 如果 $b[i][j]$ 在 $a$ 中，根据奇偶性尝试通过选择更新

3. 判断结果：

   • 若 $dp1[1][1] = 1$，输出 "T"
   • 否则输出 "N"

时间复杂度

• 预处理数组 $a$：$O(l)$
• 动态规划：$O(n \cdot m)$
• 所有测试用例的 $n \cdot m$ 总和 $\le 3 \times 10^6$，总时间复杂度可行

完整代码

#include <bits/stdc++.h>
using namespace std;

const int L = 1505, N = 1505, M = 1505;
int a[L], b[N][M];
int l, n, m;

int ind[N * M];  // 记录每个数字在 a 中的位置

int dp0[N][M], dp1[N][M];  // dp0: 偶数索引, dp1: 奇数索引

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;

    while (t--) {
        cin >> l >> n >> m;

        // 读入数组 a
        for (int i = 1; i <= l; i++) {
            cin >> a[i];
        }

        // 预处理：截断数组 a，使每个数字最多出现一次
        for (int i = 1; i <= l; i++) {
            if (ind[a[i]]) {  // 该数字已经出现过
                l = i - 1;    // 截断到当前位置之前
                break;
            }
            ind[a[i]] = i;    // 记录第一次出现的位置
        }

        // 读入矩阵 b
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                cin >> b[i][j];
            }
        }

        // 初始化 dp 数组为无穷大
        const int INF = 1e9;
        for (int i = 0; i <= n + 1; i++) {
            for (int j = 0; j <= m + 1; j++) {
                dp0[i][j] = dp1[i][j] = INF;
            }
        }

        // 动态规划：从右下角往左上角计算
        for (int i = n; i >= 1; i--) {
            for (int j = m; j >= 1; j--) {
                // 通过移动（跳过当前格子）更新
                dp0[i][j] = min(dp0[i + 1][j], dp0[i][j + 1]);
                dp1[i][j] = min(dp1[i + 1][j], dp1[i][j + 1]);

                // 检查是否可以选当前格子
                int pos = ind[b[i][j]];  // b[i][j] 在 a 中的位置
                if (!pos) continue;       // 不在 a 中，不能选

                // 根据奇偶性尝试更新
                if (pos % 2 == 0) {
                    // pos 为偶数，当前轮到 Narek，选择后下一个玩家从 pos+1 开始（奇数）
                    // 如果下一个玩家无法从 pos+1 获胜，则当前玩家获胜
                    if (pos + 3 <= dp1[i + 1][j + 1]) {
                        dp0[i][j] = min(dp0[i][j], pos);
                    }
                } else {
                    // pos 为奇数，当前轮到 Tsovak，选择后下一个玩家从 pos+1 开始（偶数）
                    // 如果下一个玩家无法从 pos+1 获胜，则当前玩家获胜
                    if (pos + 3 <= dp0[i + 1][j + 1]) {
                        dp1[i][j] = min(dp1[i][j], pos);
                    }
                }
            }
        }

        // 判断结果：从 (1,1) 开始，轮到 Tsovak（奇数索引）
        if (dp1[1][1] == 1) {
            cout << "T\n";
        } else {
            cout << "N\n";
        }

        // 清空 ind 数组，准备下一个测试用例
        for (int i = 1; i <= l; i++) {
            ind[a[i]] = 0;
        }
    }

    return 0;
}

代码说明

1. 数组大小：

   • $L = 1505, N = 1505, M = 1505$ 足以处理 $l, n, m \le 1500$ 的情况
   • $ind$ 数组大小为 $N \times M$，因为 $b_{i,j} \le n \cdot m$

2. 重复数字处理：

   • 与简单版相同，使用 $ind$ 数组记录每个数字第一次出现的位置
   • 遇到重复时立即截断 $l$

3. 动态规划顺序：

   • 外层循环 $i$ 从 $n$ 到 $1$
   • 内层循环 $j$ 从 $m$ 到 $1$
   • 这种顺序保证了计算 $(i,j)$ 时，$(i+1,j)$、$(i,j+1)$ 和 $(i+1,j+1)$ 都已计算完毕

4. 转移逻辑：

   • 先通过移动更新（相当于不选当前格子）
   • 再考虑选择当前格子，此时需要检查下一个玩家在子矩阵 $(i+1,j+1)$ 中是否必败

5. 条件 pos + 3 <= dp1[i+1][j+1] 的解释：

   • 如果 $dp1[i+1][j+1] \ge pos+3$，说明从 $pos+1$ 开始无法获胜
   • 因为 $dp1[i+1][j+1]$ 存储的是能获胜的最小 $k$，如果这个最小值大于 $pos+1$，则 $pos+1$ 无法获胜
   • 使用 $pos+3$ 是因为 $dp$ 存储的是索引，需要留出足够余量

6. 边界处理：

   • 当 $i=n$ 或 $j=m$ 时，$dp0[i+1][j]$ 或 $dp0[i][j+1]$ 为 $\infty$
   • 当 $i=n$ 或 $j=m$ 时，$dp0[i+1][j+1]$ 也为 $\infty$，此时选择当前格子可能获胜