专栏文章

题解：P11983 [JOIST 2025] 展览会 3 / Exhibition 3（暂无数据）

PPetit_Souris
P11983题解参与者 5已保存评论 5

文章操作

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

当前评论
5 条
当前快照
1 份
快照标识符
@mipgrgij
此快照首次捕获于
2025/12/03 11:45
3 个月前
此快照最后确认于
2025/12/03 11:45
3 个月前
查看原文
难度已经远比我能独立做出的题高了。不过回顾一下，几个 trick 的叠加也并非无迹可寻。好题，值得学习。

Hint 1：你能编出一个多项式复杂度做法吗？

看到字典序想到逐位贪心。我们考虑从大到小枚举 vv，把 vv 放在尽可能靠前的位置。
对于每个 vv，我们按顺序尝试加入所有还没被覆盖的区间。如果加入之后，覆盖这些区间需要的点数 C≤cntvC\le cnt_v 就是合法的。
判断最小覆盖是一个经典贪心问题，每次选择右端点最小的区间，在其右端点处放一个点即可。

Hint 2：每次选出的区间形态如何？

显然是一段前缀，加上一些零散的区间。这看起来是一句废话，但是我们考虑那一段前缀后面一个位置，他不能选说明加入他之后 C>cntvC>cnt_v 了，而由于 CC 的变化是连续的，这说明这个前缀加入之后 C=cntvC=cnt_v。
这样后面的区间就必须满足加入之后，不会增加最小覆盖点数。

Hint 3：如何找到这个前缀？直接二分为什么不可行？

二分意味着我们花了至少序列总长的代价去删除一些元素。因此如果每次只删一个复杂度就起飞了。
但是我们可以考虑先倍增。找到最大的 2k2^k 满足删除前 2k2^k 个合法，接下来再在 [2k,2k+1)[2^k,2^{k+1}) 内二分，每次暴力跑上面的贪心检验。这样我们就用 O(clog⁡2c)\mathcal O(c\log ^2 c) 的代价删除了 cc 个元素。总共只删除 mm 个元素，因此均摊复杂度正确。

Hint 4：如何判断加入一个区间之后是否需要多一个点覆盖他？

这个结论应该是经典的，可惜我还没见过这样做的题目。有同学知道类似的题目可以在评论区告知我。/kt
我们考虑正反做两遍贪心，求出每个点所在的范围 [tlj,trj][tl_j,tr_j]。如果 [Li,Ri][L_i,R_i] 和某一个 [tlj,trj][tl_j,tr_j] 有交，那么可以调整 jj 使得不增加新点。反之，需要增加一个点。

Hint 5：一个区间加入之后，tl,trtl,tr 会发生怎样的变化？

以 trtr 为例。我们找到 RiR_i 右边第一个 trjtr_j，然后一路向右，如果左端点在前面的，对应的最小右端点不到 trjtr_j 就会一路修改下去。
这样做的修改次数实际上是 O(c)\mathcal O(c) 次，因为 trtr 相当于保留一些区间的右端点，而一个右端点存活的时间是一段区间。

Hint 6：利用上面的性质编出正解。

找到前缀后，我们只需要快速找出编号最小的，可以加入的区间。
一个简单的想法是用一个小根堆维护所有的编号。这样我们每次对于一个 trjtr_j，去加入所有和他有交的区间，并贪心跑。
但是这样有一个严重的问题就是，一个区间可能会被放进去很多遍，就退化成 O(nm)\mathcal O(nm) 了。解决方案也很简单：把所有包含某个 [tlj,trj][tl_j,tr_j] 的 [Li,Ri][L_i,R_i] 都提前拿出来，这样剩下的区间至多放进去两遍。
找有交的最小编号可以分讨二维偏序关系，用两个线段树维护。
最后整理一下这部分的过程：
  • 先得到 tl,trtl,tr，对于每个 [tlj,trj][tl_j,tr_j]，先把所有包含他的，还未使用过的区间拎出来标记上。
  • 接下来，对于每个 [tlj,trj][tl_j,tr_j]，找到与其有交的最小编号，加入小根堆。
  • 每次取出最小的编号，加入答案。并且重新松弛对应的 jj，找到新的最小值。
最终时间复杂度为 O(nlog⁡2n)\mathcal O(n\log^2 n)，可以通过预处理排序做到 O(nlog⁡n)\mathcal O(n\log n)。
实现上细节比较多，一定要理清楚再开始写，写完一部分 debug 掉对应的问题。参考代码。

评论

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

正在加载评论...