浅谈趣多多二分（Sugar Town Binary）——暴力而玄学的分治算法

· · 算法·理论

关于名字

该算法是由老鼠药在 2024/10/21 的联合考试中以为在打 T4 正解时无意间发明的胃酸，后由糖胶著命名为趣多多算法。

干什么？？！！

骗分，当且仅当多组询问答案具有单调性且能在接受的复杂度内二分多个询问。

注意到答案值域很小或答案种类不多时非常有效。

算法过程

  1. 尝试写暴力二分
  2. 发现二分复杂度太高
  3. 发现可以多个询问一起二分
  4. 尝试写整体二分
  5. 发现由于多个询问一起二分的算法与询问个数无关，复杂度是伪的
  6. 发现数据强度不高
  7. 尝试调试完
  8. 发现交上去能骗取 \frac{998224353}{1000000007}\times 100 分

设多个询问一起二分的算法复杂度为 O(n)，答案个数为 k，则整个算法时间复杂度为 O(nk\log q)，但实际并不容易跑满上界。

例题

CF1920F2 Smooth Sailing （Hard Version）（联合考试全真模拟 NOIP 特供版）

联合考试全真模拟 NOIP 特供版条件：n,m\le500

注意到简单版本我们有一个做法，二分答案 mid，把距离火山小于等于 mid 的地方设为不可达，然后再求从岛屿是否能到达边界。

尝试嗯套到该题硬版，多个询问一起 \operatorname{check}()，可以得到一个 O(nm) 的 \operatorname{check}()，注意到答案不超过 \max(n,m)，于是按整体二分的写法写，可以得到一个 O(n^3) 的算法，根据常数和细节可以得到 92\~~100 的好分数。