noip 2025

RainWetPeopleStart · 2025-12-05 18:59:08 · 生活·游记

先看 T1 发现一点不会，不过很快注意到只会选 x+y 最小的和若干个 x，就做完了，此时大概 20m。

再看 T2，发现不是特别好做，想了想发现可以钦定第一个买不到的位置，使用组合数 + 双指针就可以 O(n^2)。因为组合意义转化做的比较好，所以规避了范德蒙德卷积。此时不到 80m。

还有超过 3h，但是 CSP-S 2025，所以不敢放松，直接开 T3。

一开始以为 T3 直接 DP 就能 O(nm^2)，后来一直尝试优化，最后写的时候发现是 O(n^3)，写完只有 2h 出头了。

感觉可能会崩。选择继续做 T3，尝试钦定继承哪个儿子的 mex，发现每个点的贡献大概是一个链加的形式，可以做到 O(nm^2)，此时还剩 1.5h 左右。

开 T4，做出了一个 O(n^2+nq\sqrt n) 做法，拼上 AB 后有 45，写完后剩 40m。

感觉这个分还行，而且 T3 不特别会，决定检查和给 T4 卡常。

估分：100+100+76+45=321。