问题描述

Tsovak 和 Narek 在玩一个游戏。有一个长度为 $l$ 的数组 $a$ 和一个 $n \times m$ 的矩阵 $b$。

游戏规则：

• 两人轮流操作，Tsovak 先手
• 第 $i$ 轮，玩家需要寻找数组元素 $a_i$
• 当前玩家选择一个格子 $(r, c)$，该格子的值必须等于 $a_i$
• 下一个玩家必须在子矩阵 $(r+1, c+1)$ 到 $(n, m)$ 中寻找 $a_{i+1}$
• 无法找到所需元素、剩余子矩阵为空、或数组结束时，当前玩家输

双方都采取最优策略，判断胜者。

关键观察

观察 1：数字范围限制

题目保证所有 $a_i$ 和 $b_{i,j}$ 满足：

$$1 \le a_i, b_{i,j} \le \min(7, n \cdot m)$$

这意味着所有数字都在 $1$ 到 $7$ 之间。

观察 2：重复数字的处理

重要结论：当数组 $a$ 中某个数字出现第二次时，该位置的玩家必输。

证明： 设 $u < v$ 是数字 $x$ 在数组 $a$ 中第一次和第二次出现的位置。

考虑玩家需要选择 $a_u = x$ 的情况。最优策略是选择"最后"一个 $x$（即选择后剩余子矩阵中不再包含任何 $x$）。原因：

• 如果选择某个"内部"的 $x$（记作 $x_2$）能赢，那么在更大的矩阵中选择"最后"的 $x$ 也能赢
• 如果选择 $x_2$ 会输，意味着 $x_2$ 后的子矩阵中存在一个必胜状态给对手，对手可以选择它而不受玩家选择的影响

因此，当玩家到达 $a_v = x$ 时，他必然输，相当于数组 $a$ 在这里结束。

结论：我们可以将数组 $a$ 截断到每个数字最多出现一次。由于数字 $\le 7$，截断后：

$$l \le 7$$

观察 3：博弈状态的简化

由于 $l \le 7$，我们可以用动态规划枚举所有可能的状态。

定义 $dp[k][i][j]$ 表示：

• 当前需要寻找数组 $a$ 的第 $k$ 个元素
• 当前可用子矩阵的左上角为 $(i, j)$（右下角固定为 $(n, m)$）
• 当前轮到某玩家行动
• 值为 $\text{true}$ 表示当前玩家有必胜策略，$\text{false}$ 表示必败

状态转移

对于状态 $dp[k][i][j]$，当前玩家有以下选择：

选择 1：跳过当前格子，向右移动

如果 $j < m$ 且 $dp[k][i][j+1] = \text{true}$，则当前玩家可以获胜。

选择 2：跳过当前格子，向下移动

如果 $i < n$ 且 $dp[k][i+1][j] = \text{true}$，则当前玩家可以获胜。

选择 3：选择当前格子

当 $b[i][j] = a[k]$ 时，玩家可以选择这个格子：

情况 3.1：$k = l$（这是最后一个元素）

• 选择后数组结束，对手无法继续
• 当前玩家获胜
• $$dp[k][i][j] = \text{true}$$

情况 3.2：$k < l$ 且 $i < n$ 且 $j < m$

• 选择后，对手需要在子矩阵 $(i+1, j+1)$ 中寻找 $a[k+1]$
• 当前玩家获胜当且仅当对手在 $dp[k+1][i+1][j+1]$ 中必败
• $$dp[k][i][j] = \lnot dp[k+1][i+1][j+1]$$

情况 3.3：$k < l$ 且（$i = n$ 或 $j = m$）

• 选择后子矩阵为空，对手无法继续
• 当前玩家获胜
• $$dp[k][i][j] = \text{true}$$

如果 $b[i][j] \ne a[k]$，则不能选择当前格子。

算法步骤

1. 预处理数组 $a$：

   • 使用数组 $ind[8]$ 记录每个数字第一次出现的位置
   • 遍历 $a$，遇到重复数字时截断 $l$

2. 动态规划计算：

   • 从 $i = n$ 到 $1$，$j = m$ 到 $1$ 逆序循环
   • 对每个 $k = 1$ 到 $l$ 计算 $dp[k][i][j]$
   • 按照优先级：先判断能否通过移动获胜，再判断能否通过选择获胜

3. 判断结果：

   • 若 $dp[1][1][1] = \text{true}$，输出 "T"（Tsovak 获胜）
   • 否则输出 "N"（Narek 获胜）

时间复杂度

• 预处理数组 $a$：$O(l)$，由于 $l \le 7$ 可忽略
• 动态规划：$O(l \cdot n \cdot m) = O(7 \cdot n \cdot m)$
• 所有测试用例的 $n \cdot m$ 之和 $\le 10^5$，总时间复杂度可行

完整代码

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

const int L = 305, N = 305, M = 305;
int a[L], b[N][M];
int l, n, m;
int ind[8];  // 记录每个数字第一次出现的位置
bool dp[8][N][M];  // dp[k][i][j]

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];
            }
        }

        // 动态规划：从右下角往左上角计算
        for (int i = n; i >= 1; i--) {
            for (int j = m; j >= 1; j--) {
                for (int k = 1; k <= l; k++) {
                    // 优先级1：如果能通过向右移动获胜
                    if (j < m && dp[k][i][j + 1]) {
                        dp[k][i][j] = true;
                        continue;
                    }

                    // 优先级2：如果能通过向下移动获胜
                    if (i < n && dp[k][i + 1][j]) {
                        dp[k][i][j] = true;
                        continue;
                    }

                    // 优先级3：考虑选择当前格子
                    if (b[i][j] == a[k]) {
                        if (k == l) {
                            // 最后一个元素，选择后对手无法继续
                            dp[k][i][j] = true;
                        } else if (i < n && j < m) {
                            // 选择后，对手需要在子矩阵 (i+1, j+1) 中找 a[k+1]
                            dp[k][i][j] = !dp[k + 1][i + 1][j + 1];
                        } else {
                            // 选择后子矩阵为空，对手无法继续
                            dp[k][i][j] = true;
                        }
                    } else {
                        // 不能选择当前格子，且无法通过移动获胜，则必败
                        dp[k][i][j] = false;
                    }
                }
            }
        }

        // 输出结果
        if (dp[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 = 305, N = 305, M = 305$ 足以处理 $l, n, m \le 300$ 的情况

2. 重复数字处理：

   • 使用 $ind[8]$ 数组记录每个数字（$1$ 到 $7$）第一次出现的位置
   • 遇到重复时立即截断 $l$

3. 动态规划顺序：

   • 外层循环 $i$ 从 $n$ 到 $1$
   • 中层循环 $j$ 从 $m$ 到 $1$
   • 内层循环 $k$ 从 $1$ 到 $l$
   • 这种顺序保证了计算 $dp[k][i][j]$ 时，$dp[k][i+1][j]$、$dp[k][i][j+1]$ 和 $dp[k+1][i+1][j+1]$ 都已经计算完毕

4. 转移优先级：

   • 先判断能否通过移动（向右或向下）获胜
   • 再判断能否通过选择当前格子获胜
   • 这是因为移动相当于"跳过"当前格子，如果存在必胜的移动，玩家一定选择它

5. 边界处理：

   • 当 $k = l$ 时，选择最后一个元素直接获胜
   • 当 $i = n$ 或 $j = m$ 时，选择后子矩阵为空，对手无法继续

总结

本题的核心技巧：

1. 利用数字范围 $\le 7$ 的限制，通过观察重复数字的性质将问题规模缩小
2. 使用从右下角到左上角的动态规划处理子矩阵博弈
3. 状态转移时考虑"跳过"和"选择"两种操作
4. 博弈问题的标准处理：当前玩家胜当且仅当存在一步使得对手进入必败态