题解：AT_abc446_f [ABC446F] Reachable Set 2

I_Love_DS · 2026-02-22 18:14:19 · 题解

考虑洪水填充。

考虑维护一个优先队列 S 表示待更新节点，初始 S = \{1\}。对于 i = 1,2,\dots,n，每次看队头是否等于 i，如果不，说明当前必须跨过一个大于 i 的数才能达到 i，显然不合法。（这种情况见样例 1）

然后每次删队头，直到队头大于 i，说明现在更新不动了。如果现在遍历到的点少于 i，说明可能是这种情况：

（如果你不判断，那么 i=3 时你的程序也许会输出解）

注意写法，有重边自环，可以维护一个标记表示是否到过。

代码：https://atcoder.jp/contests/abc446/submissions/73499761