CSP-S 2024 游记

Day -4 Mon 10.21

作业写不完，完全没法写 OI 题，寄。

Day -3 Tue 10.22

作业写不完，完全没法写 OI 题，寄。

CP 生日快乐。

Day -2 Wed 10.23

作业写不完，完全没法写 OI 题，寄。

社团课的时候写了一点题。

Day -1 Thu 10.24

作业不写了，可以写 OI 题了，好！

英语限时后半部分喜提机房最高，但前半部分阅读错了 3 个，总分机房垫底，寄。

打了 CP 的模板赛，吃了 4 发罚时并且机房垫底，幽默。

线段树 1 吃了 3 发罚时，幽默。线段树记得要调用建树函数，建树时要 Pushup，并且要开 4 倍空间。

单源最短路也吃了一发，注意优先队列默认大根堆，如果写最短路需要写 greater。

Day 0 Fri 10.25

翘了数学限时继续来 803 学 OI。

再次打 CP 的模板赛，一共吃了 5 发罚时，又垫底了。相比之下，CP 一发都没吃，太稳了！Orz

负环吃了三发，幽默。注意多测清空存边的链式前向星，而且必须在读入之前清空。

LCA 也吃了一发。数组开小了，哈哈。无向图存双向边要开 2 倍空间。

在 CP 和碱哥的高压下，我以极高的效率复习完了所有绿及以下的模板！

Day 1 Sat 10.26

CSP 比赛日。

为拯救我本周平均 5h5min 的睡眠，我成功睡出了 9h36min 的长睡眠，11:30 成功起床。睡眠时长恰好是前一天晚上的两倍，幽默。

起床复习了一下 exgcd 和 ST 表，吃完饭就出发去考场了。

考前祭天活动怎么没有了？原来是有老师拿着相机。

琛哥和万奆回来考试了。他们匆匆地来，又匆匆地回去了，只留下 AK 的神话。

上考场！606 机房 31 号，发现我和琛哥还有碱哥形成了一个三角，我们任意两人之间的曼哈顿距离都是 2。

14:23 敲了个缺省源。

14:25 下发密码，开题。我丢，怎么题面都这么长？这玩啥？T2 怎么是高一物理？你这让初中生怎么办？T4 这个体面是构式吧？

14:30 开考。看 T1，由于太简单了，想出了 3 个做法，然后花了 5 min 在抉择哪种更好写（

14:40 写了双指针的做法。过了 T1 大样例。开 T2。我丢，T2 怎么 1e5？我不会。怎么题面这么长？谴责。

15:30 写完 T2 的 \mathcal{O(n^2)} 做法，60pts 到手。其他不会了，弃了 T2 开 T3。

16:00 出去上厕所，回来的时候遇到 CP。奇妙。写了 T3 暴力一档，15pts。然后想骗一个 \mathcal{O(n^2)} 的 50pts。于是开写。

16:40 随便写了一个 DP，设 dp_{i,0/1} 表示第 i 位涂红色/蓝色。然后令 j 为 i 左侧最近的同一个数，使用预处理+二分实现，不知道有没有更好的做法，毕竟这样带了一只 log。（P.S. 现在是 Day 2，我在看了 CP 的游记后醍醐灌顶，我们只需要对每个数预处理出一个 p_i 表示上面的 j 即可，这样就可以做到线性了）

显然在 i 和 j 之间必须填一样的颜色，于是考虑找到所有相邻一样的数字，这些是可以算贡献的。拿 d_i 做个前缀和存起来。转移就是 dp_{i,0/1}=\max\{dp_{j,0/1}+d_{i-1}-d_j+now\}，其中若 i,j 相邻那么 now 就是 dp_{j,0/1}，如果不相邻，那就从 j 的后一位转移，now=dp_{j+1,1/0}（注意这里是反过来的）。然后每次 dp_{i,0/1}=dp{i-1,0/1}，就做完了。

17:00 写完很激动，发现怎么想写 \mathcal{O(n^2)} 竟然写成了 \mathcal{O(n\log n)}！然后一测大样例发现小数据都过了，n 为 2e5 的时候出不来了。调了 5min 发现数组开小了。再一测，发现没开 long long。这下没话说了，浪费了 20min，终于在 17:20 过了所有大样例。感觉很不真实，T3 这种题是我能切的吗？还是个 DP，我最不擅长的东西。

17:30 回去写完 T2 的特殊性质 A，又 10pts 到手。这下开冲 T4 了。

18:00 花费 30min 才读完 T4 题面并写完了读入。哈哈，这个构式题面真难懂，谴责。

18:20 写完 T4 特殊性质 A。数组开小了多调了 10min，然后就没时间了。最后 10min 极限调 n\le 8 的部分分，没写完，遂只交了 16pts 的代码上去。

18:30 结束了。100+70+100+16=286 考的很好，感觉开挂了。

出考场，问了一圈，人均 300+。

CP 340 mcw 368 Orz

zzp AK CSP！！！场切黑题 Orz！！！放一下他的题解

crx 250，切了 T2。一讲做法，发现是转化成区间覆盖写贪心。醍醐灌顶。想到不久之前我在英语 presentation 中讲的正是贪心算法，更幽默了。

问了一圈 T1 做法都不一样。有点慌。不过过了大样例应该没事。众数的做法很妙，我怎么没想到呢？

晚上和 万奆 CP yizcdl2357 车神 tracker 打羽毛球。万寿羽毛球馆晚上一个场 1h RMB 106，谴责。我们两个场，这下大出血了。

回家自测，** CCF 不公示源码。还好我们有 JCOI 冠军 d0j1a1701 帮我们 decryption，获得了源代码。膜拜！

没挂分。但感觉有挂。这个入是桂！

Day 2 Sun 10.27

T4 民间数据太水了，竟然让我得了 20，幽默。

Day 10 Mon 11.4

CCF 耍猴，出分时间改了 4 次，每次卡准时间打开查分网站准备查分发现改时间了，墙裂谴责！

最后大概 6 点查到了分，100+70+100+8=278，T4 意外挂了 8 分，不懂。

总体而言，这次 CSP-S 的运气还是挺好的，完全没有想过我能场切蓝题，并且是 DP。但是 T2 绿的没做出来属实不应该，接下来一个月要加练冲刺 NOIP 了。cmh，菜就多练！