CSP 2025 游记

2021CHD · 2025-09-21 19:36:39 · 生活·游记

Day -41

初赛。

中午发现 J 组完善程序出了一道交互题，于是大胆预测下午的 S 组也会有。

结果真有。

都怪第三十题题目不清晰，毁我 AK 梦。

估分 98.5。

发癫什么的已经全都写草稿纸上了（有零个人注意到），这里也没有颠可发了。

坐等出分。

Day -36

出分了。

估分还挺准的，就是 98.5 分，被第三十题坑了……

反正能过就行。

至少比去年（96 分）有长进。

Day 1

目标：能去 WC 和 APIO。

再度宣传 APIO 2025 游记。

上午 J 没打，整个上午都在写一道题的题解。

中午听打了的人说很简单，等价于 ABC 的前四题。不确定是不是真的，然后就直接猜测下午不会太难，比如可能像 2023 年一样没有紫黑。

显然我猜错了。

时间来到下午，观察考生守则发现这次居然可以在准考证上写“代码长度等校验信息”。还好我剩的时间很少，而且代码都很长，不然我就把场上的代码都带出来了。

解压密码是 Ren5Jie4Di4Ling5%，人杰地灵。

省流：

先看 club，感觉看完题就会了。

然后开始看 road，第一感觉把 m 条边缩成 n-1 条最小生成树上的边，但是好像还过不了，先放了。

接下来开始看 replace，很快就发现只需要把中间不同的部分拿出来哈希一下就等于多测求解另外一个问题。感觉好像不能把转化出来的问题秒掉，就先放了。

最后看 employ，组合计数题，第一时间没什么想法。

倒回来好好想想 road，发现还可以优化一下，但是很遗憾没想到归并，于是我的复杂度是 O(m\log m+2^kn\log n) 的（此处认为 O(k)<O(n)），感觉有被卡常的风险。

接下来做了挺久的 T3，感觉可能是四五十分钟，也不知道为什么没想到 AC 自动机。（可能因为 AC 自动机在大纲里面属于 NOI 级，复习的时候就没有留意到）

于是最后终于转化成了一个类似二维数点的问题，用扫描线加线段树就能做完，但是感觉代码会很难写。算了一下空间，两棵字典树加起来不到 1.5\text{G}，剩下的都是线性的，应该开得下。

看了一会 T4，本来也没想着能做出来，结果看部分分看着看着就看会了一个 O(n^3) 的 DP。

此时应该还剩不到两个半小时，开始写代码。

T1 写写写……过了大样例。

T2 写写写……过了大样例，但是感觉有可能被卡常。希望 CCF 的机子是少爷机。

感觉 T3 很难写所以先写 T4。

T4 写写写……写完略微调一调就过了大样例，测了一下极限数据感觉有可能被卡常。再次希望 CCF 的机子是少爷机。

此时应该还剩不到一个半小时，开始写 T3。

接下来你们看上面表格中那个红色的 \color{red}5993 应该都知道发生了什么。

没错，我居然没……有没写完！天知道我是怎么写完的。

可能大概就是 T3 写写写写写写写写写写写写……

剩不到二十分钟写完发现过了小样例但是没过大样例，当时感觉要寄了。但是经过仔细盯真，发现我答案存放的顺序错了，于是修改了这个愚蠢的错误以后居然就直接过大样例了，还跑挺快。

接下来把四题代码丢虚拟机里编译了一遍，没有 CE，检查文操，发现文操都开好了。

最后十分钟开始写“以选手姓名为文件名”的文件，虽然感觉好像不写也没问题，似乎从来没用过这个东西，但还是写了。

自我感觉 A<B<D<C。

出场发现好像有若干人打爆了，还好我比较幸运。

不足之处也是很明显的：在时间不够充裕的前提下 all in T3。如果最后赌输了可能就爆炸了。

J 和 S 都没有交互题。

Day 2

晚上在试图做出 J 组的题。

（正在试图做出 T1）

（正在试图做出 T2）

（正在试图做出 T3）

（正在试图做出 T4）

成功花费半小时做出四题，感觉确实就是 ABC 前四题的难度。四题代码加起来不到 1.5\text{k}，J 组还是太神秘了。

感觉 J 组 T1 和 T4 可能评分有点虚高？（现在 T4 降了）

看了眼 S 组的题。

• T2：由于评测机性能差异，本题时限提升 1 秒。
• T3：由于评测机性能差异，本题时限提升 1 秒。
• T4：由于评测机性能差异，本题时限提升 1 秒。

那看得出来 CCF 的评测机性能应该还是很不错的。

感觉 S 组 T1 和 T4 可能评分有点虚高？（现在 T1 降了）

在代码公布之前我应该都不会再写今年 S 组的题了。

Day 3

今天早上通过询问 DeepSeek 得知 CCF 的评测机确实是少爷机，比本机还快一些，感觉可能不太会被卡太多常。虽然好像 T2 还是不一定能拿到满分。

Day 5

通过神秘方式（如上图）得知了实际得分：100+80+90+100=370，小挂，问题不大。

感觉至少不会去不了 WC。

现在感觉 \sout{A<D<C<B}。

Day 6

出分了。

代码和数据公示了。

J 组赛后半小时写的代码成功通过官方数据。

S 组经长度和 CRC32 检验，鉴定为 CCF 没有掉包我的代码。

• T1 和 T4 平稳通过。
• T2 在洛谷上居然冲过去了，说明 CCF 的机子没那么强。
• T3 居然是 WA 90 分，看来需要好好调一调了。

改题：

• T2 写了（期望）O(m\log m+2^kn\alpha(n)) 的做法，成功跑到了一秒以内。（此处仍然认为 O(k)<O(n)）
• 不是哥们 T3 把 n 和 q 写反了？（开始庆幸拿到 90 分了……）改完就过了。
• 经观察，发现当 n\ge q 时我的 T3 代码（大概）不会有问题，所以实际上我的 T3 最低可以拿到 20 分（q=1），还是太抽象了。

完结撒花。