CSPJ/S2024 游记

Day 0

2230 上床睡觉，保障精神状态正常。

Day 1

早上 0630 起床，0740 到了考点门口在车上再睡了一会，0810 左右进了学校。似乎是 GD 考点增加了的缘故，尽管今年的报名人数显著增加，但明显可以感觉到考点的人流比起往年减少了许多。一些往年总是能见到的朋友大概也是在别的考点参赛了，没能见面。在考场门外见到了同机房的几个同学，但没怎么交流。

上午是 J 组，考试时间是 0830-1200。经过这么长时间的准备，我还是比较有信心的，所以上了个厕所就进考场了。

T1 是简单的语法题，但是写完之后发现写复杂了，不过也只多了几十个字符，就没管。T2 是简单的模拟题，很快就写完了。然后我便看向 T3，第一眼感觉像是完全背包，然后就在这个基础上想了几十分钟，感觉可以就开始写了。大概 0920 的时候发现复杂度不对，一时没什么想法，于是就先看 T4 了。读完 T4 的题之后，T4 是没有想法，但是突然发觉 T3 可以直接贪心，于是就去写 T3 了。写完大概是 1000。

对着 T4 想了一段时间，1010 的时候想到了图论建模，然后又完善了一下，1030 发现还有问题，最后 1040 才开始写。最后感觉时间复杂度假了，但是时间已经不够了，只能希望调出来还能拿点分，结果最后也没调出来。

考完之后听同学说是 DP，我们机房最后也只有一个人做出来了，洛谷评分居然是蓝题，出乎意料，这大概是最后一次考 J 组了，也没能 AK。

估分 100+100+100+0=300。

中午大家一起吃了个饭，讨论了一下，开了个钟点房午睡，准备下午的比赛。

下午的比赛在 1430-1830，1350 的时候起了床，然后就去了考场，开始前最后看了一下字符串哈希的一些用法，最后没考。

T1 是一眼题，但是写太急了，改了 3 次，最后花了 18 分钟才写完。本着先写部分分的原则，我看向 T2。以一种不太自信和保守的心态，我也不太敢直接想 T2 的正解。

看了一会，感觉求出每辆车会被哪个区间的测速计发现超速之后就变成了给出若干区间，选出最少的点使得每个区间内都有被选择的点，但当时没有继续想。现在想来，一是太过保守，二是思维速度确实不够快。然后我便看向特殊性质，很快地，我便打完了特殊性质 A、B 的部分，然后思考了片刻 C，便得出了 C 的做法，然后发现 C 的做法最后的步骤和 n^2 的做法是一样的，当时还沾沾自喜觉得能拿 90 分。等我写完 n^2 的部分后才猛然发觉，三个部分加起来其实已经可以得到正解，于是在调试完 C 部分的代码后，我赶忙把进行了修改，然后很快过了大样例，就去看 T3 了。

T3 肯定是一道 DP 问题，我先设了一个错误的状态，打了个错解，然后改了一下，设 dp_{i,j} 表示前 i 个数中第 i 个数选蓝色，上一个选红色的数的数值为 j 的最优值，稍微优化了一下，得出了一个 O(n^2+nV) 的做法，此时大约是 1730。但是这个 DP 过程其实很明显可以优化，然而由于我并不熟悉线段树优化 DP 和整体 DP，所以当时没有想出来，也没敢去想。不过值得一提的是，很明显可以前缀和做的一个预处理数组，f_{l,r} 表示 l\sim r 都选同一种颜色的贡献，我却没想到，一直是用 n^2 做的。后面忘了转移过程中也有 n^2 的操作，复杂度瓶颈其实不在预处理，然后想写 O(nV) 的部分分的时候，我甚至写了一个线段树来维护。

T4 题面又长，看着就不好做，暴力也不好写，最后就没写。

估分 100+100+50+0=250。

晚上又一起吃了个饭，高一学长说 T3 是教练讲过的原题，但是我们当时都没发现，最后除了他以外只有 2 个大佬写出来了，但都是用线段树优化 DP 做的，他们也没想起来之前讲过。还有一个同学之前写过这道题，结果考场上调了很久错解，最后得到一个玄学做法。吃着饭呢，突然想起来我 T2 匀加速的情况写错了，最坏会变成 60 分，本来 250 还是比较稳的，但是 210 就不一定了。

所以估分 100+100+50+0=250 \rightarrow 100+60+50+0=210，不过这是最差的情况，也可能不会挂这么多。很讽刺的是我如果不把它们缝起来，直接用原来的部分分写法是肯定能拿 90 分的，当时过了大样例就没怎么看了，没想到会挂。

结语

今年好像很多人都拿了 300 分，不过我估计应该是幸存者偏差而已，去年 S 一等线是 150 分，今年虽然简单一些，但也没理由会上 200，所以 1= 应该是没什么问题的。初测成绩会在 11/05 公布，到时候再看吧。今年的 CSP 成绩在很多方面都低于预期，好几个朋友也不太满意，比如说 da17_ 的 这篇一句话游记

赞美万机之神/破碎之神/Omnissiah/Mekhane/WAN

11/2 Update

今天默写了一遍 T3 代码（赛时的 O(n^2+nV) 的做法），结果交上去只有 10pts，但是过了大样例的 n\le 2000 部分，乃大惊，心中已经开始担心今年是不是要再挂 40pts，仔细检查后发现原来是有一部分转移的范围本来是 \max a_i 的，写成 n 的了，但是不记得考场上写对没有。不过考虑到我当时一直想着 O(nV) 这一部分时间复杂度，后面还尝试过从 O(n^2 + nV) 完全改成 O(nV) 的，这里应该不会出问题，但还是有点担心。

破碎之神保佑

11/2 再次 Update

我又回去看了一眼题目的数据范围，发现在 n\le2000 的部分分中保证了 \max a_i 与 n 同阶，也就是说这一部分转移就算范围就是 n 也不应该会错，因为 \max a_i \le n，想到这里，我把转移的上界改成了 \max(\max a_i,n)，果然是对的。我开始怀疑民间数据造得有问题，于是在读入完后加上 \operatorname{assert}(\max a_i \le n)，不出所料全部 RE，这下不担心了，考场代码一点出问题的空间都没有，起码 T3 是不会再挂了。

11/2 第三次 Update

虽然 \max a_i 与 \max n 同阶，但是 \max a_i \le n 是不成立的，所以当时怀疑错了，不过赛时代码应该还是没有问题的。

11/4 Update

今天 CCF 三次变卦，上午 11 点左右把公布时间从 11/5 1300 改成了 11/4 1300，于是我心怀忐忑地度过了两个小时，甚至在去买饭票的时候，我和 @skella_ 还打算先只买中午的，省得下午发现挂完了得直接回原来的学校上 whk。结果 1300 打开一看：

成绩单未上传，请稍后查看！

等了十几分钟，CCF 终于反应过来，把查看成绩的通道关了，再次修改为 11/4 1600。然后又是紧张的 3 个小时。然后出乎意料的，在 1600，CCF 再次修改时间为 11/4 1730，此时我已经不怎么紧张了，忐忑的心情都在前两次被消耗完了。在颓废中度过了 1.5h，1730，机房里的同学们如期打开了查分网站，这回网站却直接卡死了，我们等到了 1735，最终还是决定先去吃晚饭。回到机房时，已经可以查分了。

最终成绩 S 100+100+50+0=250，J 100+100+100+0=300。

CCF 的数据太水，本来写错的 T2 居然过了，找到赛时代码之后交到洛谷上测，民间数据只有 80pts，把印象中 a>0 的问题改了也只有 90pts，CCF 的数据真是够水的。本机房有人离散化写挂 65pts，有人被 Dev-C++ 的编译坑没了 100pts，我没挂分甚至还完全没被卡还是挺幸运的，该说不愧是机神教信徒吗，虽然 T3 没有做出来有点丢脸。

11/4 再次 Update

补充一下今天看 S-T3 题解看到的内容，由于红色和蓝色交换是完全一样的，我在设置 DP 状态的时候就只设置了一个，然而在后续的转移方程中，我没有想起来，转移时前面的 dp_{x,y} 不仅可以表示 x 取相同颜色，y 取不同颜色，也可以表示 x 取不同颜色，y 取相同颜色，也就是说如果当前状态表示选的是蓝色，其前置状态的含义不仅可以是选择蓝色，也可以是选择红色。如果在这个基础上思考，将极大地简化转移过程并可以推出 O(n) 的正解。

接下来就要准备 NOIP 了，然后就只有不到半年的时间准备中考，希望一切顺利吧。

神必完整 \text{鸣大钟一次，推动杠杆，启动活塞和泵！} \text{鸣大钟两次，按下按钮，发动引擎，点燃涡轮，注入生命！} \text{鸣大钟三次，齐声歌颂，赞美万机之神！}

最终记于 2024/11/04，笔者的 15 岁生日。