CSP2024游寄

· · 生活·游记

初赛

过了。

复赛

下午 1 点左右看到了上午的 T4，但是我咋不会啊/ll。

进场的时候有点紧张，但是开考后就好些了。

上来发现 A 是简单的，B 是不难的，但还是先把所有题都看了一遍。但是发现 D 很长，所以还是先把 A 写了。本来想猜个结论，但最后还是选择了排个序再双指针扫。14:45 左右写完了 A。

之后稍微理了一下 B 的思路，发现就是简单的求交然后区间覆盖，后者是个经典贪心问题，很快就写完了。然后我才意识到他给的是距离，我的末速度算的完全是错的……但是我没学过高中物理啊啊啊啊啊。然后连续记错公式（忘记乘 t 了，搞得十分慌张。好在用题目给的公式，写了写还是在 15:30 左右过了大样例。

之后发现 C 很难。感觉这个贡献完全不会算啊。但是很快想到了个 O(nv^2) dp，然后发现这个必有一维是 a_i，然后变成了 O(nv) 的，然后发现这个只有 f_{a_{i-1}} 要特殊更新，然后变成了 O(n+v) 的。写了下发现过不了大样例，于是写了个比这份代码难写不少的暴力，然后陷入调试。仔细观察发现贡献搞错了，改了改就过大样例了，这时大约是 16:15。

之后发现 D 很难。坏了我咋啥做法都不会。感觉越想头越大，于是决定先写个 O(nmpolylog) 的暴力。写了写发现写的很难受。最后在 17:20 左右发现值域是 \log 的，然后直接在每个节点记录每个 a_i 的和就可以轻松转移，然后每个 2 的幂重构即可，复杂度为 O(tn\log^2n)。写的很难受，调的也很难受，还好最后写了出来，期望得分 [68,76]。

最后期望得分 100+100+100+[68,76]，说实话打的不错，但感觉这场出的还是太幽默了。