CSP-J/S 2025 复赛 游记

· · 生活·游记

CSP-J/S 2025 复赛 游记

初一蒟蒻的第一篇游记，如有不足之处还请多多指出%%%

DAY -7

去体检，在大巴上补了一下忘记的语文默写作业，结果回来脖子拉伤了

DAY -3

我因为不小心把水洒到了我的 Win7 电脑上，导致 Win7 蓝屏，就再也没醒来过

陪伴了我2年的朋友就这么没了，我很担忧我的CSP会不会也是这样

DAY -1

做好上午 J 组下午 S 组双考的准备，背了一下线段树、树状数组、扫描线、 KMP 、 Manacher 、字符串哈希、 LCA 、 Tarjan 的板子，21:00 准时睡觉

幸好脖子好了 qwq

DAY 1 上午 J 组

6:00

早上睡不着，很紧张，醒了

继续看整理的板子，看了 10 分钟才反应过来这是J组，而我背的都是S组的东西

过于紧张了，就写了一会语文作业放松心情

7:00

出去吃了早饭，豆腐脑和油饼都好吃

7:30

出发去考场，考点东坝，有点小远

8:00

到了考场，进考场，保安说 8:10 分才能进

8:15

找到了自己的机子，键盘好评！键位高度刚刚好

居然让提前写代码？！

迅速写了个缺省源，并把对拍 4 件套写完

8:25

完工，去上个 WC ，才发现自己手都一直在抖

想起来自己年六年级，去参加 J 组的复赛因为 T3 写了个神秘 dp 只得了 50 分，获得了 100+100+50+0=250 的吉利分数，而一等奖的线是 260 ，这份被同学笑了半年的乐子使我难以忘记

尽量的鼓励自己

8:30

开赛，输密码，解压缩，一切正常

决定先用时间把四题都浏览一遍，不要想复杂。

8:40

浏览完了所有的题目，感觉 T1T2 都是水，T3 竟一时没什么思路，T4 感觉只会暴力

很慌

8:50

决定不再浪费时间，先写 T2

9:10

没想到小 T2 这么卡人，完成了 T1T2，开始苦思冥想 T3

9:20

对于 T3 这种题的套路第一印象拆位贡献，事实证明不可做

决定先写一个暴力：O(n^2) 的 dp

9:25

用 5 分钟先写了个 O(n^2) 的 dp，这只能拿 60 分，是远远不够的

都说特殊性质好，于是决定思考特殊性质 C

观察到 $O(n^2)$ 的 $dp$ 做法的瓶颈在于需要枚举这一个区间最大的左端点 $j$，于是可以考虑动态更新 $j$ 的答案，于是想到了用 $lst_x$ 表示如果当前以 $i$ 为结尾的区间如果异或和为 $x$，每次 $lst_x = lst_{x \oplus {a_i}}$ 且 $lst_{a_i} = i$，最后 $dp_i = dp_{lst_k} + 1 9:40

写完了特殊性质 C，和之前的暴力代码写在了一块搞了个数据分治，这时我去了趟 WC，想到了一个奇怪的思路：使用分块来优化枚举 j 的过程。具体的，开 \sqrt n 个 umap，其中 umap 的每一个元素表示的是一个后缀异或和，假设当前枚举到第 j 个块，且 i 在第 k 个块里，并设 sum 为第 j+1 个块到第 k 个块的异或和，如果第 j 个 umap 里有 sum \oplus k，那么 dp_i 可以从第 j 个块里的 dp_{l->r} 进行转移，时间复杂度 O(n \sqrt n)

10:20

耗时 40 min 调完 100 行巨作，大样例都过了，但感觉有点悬，反正至少能拿 n \le 2 \times 10^5 的 80 分了。

上个 WC，看 T4

10:30

一开始的思路比较假，设 dp_{i,j,k} 为前 i 个数，最大值为 j，且和为 k 的方案数，想了一会后感觉不可做也不可转移。还剩 1h30min，依旧很慌

开始思考暴力，发现 dfs 可以得 40 分，于是先写了 dfs。

旁边的小孩一直跟老师吵说为什么没有 DEVCPP

10:40 $10:45

其实没用 5min

开始思考正解，盯着 \sum_{i=1}^{m} l_i > 2 \times \max_{i=1}^{m} l_i 这个式子，觉得如果是求 \sum_{i=1}^{m} l_i \le 2 \times \max_{i=1}^{m} l_i 的话会非常简单，但其实这两个式子的和就是 2^n，很显然第二个式子非常好求，先将数组排序，对于 dp_{i,j} 表示前 i 个数，和为 j 的方案数，转移太简单不说了，对于每一个 a_i，对答案的贡献是 \sum_{j=1}^{a_i} dp_{i,j}

11:10

写完了 T4 正解，完成了数据分治，大样例都过了，果断开始给 4 题对拍

11:50 $12:00

完事收工，出考场发现一堆人 AK %%%，看来今年题比较简单，出来跟我爸说今年是红橙黄黄

估分 100+100+[80,100]+100=[380,400]

12:30

到酒店了，刚到就和朋友聊，发现都是 AK 佬%%%，都说简单，教练预测今年 J1= 分数线 300 左右

13:00

本来想睡个觉，我爸说第二题输入是反的，n 是列数，m 是行数，把我吓醒，后来我爸说是输出反的，不是输入，哦那稳了，但这下这下睡不着了，背背板子吧

DAY 1 下午 S 组

13:40

出发，去的路上有超大逆风 qwq

14:10

进考场，和 J 一样的操作，敲了缺省源和对拍，但键盘差评

14:30

开赛，输密码，解压缩，一切正常

依旧先用时间把四题都浏览一遍。

15:00

我有种不好的预感，就是我一道都不会

我只能先做 T1

15:20 看来部分分是唯一的手段了 $15:40

写了个 O(n^3) 的 dp

开始思考正解，发现好像可以先按最好的装进 3 个桶里边放，多出来的往损失小的里边放，然后统计答案，而且这样桶还不会多出来

16:20

果然，自己是思想的巨人，实现的矮子

$17:00

甚至 T2 一直没读懂题

去写 T3T4 的暴力

17:30

写完了 T3T4 的暴力，回来看 T2

还是看不懂题……

17:50

终于！把 T2 看懂了！

开写！

18:15

不知道为什么写了个 O(2^kkn^2) 的写法，我甚至还以为能过 n \le 10，k \le 5 的部分分，结果第一二个大样例过了，第三个 TLE 了

优化后 10000ms 变成了 992ms，结果发现数不对……

瞬间心凉了

18:25

就要结束了么……

坦然接受一切吧

检查了所有代码，没有问题

18:30

出考场，回家一路没说一句话

和朋友聊，他估分 158，自己心里好受了些

估分 $100 + 48 + 10 + 8 = 166

看来大家都说难

DAY 1 晚上自测估分

19:30

到了家，迫不及die去洛谷自测

只测了 S 组

第一题写完，提交，AC ~

第二题写完，提交，

等一下，AC+TLE，16 分……

第三题，等会，讨论区…… |t1| \ne |t2|

爆零

第四题，提交，8 分

分数：100+16+0+8=124

教练说只能二等

爸妈从眼里都能看出来失望

不敢面对，自己哭了一晚上，没睡

我今年要是拿不到 S1=，WHK 啥也不是的我也就 AFO 吧

DAY 5 查分日

本来我已经回归 WHK 的半 AFO 了

但我不死心，依旧水水洛谷讨论区

说今天就出分？？？

好吧看来今天就要了结了

体面的 AFO 吧

我只好让我爸去看了看，看看有没有 S2=

我爸去查了分，说我第一三四题都和我测的一样，但第二题不太对，是 56 分，总分是 100+56+0+8=164！

我：夺少？

也许是 CCF 不想让我 AFO？

问了朋友，怎么都是 164pts 啊

如此的话，只好准备 NOIP 吧

NOIP 2025RP++