再记一次人类智慧

· · 算法·理论

妙妙题。

给 n 种物品，每种有体积 a_i 和价值 b_i。每种物品有无限个。

$n,m \le 10^5$，值域 $10^{12}$。 --- 首先给一个场上糊的神必做法。 物品排序之后搞前缀和，然后二分一个当前会购买的东西，二分一个会连续购买几个。不断二分。 有人说可以搞一个 选、不选、选、不选 这样的序列卡到 $O(mn\log n)$，实际上这样值域增长速度是 $2^n$ 的，或者说，发现每跳过一个物品不选（即将一个连续购买的段断开）则物品体积会减少一半，因为跳过的物品体积必大于之后所有选的物品的体积和。 然后就是 $O(m\log n\log V)$。 --- optimize_2：fzc 讲讲，fzc 怎么做的。 optimize_2：你玩原神吗你玩原神吗你玩原神吗？【数据删除】我不能构造一个就是选一个不选一个的数据，给你卡到嗯欸呣劳格嗯，【数据删除】我要申诉取消成绩，这数据脚造的，cdx 真的不会造数据。 optimize_2：啊？ optimize_2：什么后面选的和？ optimize_2：那就是一个什么，斐波那契数列，你知不知道斐波那契数列的增长速度是什么来着。啊你不知道，很菜很菜。 optimize_2：那你说是什么，啊二的嗯次方，不管了反正都增长很快就是了，它值域多少来着。 optimize_2：【数据删除】。 optimize_2：我算一下能不能卡掉。 optimize_2：那大概就是多少，欸呣劳格嗯劳格值域，是吧。 optimize_2：hwy 你场上过没过，你理解了没有，就他那个二分。 optimize_2：那你很菜很菜。 optimize_2：我【数据删除】平衡树【数据删除】是嗯劳格嗯劳格值域，遗憾的，卡不掉。 optimize_2：我急了，你是不是开了，我【数据删除】场上写了 250 行 fhq-treap，我写的时候感觉欸场上就我会 B，欸没人会 fhq，这波稳赢，我短时赛比你们长时赛还高。 （前情提要：O2 因为前一晚 CF 导致的睡过头，原来 4h 的模拟赛不得不在不到 2h 内打完。还是很高就是了。） optimize_2：然后我一看榜，【数据删除】的十九个人过 B，我当时就【数据删除】想不通，【数据删除】你们一个个都会 fhq 还都能写出那么妙的实现啊？？ optimize_2：我【数据删除】这个二分。你敢信吗这个二分居然卡不掉，我【数据删除】。 optimize_2：这样好不好。我们匹配一下代码里有 `mid` 这个词就取消成绩好不好。这不公平的，就我写了平衡树，居然和你们一个分。 （过了一会） optimize_2：这个完美诠释了什么，前面忘了， Stop learning useless algorithms, go and solve some problems, learn how to use binary search，后面忘了。 optimize_2：完了数据结构学傻了，fhqtreap 是一款由（后面省略） （过了一会） optimize_2：二分二分二分二分二分二分。要不给你们仁慈一点，给两分怎么样。 --- 也是妙妙做法。 先物品排序。 将所有人一起搞，统统塞进一棵 fhq-treap 里面。 然后发现从大到小枚举物品，考虑将 treap 砍断切开剁碎，切成装得下该物品和装不下两部分。 然后装得下的部分人都会拿这个物品，但是发现这部分人拿了之后值域和拿不下的人那棵树的值域有重合没法合并。 所以这才是妙妙题。 改为切成三部分，设当前物品体积为 $v$，则切成 $[0,v)$、$[v,2v)$、$[2v,\inf)$ 三份，第一份不管，第三份打一个减体积加答案的 `lazytag` 直接和第一份合并，第二份暴力 $-v$ 暴力加答案暴力插入。 考虑这为什么是对的。 因为暴力插入的时候区间在 $[v,2v)$，那么 $-v$ 之后大小至少减少一半，因此每个人至多暴力插入 $\log V$ 次，总时间很不幸的是 $O(n\log m\log V)$。 --- 最终结果显而易见。两次二分 106ms，fhq 327ms。 今日胜负：optimize_2 完败。