1895E Infinite Card Game
这是一道博弈论建图题目，通过对两个数组排序并用前缀最大值确定连边关系，反向建图后跑拓扑排序判断最终状态。
题目大意
Infinite Card Game
单卡和双卡在玩纸牌游戏。每张牌都有两个参数：攻击值和防御值。$s$ 能打败 $t$ 当且仅当 $s$ 的攻击值严格大于 $t$ 的防御值。
Monocarp 有 $n$ 张牌，其中第 $i$ 张的攻击值为 $\mathit{ax}_i$，防御值为 $\mathit{ay}_i$ 。Bicarp有 $m$ 张牌，其中第 $i$ 张的攻击值为 $\mathit{bx}_i$，防御值为 $\mathit{by}_i$。在第一步棋中，Monocarp 选择他的一张牌并打出。Bicarp 必须用他自己的牌来回应，而这张牌要胜过那张牌。之后，Monocarp 必须用一张击败比卡普的牌来回应。之后，轮到 Bicarp，以此类推。
一张牌被打出后，回到打出该牌的玩家手中。 这意味着每个玩家总是拥有游戏开始时的同一套牌。 游戏结束时，若当前玩家手中的牌不能击败对手刚刚打出的牌，当前玩家输掉游戏。如果对局持续 $100^{500}$ 步，则宣布平局。
Monocarp 和 Bicarp 都是最佳下法。也就是说，如果棋手无论对手下了多少步棋，都有获胜的策略，那么他就会获胜。否则，如果他有平局策略，他就下平局。要求您计算三个值：
- Monocarp 的起手牌中导致 Monocarp 获胜的牌数；
- Monocarp 的起手牌中导致平局的牌数；
- Monocarp 的起手牌中导致 Bicarp 获胜的牌数。
多组数据，$1 \le t \le 10^4$，$1 \le n \le 3 \cdot 10^5$，$1 \le \mathit{ax}_i,\mathit{ax}_y,\mathit{bx}_i,\mathit{by}_i \le 10^6$，$\sum n,\sum m \leq 3 \cdot 10^5$。
思路
对于这类问题，可以考虑建立有向关系图，描述每张牌对应的“下一张牌”可能是什么。然而，$O(N^2)$ 的建图时空复杂度均过高，考虑如何将图的边数压缩，只保留有效的边。
不难发现，每张打出的牌的攻击力只需要满足大于场上牌的防御力 $y$ 的条件，而为了使对方尽量不能出牌，贪心的考虑，应当使打出的牌防御力尽可能大。也就是说，每张牌对应的它的“下一张牌”一定是对方所拥有的攻击力大于 $y$ 的牌中，防御力最大的一张。这个操作可以对两个数组排序，然后求解出前缀最大值来完成。
将每张牌被打出的情景视为一个状态，对于每个状态，它的下一个节点都是确定的（出度最大为 1），最终结果也是确定的。
因此不难想到，反向建图后跑一遍拓扑排序，初始入度为 0 的那些点也就是这个点所对应的一条链上的所有点的最终状态，而拓扑排序没有跑到的点（环上的点）即是平局状态。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
int n, m, p;
struct node {
int atk, def, id;
} a[maxN + 5], b[maxN + 5];
int pre_max[maxN + 5];
vector<int> to[2 * maxN + 5];
int in_deg[2 * maxN + 5], res[2 * maxN + 5];
void solve() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i].atk;
a[i].id = i;
}
for (int i = 1; i <= n; i++) {
cin >> a[i].def;
}
cin >> m;
for (int i = 1; i <= m; i++) {
b[i].id = n + i;
cin >> b[i].atk;
}
for (int i = 1; i <= m; i++) {
cin >> b[i].def;
}
for (int i = 1; i <= n + m; i++) {
to[i].resize(0);
in_deg[i] = 0, res[i] = 0;
}
sort(a + 1, a + n + 1, [](node x, node y) { return x.def > y.def; });
sort(b + 1, b + m + 1, [](node x, node y) { return x.atk > y.atk; });
pre_max[1] = 1;
for (int i = 2; i <= m; i++) {
if (b[i].def > b[pre_max[i - 1]].def) {
pre_max[i] = i;
} else {
pre_max[i] = pre_max[i - 1];
}
}
p = 1;
for (int i = 1; i <= n; i++) {
if (b[p].atk <= a[i].def) {
continue;
}
while (b[p].atk > a[i].def && p <= m) {
p++;
}
p--;
to[b[pre_max[p]].id].pb(a[i].id); // 反向建边
// cerr << b[pre_max[p]].id << " " << a[i].id << endl;
in_deg[a[i].id]++;
}
sort(a + 1, a + n + 1, [](node x, node y) { return x.atk > y.atk; });
sort(b + 1, b + m + 1, [](node x, node y) { return x.def > y.def; });
pre_max[1] = 1;
for (int i = 2; i <= n; i++) {
if (a[i].def > a[pre_max[i - 1]].def) {
pre_max[i] = i;
} else {
pre_max[i] = pre_max[i - 1];
}
}
p = 1;
for (int i = 1; i <= m; i++) {
if (a[p].atk <= b[i].def) {
continue;
}
while (a[p].atk > b[i].def && p <= n) {
p++;
}
p--;
to[a[pre_max[p]].id].pb(b[i].id); // 反向建边
// cerr << a[pre_max[p]].id << " " << b[i].id << endl;
in_deg[b[i].id]++;
}
queue<int> q;
for (int i = 1; i <= m + n; i++) {
if (in_deg[i] == 0) {
q.push(i);
res[i] = i;
}
}
while (!q.empty()) {
int xn = q.front();
q.pop();
for (auto &it : to[xn]) {
in_deg[it]--;
res[it] = res[xn];
q.push(it);
}
}
int ans[3] = {0};
for (int i = 1; i <= n; i++) {
if (res[i] == 0) {
ans[1]++;
} else if (res[i] <= n) {
ans[0]++;
} else {
ans[2]++;
}
}
for (int i = 0; i < 3; i++) {
cout << ans[i] << " ";
}
cout << endl;
}