CSP-S 2024

不知道 ~x 是干啥的，丢了 \mathcal O(1) 分。又没上 90，乐。两年的 \sum (90 - \text{myscore}) = 1.5。

5 分钟签完了 T1，拿到出题人送的 100 分。

花了很长时间才看明白 T2 题面，没上过高中物理不知道加速度导致的 /cf

速度不超过 V 的位置肯定是一个区间，第一问直接前缀和就好；第二问相当于，一个 01 序列，选择最少的 1 使得每个区间里至少有 1 个 1。

这个题（upd：abc216g）我明确记得我是看过的——我记得题解都是差分约束，还有一个帖子说它是【种树】的多倍经验。【种树】是我没做过的超经典题之一，差分约束也忘了咋写，急急急急急急。后来想了个按照 r 排序的贪心，感觉很对啊！直接开写。

首先写完了第一问，给定初末速度加速度算位移竟然一遍就写对了，还是抄公式舒服。过了样例之后我把代码拖出虚拟机备份，结果虚拟机直接卡爆了。找了工作人员来处理，还好 vs code 自动保存，我的代码没丢。

然后写第二问，一遍就过了所有大样例，很好啊！搞完这些过了大概 50min，优势在我。

看完 T3 立刻会了 \mathcal O(n^2) DP，想了一下发现直接线段树就对了，这么水的。10min 写完了暴力 DP，10min 写完了线段树，光速过了这题。

前 3 个题用了 1 小时 17 分钟，怎么能不赢！

T4 有非常多的部分分，这对我的策略选择造成了影响。16 分的 A 性质很简单，但我决定还是先思考正解，最后再拼暴力。

大概在 1h 45min 的时候如会了一个 \mathcal O(n \log n) 的 DP，中途假了很多次。打了一个补丁后复杂度变成了 \mathcal O(n \log^2 n)，但是好在没再假了。在 2h50min 时过了所有大样例，但是只能拿 [68,76] 分。

于是我又要进行策略的选择，最终我选择了保守的打法，去写了 T2，T3 的拍子，万幸什么都没拍出来。思考后发现 T4 在动态加点的过程中可以对左右儿子分讨，其另一侧儿子都只有一个位置有值。对于原本的 20 位 bool 数组可以直接压进一个变量，最终砍掉一个 \log。

这时只有 30min 不到了，但我没有任何压力了，直接开写。比较遗憾的是最后没有时间调了，只能遗憾离场。

估分 100+100+100+[68,76] = [368,376]，希望别挂分吧。