我说非传统题王朝了你尔多隆吗

· · 题解

题目大意

给定 n 个点 m 条边的无向图 G 和正整数 k，你可以对这个图进行不超过 p 次操作，单次操作如下：

最大化所有操作后 G 的边数，同时给出构造。

## 解法 显然一次操作可以看作整体异或一个 $k$ 个点的完全图。为了刻画方便，首先将 $G$ 取补图，此时要求变为最小化最终的边数。原题答案即为 $\frac{n(n-1)}{2}$ 减去该值。 我们猜测 $p=\frac{n(n-1)}{2}$ 是充分大的：即使操作次数没有限制，$G$ 可能的最小边数也不会小于 $p=\frac{n(n-1)}{2}$ 时的最小边数。进一步猜测最小边数总是能够取到 $0$，但是观察大样例发现不对。 考虑操作过程中哪些因素会导致图无法删空。异或操作启发我们关注模 $2$ 的不变量。具体来说可以发现： - 若 $2\nmid k$，则一次操作不改变每个点的度数的奇偶性； - 若 $2\mid \binom{k}{2}$，则一次操作不改变总边数的奇偶性。 这两个条件恰好将 $k$ 按照模 $4$ 的余数分为了四类。我们猜测这两个条件是充分的，即图 $G$ 能够删空**当且仅当**： - $k \equiv 2 \pmod 4$：无限制。此时任意图能够删空。 - $k \equiv 3 \pmod 4$：所有点度数为偶数。 - $k \equiv 0 \pmod 4$：边数为偶数。 - $k \equiv 1 \pmod 4$：上述二者。 则答案恰为最少更改多少条边，使得 $G$ 变为符合要求的形式。继续分类讨论： - $k\equiv 3 \pmod 4$：记 $G$ 中奇度数的点有 $x$ 个。将其两两配对并更改之间的边即可。此时最小边数即为 $\frac{x}{2}$。 - $k\equiv 0 \pmod 4$：若边数为奇数，则任意改一条边，最小边数为 $1$；否则为 $0$。 - $k\equiv 1 \pmod 4$：首先进行 $k\equiv 3$ 时的操作。若此时边数为奇数： - 若更改过至少一条边，不妨记该边为 $(u,v)$。将其改为修改 $(u,x),(x,v)$，其中 $x$ 为任意异于 $u,v$ 的点。此时答案需要额外加 $1$。 - 否则至少需要更改 $3$ 条边。只需改任意一个三元环，答案为 $3$。 此时可以获得 $25$ 分。 --- 上一步之后我们已经获得了一个满足要求的图 $G$。接下来构造操作以将 $G$ 删空。 考虑**递归构造**。当 $n>k+2$ 时，可取出 $n$ 号点，将其度数变为 $0$ 后，继续处理剩下大小为 $n-1$ 的子图。根据假设，剩下的子图一定能在内部用 $\frac{(n-1)(n-2)}{2}$ 次操作删空，因此只需做到用不超过 $n-1$ 次操作将 $n$ 号点的邻边删除。 我们直接忽略剩下 $n-1$ 个点组成的子图，并记录 $1\sim n-1$ 中的每个点此时是否与 $n$ 有边，得到一个长为 $n-1$ 的 $01$ 串。则问题变为每次在该串上翻转恰好 $k-1$ 个位置，希望将其变为全 $0$。显然当 $1$ 的个数 $x\ge k-1$ 时，一次操作总可以将 $x$ 减少 $k-1$。接下来考虑 $x<k-1$ 但不为 $0$ 的情形。对 $x$ 的奇偶性分类讨论： - 若 $2\mid x$：考虑两次操作将 $x$ 减小 $2$。首先选取 $x-1$ 个 $1$ 和 $k-x$ 个 $0$，将其翻转。由于 $n>k+2$，$0$ 的个数一定有至少 $k-x$ 个，因此该操作可以进行。接下来选取全部 $k-x+1$ 个 $1$ 和 $x-2$ 个 $0$，将其翻转。不断这样做直到 $x=0$。 - 若 $2\nmid x$：根据假设，此时 $k$ 一定是偶数。考虑两次操作将 $x$ 增加 $2$：第一次选取 $x$ 个 $1$，第二次选取 $k-x-2$ 个 $1$ 进行翻转。这样做直到 $x=k-1$，然后翻转全部的 $1$。 关于操作次数：在 $x\ge k-1$ 时，一次操作可以消去 $k-1$ 个 $1$；$x<k-1$ 时最坏情况下为 $k-1$ 次操作消去 $1$ 个 $1$。显然操作次数不超过 $\max(k-1,deg_n)$，从而不超过 $n-1$。 递归构造的终止条件是 $n=k+2$，考虑此时的做法。我们考察一次操作的**反面**：记操作 $P_{u,v}$ 为选择两个点 $u,v$，操作剩下的 $k$ 个点。此时一次操作等价于如下三步： - 对图取补图。即，对所有边翻转。 - 将 $u$ 的邻边与 $v$ 的邻边翻转。 - 将边 $(u,v)$ 翻转。 注意到，若当前的图 $G$ 满足每个点度数为偶数，且总边数为偶数，则可以选取 $G$ 中每条出现过的边 $(u,v)$，然后同时操作 $P_{u,v}$。此时整张图被取补偶数次，且每个点的邻边也被翻转偶数次，恰好抵消。因此我们的操作目的变为将 $G$ 修改为该形式。仍然对 $k$ 分类讨论： - $k \equiv 1 \pmod 4$：根据假设，此时的图已经合法。 - $k \equiv 3 \pmod 4$：此时每个点度数一定为偶数。若总边数为奇数，则任意操作一次即可。 - $k \equiv 0 \pmod 4$：此时总边数一定为偶数。考虑每个点度数的奇偶性情况，一次操作可翻转恰好 $k$ 个位置。显然奇度点有偶数个，因此可以不断进行前述的减 $2$ 操作，直到不存在奇度点。 - $k \equiv 2 \pmod 4$：首先进行 $k\equiv 0$ 时的操作。此时若边数为奇数，则考虑**操作补图**。具体来说，改为选取 $G$ 中每条未出现的边 $(u,v)$，然后同时操作 $P_{u,v}$。由于此时每个点度数为偶数，且 $n=k+2$ 是 $4$ 的倍数，可以发现该操作恰好抵消了所有边。 对于这部分算法，注意到本质不同的 $P$ 只有 $\frac{n(n-1)}{2}$ 个，且同一个 $P_{u,v}$ 操作两次可以抵消，因此将所有操作去重即可保证操作数。 实现时，可以使用 bitset 做到 $O(\frac{k^2}{w})$ 维护异或大小为 $k$ 的完全图，总复杂度 $O(\frac{n^2k^2}{w})$，总操作次数 $\le \frac{n(n-1)}{2}$，可以通过。