专栏文章

胸和钥匙 无敌做法

PPosVII
P8339题解参与者 7已保存评论 6

文章操作

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

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

前言

upd: bitset 做法假了，改成根号分治了。
[AHOI2022] 钥匙
有朋友说看不懂，那我修改下文风。这个新文风我是煮了又煮，希望大家喜欢喵喵！！
AHOI 的大师出的题，果然是相当的规范！我很喜欢哈！好题难得！大家一定要珍惜咩！
嘴巴一个不需要对钥匙数量限制的做法咩。需要使用到根号分治咩。

做法

为了表达方便，我们设每种钥匙数量的最大值为 cc 咩。
考虑到此类信息的合并是困难的，抛弃常规的 O(log⁡n)O(\log n) 或 O(n)O(\sqrt{n}) 次合并的做法。使用点分治或启发式合并将最终的路径划成两半咩。
每次询问 (x,y)(x,y) 变成了 (x,rt)(x,rt) 与 (rt,y)(rt,y) 的过程，考虑这种括号合并的问题在序列上分治的时候是怎么处理的咩：
记录 (x,rt)(x,rt) 的答案及剩下的钥匙数量，记录 (rt,y)(rt,y) 的答案及剩下的胸数量，对于每种颜色，取剩下的钥匙和胸的较小值计入答案即可咩。
那么如此，考虑如何维护两者的较小值。一种比较显然的方法是，直接对于每种颜色算贡献。
但是这样的话复杂度仍然是 O(n2log⁡n)O(n^2 \log n) 的咩！
考虑优化，可以使用经典的根号分治套路，设阈值为 BB 咩：
  • i≤Bi \leq B，使用标算方法做/特判，复杂度 O(Bnlog⁡n)O(Bn \log n) 咩。
  • i≥Bi \ge B，使用上述方法做，复杂度 O(n2Blog⁡n)O(\frac{n^2}{B} \log n) 咩。
B=nB = \sqrt{n} 时最优，复杂度为 O(nnlog⁡n)O(n \sqrt{n} \log n)，很抽象吧咩咩咩咩咩咩咩咩咩咩！

代码

代码就不放到这里了咩！大家自己咩一咩咩！
咩咩咩咩咩咩咩咩咩咩！咩咩咩咩咩咩咩咩咩咩！咩咩咩咩咩咩咩咩咩咩！咩咩咩咩咩咩咩咩咩咩！咩咩咩咩咩咩咩咩咩咩！咩咩咩咩咩咩咩咩咩咩！

评论

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

正在加载评论...