题解：P8984 [北大集训 2021] 末日魔法少女计划

· · 题解

省流：披着个构造皮子的 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 值是从哪里来的，输出每一次产生的新的贡献的边即可。

提交记录