CSP-S2024 游记

· · 生活·游记

看 T1，一眼不会，手模一下样例，这不简单题，整个桶扫一遍就行，几分钟敲完过掉大样例。

接着看 T2，怎么出物理题？思考一下发现可以算出每个车超速区间，然后直接平凡贪心就行。手玩了一下贪心觉得没啥问题就开写了，写完就过大样例了。

接着看 T3，平方 dp 不难得到，那优化不是直接线段树开码，写完就又过了所有大样例。最后一个大样例跑 0.3s，自信了。

还不到一个小时。

接着仔细思考 T4，考虑在完全二叉树上维护答案，pushup 维护一个确定点的桶和不确定点的桶做统计就好了。复杂度 O(Tn\log^2 n)，视常数感觉有 60-76。开写，调题，过样例，t=2 就要跑 1s，卡常数卡到 500ms，可能能多拿 8 分，又想了想怎么优化，不会了。

把代码拉下来检查，ulimit -v 和 -fsanitize=address,undefined 都试过。突然发现 t3 大样例有点水。自己写了个 gen 造了 t=10,n=2\times 10^5，代码跑了 1.4s，改了改跑 1.0s 出头，但是来不及就先交了。

如果机子比较快是 100，慢点就是 60 了。

估：100+100+[60,100]+[60,68]=[320,368]