警惕 OI 中的多测陷阱

APJifengc · 2024-03-15 20:24:55 · 个人记录

研究了半天为啥我省选 D1T2 为啥根本跑不动后，终于发现了 OI 的险恶。

因为我并不是很会压缩 Trie 怎么快速计算一条链上的 DP 值，因为有个恶心的卡不卡下界的 bool，于是我就直接把卡下界的单独拿出来算，不卡下界的再压缩一下，这样就能 O(k (n + k)) 了，怎么样，是不是看起来很不错！

数据：T = 500000, n = 1, k = 120，你的算法的复杂度是 O(Tk^2) 啦！

简直感动的我要哭了。

还有 D2T1 我写的 O(2^{2n}) 加特殊性质 A（别问我怎么菜到连 100 都不会，我写完这个已经过去两小时了我不敢再浪费时间想怎么拿剩下 20 分了qwq），我没判断 \sum 2^n 而是直接判断的 n 来分辨子任务，然后呢，数据反手给我塞了 T 组 n \le 11，导致后面的点直接给我干成 O(T2^{2n}) 了，妈的跟你爆了。

唉，人间险恶啊。祝大家身体健康，万事如意，谢谢大家。