自动搬运

查看原文

来自洛谷，原作者为

	nullqtr_pwp 我注意到有些人一直在做各种地方的cnoi题，但是并没有什么b用，可能是因为一直在舒适区里面舒服的卷，虐杀自己擅长的东西并获得成就感。

搬运于2025-08-24 22:44:19，当前版本为作者最后更新于2024-04-26 22:41:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

省流：披着个构造皮子的 dp 题。

讲课讲了这题，感觉很厉害啊。

注意到 $A_{i,j}=1$ 的点对 $(i,j)$ 可以改写成一张有向图上 $i\to j$ 的边，考虑把这张图建出来。那么 $\forall i,j:(A^k)_{i,j}=1$ 的意思就是存在一条路径，使得 $i$ 到 $j$ 经过不超过 $k$ 条边。现在我们就是要构造这张有向图上的非平凡边（$i\to i+1$ 都是给出的）。

评分标准告诉我们存在一种方案，$m\leq nf(k)$。$0.9\leq f(k)\leq 8$。大概边数要做到 $O(n)$，这其实很困难，但这引导我们去往最小化边数去思考。

$\bm{k=2}$ 怎么做？

显然就是分治：对于每个 $[l,r]$，$[l,mid-1)$ 都向 $mid$ 连边，$mid$ 都向 $(mid+1,r]$ 连边。分治解决 $[l,mid),(mid,r]$ 即可。这样的边数恰好满足 $m\leq nf(2)$。

$\bm{k=3}$ 怎么做？

注意到 $mid$ 是个很厉害的性质，然而只找一个有点亏，依旧考虑当前区间 $[l,r]$，我们可以找两个关键点 $a,b$，使得区间被划分为 $[l,a),(a,b),(b,r]$。我们考虑 $a,b$ 都往相邻的区间中的所有点都连边，并且连接边 $a\to b$，这样可以得到比猫树分治做法更优的解。

注意到这个关键点可以选不止一个，其实可以选任意 $t$ 个，设为 $p_1,p_2,\cdots,p_t$，此时被分割成的若干段区间内部都满足相同子结构性质。也就是说，$\forall i,(p_i,p_{i+1})$ 的区间的划分是递归进行的，相同子结构的问题（定义 $p_0=l-1,p_{t+1}=r+1$）

注意到要保证两两能跳到，因此 $p_1,p_2,\cdots,p_t$ 这些关键点之间两两都必须有边，此时会多产生 $\dfrac{t(t-1)}{2}$ 的代价。

$\bm{k>3}$ 怎么做？

注意到关键点之间两两需要保证在 $k-2$ 步之内可以互相抵达，这同样可以被归类为一个长度为 $t$，$K=k-2$ 的子结构。

算法设计

上面一车东西都是「在 $n$ 个点的图中，$k=t$ 时最少需要添加多少条边」的子结构，直接把这个写成 dp，记为 $f_{t,n}$。

转移按照 $k$ 从小往大进行，每次枚举一个长度 $n$，然后枚举关键点个数 $t$。

考虑关键点内部怎么划分。注意到我们要求中间划分出来的段尽量均摊，调整法理解一下就会发现这是对的，但是两边与中间的贡献是不平衡的，我们只能保证两边选出来的数量尽量一致，不能去考虑与中间的一致，之前在这里卡了半天。

因此考虑一个「辅助情况」：两边都划分为 $0$ 个，直接钦定 $p_1=l,p_t=r$，中间直接被划分为 $t-1$ 段。此时可以刻画出来每一段的长度，就是直接均摊。继承子结构的贡献之后，然后加上这一层关键点对两边区间的新边，以及关键点之间的边的数量。

然后你发现，枚举两边的点的个数相等为 $h$ 时，减去两侧的点之后，就是一个规模为 $n-h$ 的「辅助情况」的解。

这样容易将一层的 dp 做到 $O(n^2)$，总共 dp 的复杂度就是 $O(n^2k)$。

构造方案？直接由最后的 dp 值倒序进行整个 dp 过程，找到每个 dp 值是从哪里来的，输出每一次产生的新的贡献的边即可。

提交记录