CSP-S 2024 游记
yiming564
·
·
生活·游记
\text{CSP-S 2024} 游记
作为一个高二的 \text{OIer}，除非今年能拿到 \text{NOI Au}，不然我就只能 \text{AFO} 了，因此今年几乎 100\% 是我的最后一年 \text{CSP-S}，谨以此文记录我最后一年的回忆。
\text{Day -6}
上午 vp 了 Public NOIP Round #6，赛时只做出 T1 T3，离 300 分的目标还是有点遥远了，结果赛后发现 T3 空间开小挂成 40 了。
下午本来报了信友队的模拟赛，结果一道都没有思路，模拟赛的样例解释也云里雾里的，解释不清，遂放弃。
如此水平，还是回去高考罢（
\text{Day -2}
vp 了 Public NOIP Round #1，打出了历史最低：100 + 0 + 0 + 0。
居然只做出了一道大模拟。。。
第一次做概率题，差点给我做出来了，但后来发现化简到最后一步，有一个式子不会算：
我没学过数学，我只会 $O(k)$ 硬算，然后时间瓶颈。
当然如果我能把分打满还是有一点分的。
但我当时使用考场的 $\text{NOI Linux}$ 没有 vscode 插件，拿垃圾 GDB 调试不出来，我都担心考试时会不会因为没有 vscode 爆零。
```
gdb ./program -tui
```
加上这个选项，让 GDB 给你提供仅存的一点图形化界面。
## $\text{Day -1}
复习了一下 \text{ACAM}，但我要考的好像是 \text{CSP}。
\text{Day 0}
复习了一下网络流，计划再学一下分数规划。
upd. 最后也没有学。
\text{Day 1}
早上打了几个图论板子，下午提前 \text{35 min} 到了学校。
进机房打开 \text{NOI Linux} 敲了缺省源并配置了字体和 GDB，然后在开考前 \text{2 min} 突然发现 vscode 可用，谢天谢地！！！
推测原因可能是我把 vscode 一直放在后台挂着，vscode 一直在尝试下载 C++ 插件依赖只不过没有网，而下发文件 / 密码条时短暂联网刚好让 vscode 有机会下载下来，即使只有十几秒钟的时间。
开考，T1 \text{5 min} 速通，排序 + 贪心水题，感觉今年有点简单啊。
T2 观察了一会题，发现应该先算超速的区间，然后花了 \text{20+ min} 大力分讨终于处理出了超速区间，然后算超速车辆是容易的，算无用的摄像头一开始想了个假做法，以为每辆车都会被第一个摄像头拍下来，因此对于每辆超速的车辆，给第一个能拍他的摄像头贡献 + 1，最后无贡献的摄像头就是无用的摄像头。
写了一会发现样例 2 错了，想了一会没思路，遂转战 T3。
T3 看了一会感觉是一个一眼 \text{DP}，结果推了一个错的转移，没有什么头绪。
转战 T2，想到这其实是用最少的点来切割最多的区间的问题，想起来这应该是一个贪心，但我没有做过这种板子，硬着头皮现推。
区间启发式合并？不见得。
按端点排序？哦？好像按照右端点排序可行！
写完发现已经考了 \text{1h}，目前期望得分 100 + 100 + 0 + 0 = \text{200 pts}。
看了看 T4，怎么一股概率的味道？不会不会，专攻 T3 吧，\text{300 pts} 作为最后一场 \text{CSP} 的战绩也还算可以。
T3 手膜了一下样例 1 的第三组数据，发现自己是少考虑了 \textcolor{blue}{5}\textcolor{red}{2}\textcolor{blue}{56}\textcolor{red}{4} 这种情况的 \text{5 - 5} 的贡献，因此大胆地重构 \text{DP} 状态 f_{i, 0/1}，最终写出了 O(n) 转移 f_{i, 0}，O(n) 转移 f_{i, 1} 的一个 \text{DP} 方程（埋下伏笔）。
此时已经考了 \text{3h}，别问，问就是 \text{DP} 推的比较曲折。
然后推转移的过程中就一直在想着单调队列，于是马上开始优化，结果最后发现自己其实只需要维护最大值就可以了。
终于，在考试结束前 \text{20 min} 前写完了，测测大样例！
啊？？？挂了？？？
在考试结束前 \text{10 min} 我发现，这是因为我的 f_{i, 1} 的朴素转移推的太烦，导致我实际上需要维护最邻近位置和次邻近位置以及两者的最优转移，遂崩溃，交了没有优化的 \text{50 pts} 朴素的版本。
结束力！100 + 100 + 50 + 0，250 的收场，多少有点讽刺了。
事已至此，祈祷不要挂分吧。