题解：AT_agc077_b [AGC077B] Long Increasing Walk

· · 题解

怎么 leow 只提了一嘴介值定理的调整法做法，我来补一个

【题意】

给定 n,k。

考虑一个完全二分图 G，左右各 n 个顶点 l_{1\sim n},r_{1\sim n}。

构造一种方法，把 1\sim n^2 填入每条边，使得最长的边权递增路径边数为 K，或判断无解。

# 【题解】 这种构造，先考虑一下 $k$ 的上下界。 下界：发现 $k\ge n$。 > 设 $dp_x$ 表示 $x$ 结尾的最长递增路径长度。 > > 从小到大扫描所有边，对于一条边可以更新 $dp_u\gets dp_v+1,dp_v\gets dp_u+1$。 > > 不难发现较小的那个一定会变成较大的 $+1$。所以每更新一次就会使得所有 DP 值的总和至少 $+2$。抽屉原理知至少一个 $dp\ge n$。 根据这个证明可以做出简单的下界构造：取 $n$ 组完美匹配，让每次 dp 值更新是按组来更新的，这样每一组之后左右的 DP 最大值至多增加一。 然后考虑上界。 显然就是选择一条最长简单路径即可。$n$ 是偶数时 $k\le n^2$（欧拉回路）；$n$ 是奇数时需要两个奇数度数点，所以要去掉 $n-1$ 条边，$k\le n^2-(n-1)$。 --- 现在考虑怎么从上下界往中间构造。 尝试构造一条从下界到上界的路径，每一步对 $k$ 的影响都是 $\pm 1$ 的。这样就能构造出上下界之间的所有 $k$。 那么一个自然的想法就是不断延长下界的路径。但是为了延申构造出来的路径，边权的调整就会很复杂。所以我们应该是尝试调整边权使路径长度增加，而不是先确定增加的是哪条边再让边权去配合它。 取出下、上界的构造 $p_1,p_2$：两个边 $(u,v)$ 的排列，排名第 $x$ 的边在对应方案中边权为 $x$。 考虑根据 $p_1,p_2$ 构造一下中间状态 $q$。发现可以令 $q_i$ 为：把 $p_2$ 中最靠后的 $i$ 条边放到开头，其余边按照 $p_1$ 中的顺序排列。 $i\to i+1$ 就是把 $p_2[n^2-(i+1)+1]$ 的边权变成 $1$，$p_2[n^2-(i+1)+2\sim n^2]$ 的边权都加 $1$。 把边权变成 $1$ 这个操作，可能会破坏路径，导致 $k$ 一下减少很多；同时新增一条 $1$ 的边，$k$ 至多增加一。所以这个过程依然不会跳过任何状态。 不会跳过任何状态，也就是说明如果 $q_i$ 的最长路径等于 $x$，则 $q_{i+1\sim n^2}$ 一定包含 $k\in [x+1,n^2]$ 的方案，反过来也是类似的。 那么我们二分即可，复杂度 $O(n^2\log n)$。