专栏文章

题解：P12039 [USTCPC 2025] 高位逼抢

eethan_zhou
P12039题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipobte1
此快照首次捕获于
2025/12/03 15:16
3 个月前
此快照最后确认于
2025/12/03 15:16
3 个月前
查看原文
宣传博客：USTCPC25 F&K 题解
这道题是一个远古（中学时想的） idea，没想到成大三老登了竟然还能用上。

判定问题

假设 xx 一定，那么球位于某些点的时候，A 是不败的，称这些点为 胜点，其余点是 败点。考虑如何判定每一个点的胜败。
一个点 pp 是败点的充要条件是：
与 p 相连的胜点数量=deg⁡(p)−与 p 相连的败点数量≤x.\text {与 } p \text { 相连的胜点数量} = \deg (p) - \text {与 } p \text { 相连的败点数量} \leq x.
于是可以通过类似拓扑排序的方式，求出所有败点：
  • 首先把所有满足 deg⁡(p)≤x\deg (p) \leq x 的点入队，这些点一定是必败无疑的。
  • 取出队首，更新与该点相连的点 vv 的 deg⁡(v)−与 v 相连的败点数量\deg (v) - \text {与 } v \text { 相连的败点数量} 的值，如果小于等于 xx，则 vv 也入队。
显然，上述过程中，所有进入过队列的点就是败点。

最小化 xx

一个显然的结论是：
xx 对应的败点点集是 x+1x+1 对应的败点点集的子集：
x 对应的败点点集⊂x+1 对应的败点点集.\text {$x$ 对应的败点点集} \subset \text {$x+1$ 对应的败点点集}.
所以我们有一个暴力（但对正解有启发性）的方法：
  • 首先对 x=1x = 1 做判定；
  • 然后对于在 x=1x = 1 的判定过程中没有入队的结点，再看是否满足 x=2x = 2 时的入队条件，若满足则进行 x=2x = 2 的判定；
  • 然后对于在 x=2x = 2 的判定过程中没有入队的结点，再看是否满足 x=3x = 3 时的入队条件，若满足则进行 x=3x = 3 的判定；
  • 以此类推……
最后只需要记录每个点在 xx 等于几时入队，即为该点的答案。

优化

发现上述过程中的入队顺序等价于：
把所有节点扔到以
deg⁡(p)−与 p 相连的败点数量\deg (p) - \text {与 } p \text { 相连的败点数量}
为关键字排序的小根堆中，每次取出队首并更新相关信息。
时间复杂度为 O(mlog⁡m)O (m \log m)。
如果把优先队列换成桶，并进行精细实现，可以做到线性复杂度。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...