CSP-J/S 2025 游记

jd6256 · 2025-10-25 16:58:24 · 生活·游记

Day -??

不能再做水题了，脑子要动起来。好不容易切了几道 NOIP （蓝/紫）真题，这么费劲，我真是个蒟蒻。（不过在学校不会闲着了）

Rp要省着点用，所以数学考试只考了 98 pts（满分 100）。好吧我数学习惯太差了……

希望 CSP-J/S 的题不要太奇怪，比如我没写过的交互题。~~Yixiuge 说不要在赛前预设分数，所以我的期望得分是 0pts.~~

Day 0

这么快就到比赛啦，好神奇啊。最近都在刷往年蓝题，看完题面就在~~数学课和~~午休的时候想（谁说这解法会 T? 这解法可太棒了），感觉蓝题也不怎么难(?)。

9 班有一位蒟蒻 OIer ghl,上学变得有趣起来了。

放学了，我和 ghl 互相~吹捧~鼓励对方。I AK CSP-J! ~(当然不可能)~ Rp++!

Day 1

比赛当天竟然不是很紧张……

吃完早饭后，就去了八中考试。别人都在门口拍照，~我没拍，我太可怜了~。

入场，找座位，写快读快写和对拍模板。不好，不知道 NOI Linux 下如何使用命令行运行程序！没救了。

8：30 发密码。神奇老师用中性笔写解压密码，好多人根本看不见，后来贴了张打印的密码。开始写代码。

T1 是一个无脑桶排序，但我的代码居然神奇 CE 了？太奇怪了，但重写之后好了。T2 小模拟，简单。

T3 有区间异或，盲猜前缀异或和，果不其然。用单调性质优化后可做到 O(n). 就是后面调了一小会。

T4 应该有绿，也是整场考试中最难的。人类直觉告诉我这是 dp，但是枚举当前位置，当前和，当前最大值是 O(n^2\sum{a_i}) 的时间复杂度，会 T。思考了一下发现和大于最大值的2倍时，和的具体数值无用。优化后，时间复杂度为 O(n^2\max{a_i}), 有 80pts. 再发现当前位置与当前最大值可以合并，用前缀和维护转移，时间复杂度为 O(n\max{a_i}), 完美。（赛后得知 ghl 最后一步没想出来）

经过 80min 的鏖战，4 道题都写出来了。我想起来了命令行指令，于是开始对拍 T4 & T3. 跑了上万遍，结果都是对的。希望不要挂。

下午就不幸运了。T1 是反悔贪心，轻松写出。但为什么过不了大样例？原来是比较有问题。~~（虽然没看出来）~~ T2 一眼最小生成树 + 枚举 k 个点。但最小生成树是 O(m \log m) 的，一定有更好的做法……（然后 T2 就寄了，1= \rightarrow 2=） T3 只会输出 0 偏分，T4 也只拿了 12 pts，大寄！

Day 2（赛后反思）

对于基础题，花的时间还是太长了。（听说别人 30+min 就 \text{AK} 了 \text{J} 组）
现在机器越来越发达，时间复杂度相对于之前可以宽松一些，比如 m=10^6 时可以用 O(m\log m) 的做法。只要不超过 3\times 10^8,都是允许的。
~~Rp 不够~~