CSP-S 2024 游记

上午

上午打板+睡觉。希望能比去年有进步。

下午

下午进考场，好像来早了，一直没见到带考的老师，于是自己先进去了。

鼠标不好用，滚轮坏了，申请换一个。结果更不好用，过一会就卡一下。于是换了个位置，鼠标滚轮还是坏的，将就着用吧。

开题。T1 是一个简单的贪心，决策包容性是易证的。T2 是一个二分套上区间选点，是经典的模型，并不困难。一个小时左右就切了，而且特别顺利，基本上都是一发过。感觉良好，去上个厕所。

T2 本地跑了 1.8 秒，看了半天哪里写假了，因为样例只有 2000 左右。最后发现读入就用了 1.4 秒，这下知道了。

T3 看起来很像 DP，直接考虑设状态。发现单步 DP 不能优化，考虑每次钦定最后一个红点位置。然后发现好像递推时如果红点连续处理蓝点贡献会出事，然后想想想。过了一会考虑只计算有贡献的点，但是好像还是没有解决瓶颈。之后继续想想想。

去上个厕所。回来猜了个结论，好像也不是很好做。继续想想想，忽然发现一个很弱智的结论，可以把连续一段相同数字缩成一个。然后把结论套上去，好像红点连续还是处理不了，但是感觉可以证明不影响，先写个 O(n^2)，写写写，一发通过了小样例，感觉良好。

直接测大样例，跑了一分钟，结果一个都没有对。有点急了，T1 T2 太没有区分度了，T3 现在连 O(n^2) 都没写出来，怕不是要垫底了。想想想，上个厕所冷静一下。

回来发现不影响的结论假了，因为红点位置不一样。轻度破防，想想想。发现可以在红点之间转移时翻转处理一下，好像很对，写写写。测大样例，上个厕所。

上完厕所回来，跑出来了，居然过了！当时真的非常激动，差点把鼠标甩出去。然后发生了一件特别抽象的事情，就是我发现我的代码假了，好想有一种情况没有处理。凝固了。

后来补了一个边界判定，还是过了大样例。这下真不知道对不对了。开始优化，先写了一个树状数组，然后发现可以线性。大样例 0.04 秒。玄学做法，感觉很危险。

T4 是个什么东西，暴力都不好写，遂没写。

出考场，和初中同学聊天。碰到 yyz，yyz 好像过了 T3。完了好多人过了 T1 T2 T3，感觉要成为 HB 倒数第一了。可是不知怎么，心情异常平静。