免费咨询专业服务_网络营销推广的策略_太原做网站哪家好_搜外seo视频 网络营销免费视频课程

Subtangle Game (Hard Version))

#动态规划 #记忆化搜索 #博弈论 #模拟

题目描述

This is the hard version of the problem. The differences between the two versions are the constraints on all the variables. You can make hacks only if both versions of the problem are solved.

Tsovak and Narek are playing a game. They have an array $a$ and a matrix $b$ of integers with $n$ rows and $m$ columns, numbered from $1$. The cell in the $i$-th row and the $j$-th column is $(i,j)$.

They are looking for the elements of $a$ in turns; Tsovak starts first. Each time a player looks for a cell in the matrix containing the current element of $a$ (Tsovak looks for the first, then Narek looks for the second, etc.). Let’s say a player has chosen the cell $(r,c)$. The next player has to choose his cell in the submatrix starting at $(r+1,c+1)$ and ending in $(n,m)$ (the submatrix can be empty if $r=n$ or $c=m$). If a player cannot find such a cell (or the remaining submatrix is empty) or the array ends (the previous player has chosen the last element), then he loses.

Your task is to determine the winner if the players play optimally.

Note: since the input is large, you may need to optimize input/output for this problem.

For example, in C++, it is enough to use the following lines at the start of the main() function:

输入格式

The first line of the input contains $t$ ($1\le t\le 1500$) – the number of test cases.

The first line of each test case contains three integers $l$, $n$, and $m$ ($1\le l,n,m\le 1500$) – the size of the array and the sizes of the matrix.

The second line contains $l$ integers $a_1,a_2,a_3,\dots a_l$ ($1\le a_i\le n\cdot m$) – the elements of the array $a$.

The $i$-th of the last $n$ lines contains $m$ integers $b_{i,1},b_{i,2},b_{i,3},\dots b_{i,m}$ ($1\le b_{i,j}\le n\cdot m$) – representing the $i$-th row of the matrix.

It is guaranteed that the sum of $n\cdot m$ over all test cases does not exceed $3\cdot 10^6$.

It is guaranteed that the sum of $l$ over all test cases does not exceed $1500$.

输出格式

You should output $t$ lines, the $i$-th of them containing a character representing the answer of the $i$-th test case: “T” if Tsovak wins or “N”, otherwise (without quotes).

样例 #1

样例输入 #1

3
2 2 3
1 2
1 3 6
4 6 2
2 2 4
1 2
1 1 3 2
4 2 5 1
2 4 2
1 2
3 4
5 6
7 8
8 8

样例输出 #1

N
T
N

解法

解题思路

首先我们知道，对于同一个数，我们取横坐标越大、纵坐标越大的位置绝对是更优的，因此，后手选择的时候只需要选择较大的即可。

考虑先手什么时候获胜。由于这是博弈论是在这样一个矩阵上进行的，我们其实可以通过记忆化搜索的情况把后手的所有选择都处理出来，如果后手不存在获胜的条件，那么先手就能获胜。

由于每次都是相同的过程，所以直接递归记录即可。

注意的就是一开始我们需要筛选出横、纵坐标最大的那些位置，这样可以减少一些不必要的搜索，搜索的效率会大大提升，然后在搜索到结果时及时返回，进行剪枝。

还有一个小技巧，就是我们直接从$0$开始搜索，而不是$1$，这样就无需遍历所有$1$的节点搜索，这样的写法可以减少一些代码量。

代码

const int N = 1e3 + 10;void solve() {int len, n, m;std::cin >> len >> n >> m;std::vector<int>a(len + 1);for (int i = 1; i <= len; ++i) {std::cin >> a[i];}std::vector<std::vector<pii>>pos(n * m + 1);std::map<std::array<int, 3>, bool>memo;std::vector<std::vector<int>>mx(n + 1, std::vector<int>(m + 1));for (int i = 1; i <= n; ++i) {for (int j = 1; j <= m; ++j) {std::cin >> mx[i][j];int x = mx[i][j];while (pos[x].size() && pos[x].back().second < j) {pos[x].pop_back();}pos[x].push_back({ i, j });}}auto dfs = [&](auto&& self, int x, int y, int idx)->bool {if (idx >= len) return false;if (memo.count({ x,y,idx })) return memo[{x, y, idx}];bool &ok = memo[{x,y,idx}];for (auto& [i, j] : pos[a[idx+1]]) {if (i > x && j > y && !self(self, i, j, idx + 1)) {ok = true;return ok;}}return ok;};bool ok = dfs(dfs, 0, 0, 0);if (ok) std::cout << "T\n";else std::cout << "N\n";
}signed main() {std::ios::sync_with_stdio(0);std::cin.tie(0);std::cout.tie(0);int t = 1;std::cin >> t;while (t--) {solve();}
}