题解：AT_agc046_e [AGC046E] Permutation Cover

Cadmus · 2026-01-21 14:46:21 · 题解

本题解在写作完成后使用 DeepSeek 进行了润色。

题目解析与算法构建

本题解将从必要条件的判定入手，逐步推导至基于区间构造的优化算法。

1. 有解条件的判定

首先，我们需要寻找问题有解的必要条件。直观上，不同数字的出现次数之差不应过大。

考虑任意两个数字 x 和 y，x 所在的每一个排列中至少包含一个 y，而 y 只能与左右最近的 x 处于同一个排列中。基于此性质，必须满足：a_x \le 2a_y 当满足该限制时，我们可以通过以下策略构造合法序列：设出现次数取到最小值的集合为 S，其余数的集合为 T，构造序列开头为 TST。此时，剩余部分的出现次数关系仍然合法，可以继续递归构造。结论：有解的充要条件为 2\min a_i \ge \max a_i。

2. 朴素思路与瓶颈

若采用字典序逐位填数的策略，我们需要进行 nk 次有解性判定（其中 n=\sum a_i）。

假设已填好的前缀为 [1,p]，此时剩余数字的分布会对后续构造产生复杂影响。由于数据范围较小，粗略估计此时很难找到简洁的 O(1) 或 O(n) 条件来快速判断是否有解。

3. 优化策略：前缀构造与区间模型

核心思想：考虑填入一段前缀后，使剩余数字的出现次数满足上述合法条件（2\min \ge \max），进而直接复用之前的构造方案。直观推测填入的前缀长度不会太长，这为优化提供了可能。

我们可以建立一个模型来描述排列对应的区间：

从序列开头开始，每次贪心地选择能拼接且右端点最靠右的区间；
将所有有交集的区间合并为连通块。

此时，填入的前缀即为包含位置 p 的连通块的后缀。

显然，该连通关系构成的图是一条链。考虑连通块最右侧的三个区间 [l_1,r_1], [l_2,r_2], [l_3,r_3]（满足 l_1 < l_2 < l_3）：

若 p \le r_1，则将 (r_1,r_3] 这一段切断并形成新的连通块是完全可行的。

推论：填入的前缀至多涉及两个区间。

4. 情况分类与枚举

基于上述推论，我们只需要考虑以下三种情况：

只填一个区间 [l_1,r_1]；
填两个区间 [l_1,r_1],[l_2,r_2]，且 l_2 > p；
填两个区间 [l_1,r_1],[l_2,r_2]，且 l_2 \le p。

对于情况 1，直接枚举区间即可。

对于情况 2 和 3，枚举 [l_1,r_1] 和 [l_2,r_2] 后，(p,r_1] 和 [l_2,r_2] 的内容是确定的。

以情况 2 为例：

这相当于从 (p,r_1] 填入的数中选出 l_2-p-1 个数放置在 (p,l_2)。
这意味着选出的数将消耗两次出现次数，其余数消耗一次。
贪心策略：显然应优先选择剩余出现次数最多的数填两次。
在枚举 l_2 时，可以顺便维护填数状态，该部分复杂度为 \mathcal O(k^2)。

5. 进一步优化与复杂度分析

我们可以通过考虑边界情况来减少枚举量。设 [1,p] 中未被排列覆盖的后缀为 [q,p]，则必须满足 [q,p] \subseteq [l_1,r_1]。对于后两种情况，若 l_1 < q，显然可以将区间整体右移。因此，我们只需要判断 l_1=q 的情况。

优化效果：结合排序，复杂度降为 \mathcal O(k\log n)；精细实现可达 \mathcal O(k)。
此时，情况 3 的检查逻辑可以与情况 1 合并。

总结

通过上述分析与优化，算法的总时间复杂度为 \mathcal O(nk^2)。