题解：P12039 [USTCPC 2025] 高位逼抢
ethan_zhou
·
·
题解
宣传博客：USTCPC25 F&K 题解
这道题是一个远古（中学时想的） idea，没想到成大三老登了竟然还能用上。
判定问题
假设 x 一定，那么球位于某些点的时候，A 是不败的，称这些点为 胜点，其余点是 败点。考虑如何判定每一个点的胜败。
一个点 p 是败点的充要条件是：
\text {与 } p \text { 相连的胜点数量} = \deg (p) - \text {与 } p \text { 相连的败点数量} \leq x.
于是可以通过类似拓扑排序的方式，求出所有败点：
- 首先把所有满足 \deg (p) \leq x 的点入队，这些点一定是必败无疑的。
- 取出队首，更新与该点相连的点 v 的
\deg (v) - \text {与 } v \text { 相连的败点数量}
的值，如果小于等于 x，则 v 也入队。
显然，上述过程中，所有进入过队列的点就是败点。
最小化 x
一个显然的结论是：
$$
\text {$x$ 对应的败点点集} \subset \text {$x+1$ 对应的败点点集}.
$$
所以我们有一个暴力（但对正解有启发性）的方法：
- 首先对 $x = 1$ 做判定；
- 然后对于在 $x = 1$ 的判定过程中没有入队的结点，再看是否满足 $x = 2$ 时的入队条件，若满足则进行 $x = 2$ 的判定；
- 然后对于在 $x = 2$ 的判定过程中没有入队的结点，再看是否满足 $x = 3$ 时的入队条件，若满足则进行 $x = 3$ 的判定；
- 以此类推……
最后只需要记录每个点在 $x$ 等于几时入队，即为该点的答案。
### 优化
发现上述过程中的入队顺序等价于：
把所有节点扔到以
$$
\deg (p) - \text {与 } p \text { 相连的败点数量}
$$
为关键字排序的小根堆中，每次取出队首并更新相关信息。
时间复杂度为 $O (m \log m)$。
如果把优先队列换成桶，并进行精细实现，可以做到线性复杂度。