CSPS-2024 游记与反思

赛时情况

开场先看T1,10min敲完。测一下大样例，挂了。

原地坐牢调试，20min内对着自己20行的代码找不出错。

再读一遍题目，发现把 最小值 看成了 最大值 。

再花10min改正，过了所有样例。

这可能是一个意义不明的预示……

接着开T2,发现这个问题对于 a \geq 0 至少是简单的：车只会越跑越快，如果超速，一定会被最后一个测速仪发现，同时其他测速仪也是无用的。先实现一个 check(i,j) 来判断第 i 辆车是否会被第 j 个测速仪判为超速。为了避免浮点误差，可以计算第 i 辆车在第 j 个测速仪处瞬时速度的平方。

特判掉 d_i > p_m 的情况后通过了对应的性质A,B的样例。本着暴力打满的原则先去看T3。

为什么没有一鼓作气地投入思考呢……

此时，时间刚过去一个小时。

读完一遍T3的题后发现一个显然的暴力：会影响此后答案的只有当下的最后一个蓝色数和红色数。于是可以实现一个 \mathcal{O}(nV^2) 的暴力dp，发现这只有35分，不可接受。

发现当我们决策完位置 i 时，a_i 必定是最后一个蓝色数或红色数，于是dp时只需记录 a_i 是蓝色/红色以及另一颜色的最后一个数，复杂度降为 \mathcal{O}(nV) ，有65分，暂时满意。

你就不能再多思考几步吗？

此时，两个小时过去了。

回过头看T2，发现对于 a < 0 ，也有超速的位置范围是一段连续区间。对于每一辆车，可以直接分类讨论 a 的正负，一发二分找出区间 [L,R] 满足其间的测速仪都能测出超速。找出区间后，第二问就成为了经典贪心，码码码。

贪心挂了一次，终于在三小时时过了T2的大样例。

多少时间被浪费了……

最后一小时，开始匆忙地打T4暴力。\mathcal{O}(2^{2n}) 是简单的，只要依次枚举判断即可……

我怎么不会写 check?

发现T4是不可做题，回去继续思考T3。

思考不出来。

结束了。

总结分析

T3挂了15pts,成为了 250，原因至今未知。

发现自己离T3正解只差了dp转移的确定性上，当我认为状态数为 \mathcal{O}(nV) ，想着优化状态设计时，为何没有发现一些转移根本不必存在呢？

还有，读错题这种事，再也不能发生了。