CSP-S2024 游寄

D(-1)

晚上作业没写多少，好好休息了一下。

D1

上午考了 CSP-J，遇到了李汉成奆佬（bushi）。觉得 T4 比较难，想了半天，最后十来分钟才开始写暴力，最后只调出来了第一个点。预期 100+100+100+5=305。

中午去知春里地铁站附近的卫星厂吃了点东西。

下午继续考试。在开考之前我写了几个 .sh 文件用来快速地测试所有大样例。这次没有用熟悉的 vim，用了之前用地比较多的 gedit。

T1 是淼题。但是最开始看样例看成了第二大的数的个数，后来才想到是一个贪心。最后花了 <30\operatorname{min} 切掉了。

T2 第一问我想到了是要算出每辆车超速的区间，然后二分判断这一段中是否有测速仪。第二问是某种区间问题，转化为求所有测速仪构成的点集的一个最小子集使该点集能覆盖到所有在第一问中查出来的超速区间。我想不起来这种问题怎么做了，所以就口胡了一个对前缀和差分约束的做法，就是如果 [l,r] 中有一个点，那么 \operatorname{prefsum}_r - \operatorname{prefsum}_{l-1} \ge 1，可以考虑为从 l-1 号点有一条边权为 1 的边连向 r 号点，并在这个图上跑最长路。最开始写了一个基于 Dij 的算法，拿样例试了一下发现假了，所以就写了 SPFA。但是不巧 SPFA 炸了最后一组大样例。联系到这是 DAG，果断使用 dp，拿下了第二问。此时时间过去了 \approx 1\operatorname{hr}。

测试的时候意外发现第一问有错，全是倒数第二组大样例。于是又对着代码盯了半天，怀疑是浮点数精度有问题，把 eps 改了又改，最后发现是边界问题：如果超速区间的左端点要比进入道路的位置早，应该把左端点设为进入道路的位置。害我调了半天。这个故事告诉我们，我真的！太！菜！了！

过掉第二道题的所有大样例之后，时间已经过去了 1.5 \sim 2 \operatorname{hr}。开 T3。

T3 我怀疑是 dp，但我一直想不出来。最后打了个 20\operatorname{pts} 的暴力就收工了。

T4 没看懂题，随手交了个 RP++ 的代码，还过不了编译。我是真放弃了。

最后预期 100+100+20+0=220。

D2

不知道是哪位大神把代码加密协会（Code Cypher Foundation, CCF）下发的加密压缩文件解码了，拿洛谷的民间数据测试了一下。

T1 和 T3 都和预期一样。T2 T 了四个点，是由于没关流同步。希望 CCF 能保持一贯的用 jio 造数据的优良作风。

最后估分 100+60+20+0=180。应该能压线过一等线吧（

写在最后

我还是菜就多练（

打完就打完了，希望能 RP++吧

^\texttt{CSP-J}_\texttt{CSP-S} ~ \Large{\texttt{RP++}}

写在“写在最后”最后的写在最后

CCF 官方成绩出来了，出于人品 T2 没有炸。最后 100+100+20+0=220