CF1795G 题解

· · 题解

部分参考自官方题解。

删点操作有点像拓扑排序，考虑将每个点度数减去 a_i 之后从新度数 0 开始删点，得到一个拓扑序 p_i（注意题目中已经保证了有解，因此这样的拓扑序必定存在）。利用这个拓扑序可以给无向图的边定向，就得到了一个有向图。

大胆猜测一下满足要求的点对 (x,y) 需要满足在新有向图中，不存在 x\rightarrow y 或者 y\rightarrow x 的路径。下面简要证明一下：

必要性：考虑逆否命题，即存在这样的路径，那么由拓扑排序可知无论哪种拓扑序，(x,y) 必然都是某一个在前，另一个在后且顺序不会改变。

充分性：（感性理解一下）我们可以先删 x 及其后继那一堆点，再删 y 这样的点，也可以反过来这么做。

因此我们只需要算有向图中的点可达的点的数量，这里讲一下一种比较好写的压位做法。

每次以 64 为间隔，即第一次考察所有点能到 1..64 中某些点的数量，第二次为 65..128 .. 这样我们就可以用 unsigned long long 来存了，按拓扑序逆推即可。时间复杂度 O(\frac{n^2}{64})。

代码