[AGC077B] Long Increasing Walk

PTqwq · 2026-07-26 11:00:41 · 题解

直接构造对我来说很困难，但是事实上这个题还是存在非直直接构造的方法的，做法来自 jiangly 讲课。

首先第一个问题是，如果给定了一张定好边权的图，如何求最长边权递增路径：设 f_i 表示当前路径走到节点 i 的方案数，按边权从小到大扫每一条边 (x, y + n)，每次 f'_x \leftarrow f_{y+n}+1, f'_{y+n} \leftarrow f_x+1，最终答案就是 \max\limits_{1 \leq i \leq 2n}f_i。

考虑分析 \max f 的上下界，一个结论是，更新一次 \sum f_i 至少增加 2，所以 \max f 至少也是 \dfrac{2n^2}{2n} = n，最大可以考虑选一条最长的欧拉路径，n 是偶数则可以构造成 n^2，奇数则需要删掉 n - 1 条边来满足度数奇偶性，最大值为 n^2 - n + 1。

最大值的构造比较简单，而最小值可以继续考虑 DP 的更新过程，如果更新形如 n 组完美匹配，我们就可以保证 f_1, f_2, \dots, f_{2n} 最终都是 n，而构造是容易的。

现在我们得到了最小的方案 G_{\text{min}} 和最大的方案 G_{\text{max}}，如果我们可以构造一条 G_{\text{min}} \to G_{\text{max}} 的路径，相邻两个方案 G_x, G_y 的最长路径相差不超过 1，那我们就一定可以得到 k 在中间的所有解。

但是这并不容易，但是你发现如果我们删一条边，最长路径可能会减少很多，增加一条边也可以增加很多，但是如果我们改成增加一条边权为全局最小值的边，最长路径最多增加 1，所以我们每次相当于把一条边的边权改成全局最小值。

设 f(G) 表示方案 G 的答案，则有 f(G_y) \leq f(G_x) + 1，而我们使用上面的操作只需要 n^2 步就可以从 G_{\text{min}} 调整到 G_{\text{max}}。

虽然没有单调性，但是我们依然可以二分，每次都保证下一个二分的区间包含我们需要的解即可，时间复杂度 O(n^2 \log n)。

https://atcoder.jp/contests/agc077/submissions/77873695