专栏文章

题解：P14355 [集训队互测 2025] 封印

ccomplexor管理员
P14355题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min1ntvi
此快照首次捕获于
2025/12/01 19:06
3 个月前
此快照最后确认于
2025/12/01 19:06
3 个月前
查看原文

算法一

下文中“区间 ii” 指怪物 ii 或者区间 [li,ri][l_i,r_i]，称 wiw_i 为区间的权值。
首先考虑指数级算法。枚举集合 SS 表示最后权值计入答案的区间。设 L=min⁡i∈S{ri},R=max⁡i∈S{ri}L=\displaystyle\min_{i\in S}\{r_i\},R=\displaystyle\max_{i\in S}\{r_i\}。为了使 SS 合法，所有 L<li<RL<l_i< R 的区间在 [L,R][L,R] 内的部分均需被封印，且所有 SS 中的区间均需被完整封印，其余区间均可被完全放弃（即在 lil_i 被放弃）。
进一步地，可以认为 L<li<R<riL<l_i<R<r_i 的区间也被完整封印，因为如果大于 RR 的时刻出现超过 KK 个这种区间，那么它们也会使 R−1R-1 时刻不合法。
检查是否存在时刻被覆盖超过 KK 次即可。
时间复杂度 O(2nn)O(2^nn)，期望通过子任务 1。

算法二

先考虑所有区间权值均为 11 的情况。
上面的朴素算法提供了思路，最后计入答案的区间集合数量是指数级的，但集合对应的 [L,R][L,R] 很少。
枚举 [L,R][L,R]，区间可被分为六类：
  1. I\mathrm{I} 类：li≤L≤ri≤Rl_i\leq L\leq r_i\leq R；
  2. II\mathrm{II} 类：li≤L≤R<ril_i\leq L\leq R \lt r_i；
  3. III\mathrm{III} 类：L<li<ri≤RL<l_i\lt r_i\leq R；
  4. IV\mathrm{IV} 类：L<li<R<riL<l_i<R\lt r_i；
  5. V\mathrm{V} 类：li≥Rl_i\geq R；
  6. VI\mathrm{VI} 类：ri<Lr_i<L。
其中，III,IV\mathrm{III},\mathrm{IV} 类区间一定被完整封印，同时 III\mathrm{III} 类区间必须计入答案。除此之外，可以完整封印一些 I\mathrm{I} 类区间以使答案更大。
定义 [L,R][L,R] 合法当且仅当所有 III,IV\mathrm{III},\mathrm{IV} 类区间没有使得一个时刻被覆盖超过 KK 次，容易发现对于固定的 LL，合法的 RR 一定是 LL 开始的若干连续正整数。进一步，如果 [L,R1][L,R_1] 和 [L,R2][L,R_2] 均合法且 R1<R2R_1<R_2，那么 [L,R2][L,R_2] 对应答案一定不劣。证明如下：在 [L,R1][L,R_1] 最优答案中的 I\mathrm{I} 类区间集合 SS，那么 [L,R2][L,R_2] 相对于 [L,R1][L,R_1] 多出的 III,IV\mathrm{III},\mathrm{IV} 类区间都有 li≥R1l_i\geq R_1，所以它们和 SS 中的区间都不交，故在 [L,R2][L,R_2] 时选择 SS 中的所有区间也合法。
现在要考虑的 [L,R][L,R] 只有 O(n)O(n) 个，注意到 RR 随 LL 增大单调不减，故可以用尺取法加上线段树来 O(nlog⁡n)O(n\log n) 求出这些 [L,R][L,R]。
对于每个 [L,R][L,R]，显然取的 I\mathrm{I} 类区间按 rir_i 排序后一定是一个前缀。所以对于这 O(n)O(n) 个 [L,R][L,R]，分别将对应的 I\mathrm{I} 类区间按 rir_i 从小到大尝试加入即可。
时间复杂度 O(n2log⁡n)O(n^2\log n)，期望通过子任务 2。

算法三

算法二的瓶颈在于每次重新尝试加入 I\mathrm{I} 类区间，现在考虑在尺取过程中维护。尺取可以拆成 LL 右移和 RR 右移，下面分开考虑会对区间类别产生什么影响。
LL 右移：(a) I→VI\mathrm{I}\to \mathrm{VI}；(b) III→I\mathrm{III}\to\mathrm{I}；(c) IV→II\mathrm{IV}\to\mathrm{II}。
RR 右移：(d) II→I\mathrm{II}\to\mathrm{I}；(e) IV→III\mathrm{IV}\to\mathrm{III}；(f) V→IV\mathrm{V}\to\mathrm{IV}。
记答案中选取的 I\mathrm{I} 类区间集合为 SS，所有 III,IV\mathrm{III},\mathrm{IV} 类区间集合为 TT。
(a) 中如果被移除的 I\mathrm{I} 类区间如果在 SS 中，移除后显然最多再加入一个 I\mathrm{I} 类区间到 SS 中。用小根堆维护所有不在 SS 中的 I\mathrm{I} 类区间，尝试加入 rir_i 最小的那个即可。
(b)(c) 都可以看作是先删除了一个 li=Ll_i=L 的 TT 中区间。这其实和删除一个 SS 中的区间产生的影响类似，可以说明此时也只会再加入一个区间到 SS 中。对于 (b)，还要再加入一个 I\mathrm{I} 类区间。此时如果它的 rir_i 比 SS 中最大的 rr 小，将它加入 SS，然后若产生不合法则删去 SS 中 rr 最大的区间，这部分可以用大根堆维护 SS 中区间；否则加入小根堆，并尝试将堆顶加入 SS。
(d) 由于这个发生改变的区间满足 ri=Rr_i=R，所以不会将 SS 中的区间“顶替掉”。只要把它加入小根堆，并尝试加入当前 rir_i 最小的 I\mathrm{I} 类区间即可。
(e) 不会使 S,TS,T 产生任何改变只需要把这个区间权值计入答案即可。
(f) 会向 TT 中加入一个区间，上面算法二已经说明了不会影响 SS。
以上单步维护均为 O(log⁡n)O(\log n)，总时间复杂度 O(nlog⁡n)O(n\log n)，期望通过子任务 2,3。

算法四

现在考虑 wiw_i 没有特殊限制的情况，尝试扩展算法二。
尺取的正确性显然，区别在于现在不能按照 rir_i 排序了。一个自然的想法是按照 wiw_i 从大到小贪心加入，下面证明这是对的。
固定 [L,R][L,R]，设 I\mathrm{I} 类区间为 (l1,r1,w1),(l2,r2,w2),…,(lm,rm,wm)(w1≥w2≥⋯≥wm)(l_1,r_1,w_1),(l_2,r_2,w_2),\dots,(l_m,r_m,w_m)(w_1\geq w_2\geq\dots\geq w_m)。注意到这个结论和 Kruskal 最小生成树算法很类似（事实上，这本质上是因为二者都是拟阵），考虑类似的归纳证明：对于 1≤k≤m1\leq k\leq m，贪心加入前 kk 个区间后得到的集合 AkA_k 一定是某组最优解 SkS_k 的子集。
  1. k=0k=0 时 Ak=∅A_k=\varnothing 显然成立；
  2. 假设 k=ik=i 时成立，考虑向 AiA_i 中加入 (li+1,ri+1,wi+1)(l_{i+1},r_{i+1},w_{i+1}) 得到 Ai+1A_{i+1}，如果加入失败或加入成功且这个区间在 SiS_i 中，令 Si+1=SiS_{i+1}=S_i 即可说明此时命题成立。否则，考虑将第 i+1i+1 个区间加入 SiS_i 得到 Si+1S_{i+1}，此时 Si+1S_{i+1} 必然不合法。由于只保留 Si+1S_{i+1} 中编号不超过 i+1i+1 的区间合法（这是因为 i+1i+1 在贪心中成功加入了），而且此时被覆盖次数最多的时刻一定被覆盖恰好 K+1K+1 次，所以一定可以通过删除 Si+1S_{i+1} 中恰好一个编号大于 i+1i+1 的区间，使得 Si+1S_{i+1} 合法。由删除的区间的权值不超过 wi+1w_{i+1} 知删除后 Si+1S_{i+1} 的权值和不会比 SiS_i 小，故 Si+1S_{i+1} 也为一组最优解。
有了这个贪心，就可以类似算法二做到 O(n2log⁡n)O(n^2\log n)，期望通过子任务 1,2,4。
这个贪心也可以说明在 wi=1w_i=1 时，将 I\mathrm{I} 类区间以任意顺序尝试加入都是正确的。进一步，这也说明所有权值和最大的合法 SS 的区间个数相同且是所有合法方案中区间个数的最大值。

算法五

考虑 KK 比较小的情况，尝试扩展算法四。
注意到所有 I\mathrm{I} 区间，都覆盖 LL 或者右端点与 LL 重合，故算法四中计入答案的 I\mathrm{I} 类区间只有 O(K)O(K) 个。如果能找出这些区间的同时不遍历其它区间，就可以得到更优的复杂度。
设 limlim 为最小的被覆盖了 KK 次的时刻，容易发现此时可以加入的 I\mathrm{I} 类区间即为所有 ri≤limr_i\leq lim 的 I\mathrm{I} 类区间，这些区间中 wiw_i 最大的即为下一个加入答案的区间。
limlim 和所有 I\mathrm{I} 类区间容易用线段树维护，时间复杂度 O(nKlog⁡n)O(nK\log n)，期望通过子任务 1,2,4,5。

算法六

尝试结合算法三和算法四。还是考虑算法三中提到的六种情况。不妨设所有区间的权值互不相同。
(a) 即从 SS 中移除一个区间 ii。设 jj 为 wjw_j 最大的能加入 S∖{i}S\setminus\{i\} 的区间（显然 wj<wiw_j<w_i），下面说明 S∖{i}∪{j}S\setminus\{i\}\cup\{j\} 即为新的最优解：
考虑对比删去 ii 前后上面的贪心过程：
  1. 权值大于 wiw_i 的区间是否加入没有变化；
  2. 对于权值在 (wj,wi)(w_j,w_i) 中的区间，假设此时原来不在 SS 中的区间 kk 可以加入，设 SS 中所有权值小于 wjw_j 的区间集合为 AA，那么由于 j,k∉Sj,k\notin S，所以 ∀a∈A,ra<rj,ra<rk\forall a\in A,r_a<r_j,r_a<r_k，那么 j,kj,k 对 AA 中区间的限制等效，故 kk 也可加入 S∖{i}S\setminus\{i\}，与 jj 的最大性矛盾；
  3. 对于权值小于 wjw_j 的区间，由于删去的 ii 满足 ri=L−1r_i=L-1 是现在所有 I\mathrm{I} 类区间中最小的，故将 ii 替换成 jj 后限制更严，但由于 jj 能加入 S∖{i}S\setminus\{i\}，所以这部分区间是否加入也没有变化。
为了找到 jj 可以先找到最小的 limlim 满足时刻 limlim 被覆盖了 KK 次，那么 jj 即为 rj≤limr_j\leq lim 且 wjw_j 最大的 jj，容易用线段树维护（同算法五）。
(b)(c) 看作是先删除了一个 li=Ll_i=L 的 TT 中区间。这其实和删除一个 SS 中的区间产生的影响类似（可以看作删除 SS 中一个权值无穷大的区间），具体同上。对于 (b)(b)，还要再加入一个 I\mathrm{I} 类区间。设 jj 为 wjw_j 最小的从 S∪{i}S\cup\{i\} 删除后合法的区间（显然 wj≤wiw_j\leq w_i），那么下面类似 (a) 中说明 S∪{i}∖{j}S\cup\{i\}\setminus\{j\} 即为新的最优解：
考虑对比加入 ii 前后上面的贪心过程：
  1. 权值大于 wiw_i 的区间是否加入没有变化；
  2. 如果 j≠ij\neq i，则 wjw_j 成功加入；
  3. 对于权值在 (wj,wi)(w_j,w_i) 中的区间，原来在 SS 中的由 S∪{i}∖{j}S\cup\{i\}\setminus\{j\} 合法知它们仍然会加入，原来不在 SS 中的现在前面多了区间 ii，更不可能加入；
  4. 对于区间 jj，由最小性知每一个 k∈Sk\in S 且 wk<wjw_k<w_j 都要满足 rk<rjr_k<r_j，且设 mx=max⁡k∈S∧wk<wj{rk}mx=\max_{k\in S\wedge w_k<w_j}\{r_k\}，那么如果所选 I\mathrm{I} 类区间为 S∪{i}S\cup\{i\}，则 [mx,rj)[mx,r_j) 中有一个时刻被覆盖 K+1K+1 次，故可知此时 jj 不会加入；
  5. 对于权值小于 wjw_j 的区间，其中原来不在 SS 中的 kk，由 jj 最小性知 rk<rj,rk<rir_k<r_j,r_k<r_i，否则 S∪{i}∖{k}S\cup\{i\}\setminus\{k\} 合法。所以 i,ji,j 对 kk 的限制等效，故这样的 kk 肯定也不会加入。对于原来在 SS 中的 kk，由 S∪{i}∖{j}S\cup\{i\}\setminus\{j\} 合法知它们仍然会加入。
找 jj 同样可以先找到最大的 limlim 满足时刻 limlim 被覆盖了 K+1K+1 次，那么 jj 即为 rj>limr_j>lim 且 wjw_j 最小的 jj，容易用线段树维护（类似算法五）。
(d) 同 (b) 的加入。
(e) 和算法三中没有区别。
(f) 和算法三中没有区别。
所有线段树操作均为 O(log⁡n)O(\log n)，每次 L,RL,R 移动需要 O(1)O(1) 次线段树操作，总复杂度 O(nlog⁡n)O(n\log n)，期望通过所有子任务。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...