CSP - S 2025 复赛游记

· · 生活·游记

打了些啥，我咋烂完了。

Day -?

“CCF 基本不怎么出字符串的题目，就算出了你们也能用哈希水过去。”

Day -7

发烧。

Day -1

星期四，下午 LXN 组织考前信心格式赛，五题难度大概黄黄绿蓝紫，\text{T4} 是 Sushi，因为枚举顺序的问题卡了 40 \text{ min}。

如此成绩，如何 CPS-S？

有些同学文件格式出现问题，令 LXN 很是生气。

Day 0

上午没有去上文化课，在学校机房里复习板子，发现离考试只剩一天，自己的贪心学了坨浆糊，遂掏出 贪心套题 抱佛脚，然而感觉并没有什么用处。

吃午饭，上大巴。车上是 WFYZ 的 OIer。

照例强调一些千古永流传的英雄事迹，下发注意事项。

左边坐着 ZRL 初一巨犇，留影合念。

::::success[合影]

若有侵权，私信删除。 ::::

太有张力了。

睡觉，睡觉，睡觉。

“哎呦给我干哪来了。”

到酒店，办理入住，发现自己一个人住豪华双人房，爽了。

和 ZRL、GJY、ZMS、WQJ 去 DCY 房间里【数据删除】。

楼上颓废被抓到了。

吃晚饭，感觉一般般。

LXN 把所有人叫到了一起，共同加油并合照。

::::success[合影] 猜猜作者在哪里。 ::::

试机，怎么人一年比一年多了。

我在干嘛，我在试机的时候写树剖，还把 dep[top[u]] < dep[top[v]] 又一次写成了 dep[u] < dep[v]，写到学校快关门，闭门造车了属于是。

回酒店，GJY，带我学会了如何玩 Generals，有趣，但是被虐了。

洗热水澡，晚上 \tt{11 : 30} 总算睡着了。

Day 1

早上起来 \tt{6:47}，【数据删除】了一会之后去吃早饭。

伙食比昨晚好多了。

和考 CSP-J 的同学互祝 RP ++。

上午不知道要干嘛，先【数据删除】了一会，然后开始听南外的贪心，感觉挺好理解的。

吃午饭，感觉比早上更好吃，但是因为考试，并没有吃很多。

和 ZYZ 探讨如何乱搞，谈到了 AHC 的 一道题目。

有趣。

中午睡不着了，继续上午的工作。看了看 CSP-J 的题目，出水了。

哎哎哎，怎么要开始考试了，我的状态呢？？？

大巴上明显感觉到同学们的紧张了。

这是很多同学的最后一个赛季了。

开 $\text{T1}$，发现这是一个反悔贪心的题目，由于本人在贪心这块非常菜，想不出别的实现，开始按照传统的 trick 尝试运用优先队列解决。就是说，先加大的，加不了了做决策，看看是把当前的轮换还是把要放的组中贡献最小的轮换。然而非常难写，定义了 $3$ 个结构体，写了一车的下标转化，到 $\tt{15:10}$ 左右才写完，然后发现过不了第二个大样例，有点慌。开始质疑自己的思路，事实是我的思路确实假掉了。红温了，万念俱灰，缘木求鱼的操作。 上了个厕所回来继续争，浑浑噩噩，写了个对拍，拍出一组小样例，观察后摸到了一个新实现。首先把所有人都放在贡献最大的那个组里，然后判有没有超，超了的话就把那个组所有人的权值各自减一下，算出将这个人移出去的贡献是多少，然后排序，从大往小取。容易发现这个被排序的值一定是非正的，我们只需要让那个组正好减到 $\frac{n}{2}$ 即可。又发现最多只会有 $1$ 个组不合法，于是我们做法的正确性就有保证了。 大概 $\tt{16:20}$ 通过大样例，这个速度真是无敌了，剩下的时间我给后三道题修修脚都很困难，不得不开始急速骗分。 开 $\text{T2}$，先把 $k = 0$ 的情况写掉。然后特殊性质 $\text{A}$ 也很简单，我们直接把所有的点并进去跑 Kruskal 即可。一共是 $48 \text{pts}$。 开 $\text{T3}$，写了个 $O(qnl^2)$ 的暴力，然后发现特殊性质 $\text{A}$ 是一个 AC 自动机的板子，然而因为前文的【数据删除】，我在赛前并没有复习字符串，炸了。幸好特殊形式 $\text{B}$ 是很好写的，从字符 `b` 下手，预处理即可。然后再次注意到空间给了 $2048 \text{ MB}$，那么绝对是哈希了，可惜我并不熟悉前缀进制哈希，又红温了，写了 $35 \text{ pts}$ 跑路。 开 $\text{T4}$，这个时候还有一个半小时，终于看到 DP 了，思想很丰富，但是都假完了，浪费了宝贵的时间。 回到 $\text{T2}$，发现还有一个 $O(2^k(n + nk)\log(n + nk))$ 的暴力，写完了，感觉并不能多过几个点。 很快考试就结束了，感觉自己在 $183 +$，崩了，打成蛆了。 出来后都在说今年难。问了问 [WJW](https://www.luogu.com.cn/user/305069) 他 $\text{T3}$ 用哈希冲过去了，$200 +$，强强强。[FJY](https://www.luogu.com.cn/user/439960) 和我说了说他 $\text{T2}$ 的做法，恍然大悟只需要预处理排序就可以做到非常优秀的复杂度，可惜了，考场上有点着急。[GJY](https://www.luogu.com.cn/user/997206) 的 $\text{T2}$ 写了正解，但是被自己错误的 hack 骗了没有写下去，只有 $10 \text{pts}$，祝他好运。 回到大巴车上，高中生基本 $200 +$，我一个初二学生瑟瑟发抖。 在车上发了晚饭，豆浆配肉夹馍，很朴素但吃得很香。 路上 [LXN](www.luogu.com.cn/user/8267) 总结，并允许我们今晚颓。 路上继续和 [ZRL](https://www.luogu.com.cn/user/1115784) 坐一起，玩了 `edge.surf` 和 `Minecraft`。爽。 晚上 $\tt{9:20}$ 左右回了潍坊。 ## Day 2 [LXN](www.luogu.com.cn/user/8267) 询问了我的考号，并告知我是 $215$ 分，排 $200$ 名。 成了成了。