有向图游戏-DAG博弈

最近的牛客暑假营L题和26上海CCPC市赛出现了这个类型的题。

引用 OI-WIKI 上的介绍

本文讨论的公平组合游戏，要求同一局面不能出现两次，也不存在平局的可能性．因此，对应的博弈图总是有向无环图．本节放宽了这一限制，讨论如何在一般的有向图上判定各个状态是先手必胜、先手必败或平局．

有向图游戏的规则和其他的公平组合游戏大体一致：从起始状态出发，轮流沿着有向图的边移动一步，直到无路可走．根据游戏是正常规则还是反常规则，最后一个不能移动的玩家分别是败者和胜者．在这样的游戏里，每个状态的胜负情况共有三种可能性：先手必胜、先手必败、平局．平局中游戏永远不会终止．尽管稍微复杂一些，但是关于必败状态和必胜状态的 引理 依然成立，而剩下的状态就是平局状态：

• 一个状态有后继状态先手必胜，当且仅当后继状态之一是必败状态；
• 如果一个状态有后继状态，那么它先手必败，当且仅当所有后继状态都是必胜状态；
• 如果一个状态无法分类为必胜状态和必败状态，那么它就是平局状态．

要将所有状态分类为这三种状态，只需要采用类似 拓扑排序 的思路：

1. 初始化时，记录所有状态的出度，将所有出度为零的状态压入队列，并根据游戏是正常规则或是反常规则分别设为必败状态或必胜状态．
2. 弹出队首状态．如果是必败状态，则设前驱状态为必胜状态；否则，当前状态是必胜状态，将它的所有前驱状态的出度减一，并将出度为零的前驱状态设为必败状态．将可以判断是必胜或必败状态的前驱状态压入队列．
3. 算法在队列为空时终止．尚未判断为必胜或必败状态的状态均为平局状态．

这一算法可以在 $O(|V|+|E|)$ 时间内将所有状态分类．

牛客训练营三 L 题

两位登山者（先手玩家和后手玩家）在一个山地地图上玩一个游戏。
地图是一个包含 $n$ 行和 $m$ 列的网格。第 $i$ 行第 $j$ 列的格子有一个整数高度 $h_{i,j}$。地图上所有高度两两不同：没有任何两个格子具有相同的高度。
一面旗帜被放置在其中一个格子上。两位玩家轮流移动旗帜，由先手玩家率先移动。在玩家的回合中：

• 玩家必须将旗帜从当前格子移动到一个正交相邻（共用一条边）的格子上，且该目标格子的高度必须严格大于当前格子的高度；
• 如果当前格子没有高度严格大于它的正交相邻格子，那么该回合的玩家将无法移动并输掉游戏，另一位玩家获胜。

由于每次移动都会到达一个严格更高的格子，旗帜永远不会返回到它已经离开过的格子上，因此游戏总会在有限步移动后结束。两位玩家都采取最优策略。
给你 $q$ 个独立的询问。每个询问指定了旗帜的初始格子；在不同询问之间，地图本身永不改变。对于每个询问，请判断在最优策略下谁将获胜：是先手玩家，还是后手玩家。

输入描述
每个测试文件包含多个测试用例。第一行包含测试用例的数量 $T$ ($1\le T\le 500$)。接下来是各个测试用例的描述。
每个测试用例的第一行包含两个整数 $n$ 和 $m$ ($1\le n,m\le 10^5$，$n\cdot m\le 10^5$)，分别表示地图的行数和列数。
接下来的 $n$ 行描述了地图的高度。这 $n$ 行中的第 $i$ 行包含 $m$ 个整数 $h_{i,1},h_{i,2},\dots ,h_{i,m}$ ($1\le h_{i,j}\le 10^9$)，其中 $h_{i,j}$ 是第 $i$ 行第 $j$ 列格子的高度。保证同一个测试用例内的 $n\cdot m$ 个高度两两不同。
下一行包含一个整数 $q$ ($1\le q\le 10^5$)，表示询问的数量。
接下来的 $q$ 行，每行包含两个整数 $r$ 和 $c$ ($1\le r\le n$，$1\le c\le m$)，表示在当前询问中，旗帜最初放置在第 $r$ 行第 $c$ 列的格子上。
对于每个测试文件，保证所有测试用例的 $n\cdot m$ 之和不超过 $10^5$，且所有测试用例的 $q$ 之和不超过 $10^5$。

输出描述
对于每个询问，输出一行：如果先手玩家在最优策略下获胜，输出 First；如果后手玩家在最优策略下获胜，输出 Second。

备注
在示例中，地图有 $2$ 行 $3$ 列。第 $1$ 行为 $123$，第 $2$ 行为 $654$。例如，$h_{2,1}=6$ 是全图最高的格子，$h_{1,1}=1$ 是最低的格子。
站在没有严格更高相邻格子的玩家会立即输掉游戏。

• 询问 $(2,1)$ 的高度为 $6$，是整个地图的最大值，因此先手玩家无法移动并立刻输掉游戏：答案为 Second。
• 询问 $(2,3)$ 的高度为 $4$。它唯一严格更高的相邻格子是高度为 $5$ 的 $(2,2)$，而 $(2,2)$ 唯一严格更高的相邻格子是高度为 $6$ 的 $(2,1)$。因此移动路径是唯一的：$4\to 5\to 6$。先手玩家移动到 $5$，后手玩家移动到 $6$，此时先手玩家无法继续移动并输掉游戏。答案为 Second，尽管 $(2,3)$ 不是最高的格子。这也说明无法仅凭简单的局部特征来决定胜负。
• 询问 $(1,1)$ 的高度为 $1$。先手玩家可以移动到 $(1,2)$（高度为 $2$），这对于后手玩家来说是一个必败态，因此答案为 First。

我们注意到：数字只能从低往高处走，谁走到了四周都是比较低的那个，谁就输了（必输态）。所以我们就可以仿照拓扑排序那样，从高到底，依次去进行状态转移。
最高点的四周肯定比这个最高点小，所以 dp[i][j] = 0
PS: 这个DP数组的定义是：在 (i, j) 这个点，如果是必输态就是0，是必胜态就是1
接下来我们去做必胜态的转移，我们按照出度为0顺序慢慢“剥洋葱”，如果这个点的上下左右存在有一个点比当前点高（这位选手必须往上走！），并且那个较高点处于必输态dp[x+i][y+j] = 0，那么这个点就是必胜态 dp[x][y] = 1

总结一下这些点

• 如果一个点上下左右全部比这个点小，则必输态dp[x+i][y+j] = 0
• 如果一个点存在比他大的点，并且这个点处于必输态，则这个点处于必胜态 dp[x][y] = 1

代码如下

1#include <bits/stdc++.h>2using namespace std;3// #define int long long4#define endl "\n"5void solve() {6    int n, m;7    cin >> n >> m;8    vector<vector<int>> g(n+1, vector<int>(m+1, 0));9    vector<pair<int, array<int, 2>>> bug;10    for (int i = 0; i < n; ++i) {11        for (int j = 0; j < m; ++j) {12            cin >> g[i][j];13            bug.push_back({g[i][j], {i, j}});14        }15    }16    sort(bug.begin(), bug.end(), [&](pair<int, array<int, 2>>&a , pair<int, array<int, 2>>& b) {17        return a.first > b.first;18    });19    vector<vector<int>> dp(n+1, vector<int>(m+1, 0));20    int DIRS[4][2] = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};21    for (auto& z : bug) {22        auto [x, y] = z.second;23        bool flag = false;24        for (auto [mx, my] : DIRS) {25            int i = mx + x, j = my + y;26            if (i >= 0 && j >= 0 && i < n && j < m) {27                if (dp[i][j] == 0 && g[i][j] > g[x][y]) {28                    flag = true;29                }30            }31        }32        dp[x][y] = flag; 33    }34    int q; cin >>q;35    while (q--) {36        int a, b;37        cin >> a >> b;38        a--, b--;39        if (dp[a][b]) {40            cout << "First" << endl;41        } else {42            cout << "Second" << endl;43        }44    }45}46signed main() {47    ios::sync_with_stdio(false);48    cin.tie(0);49    int T = 1;50    cin >> T;51    while (T--) {52        solve();53    }54    return 0;55}