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]$，说实话打的不错，但感觉这场出的还是太幽默了。