CSP-J/S 2025 游记

· · 生活·游记

前言

自招到曹二，有高中上了/ll/ll/ll。

Day -？

初赛，菜逼。

此时的我尚且不知道事情的严重性

Day 0

得知考场在曹二图书馆，遂前往，发现布局很好/se/se/se。

Day 1

上午摆了，084启动。我为什么要摆？

13:50 抵达校门口。cln 大蛇成为了第一位进入考场的人，并在考试开始后 -30 分钟提前交卷，成为第一个走出考场的人。

实则是自行车停校园里。

神秘排队，此时的众人还没有意识到不对劲。

考试开始

携带装备：伯爵红茶一罐，曼妥思一份，神秘话梅硬糖一罐。

考试开始，先吃颗糖。

快速翻阅 T1，T2，T3，T4，无明显说法，开始 T1。

T1

显然暴力能拿部分分，但考虑到这是 S 组签到题，应该正解不难。

考虑去掉 \frac{n}{2} 限制，好做的，直接每个数分进收益最大的组。

接下来考虑调整到答案。设第 j 组为超过限制的一组，不难发现将第 j 组大小调整到 \frac{n}{2} 后，一定不会不满足限制，直接贪心再调整一遍即可。

此时时间 15min 到 25min。

T2

图论题，我完蛋了/ll/ll/ll

去掉神秘乡村节点，就是 Kruskal 板子。

猛回头，k<=10,n<=10000，大概率枚举乡村节点建立状况，考虑枚举，剩余部分为 Kruskal 板子，复杂度 \operatorname{O}(2^{k}(m+nk))。

感性理解一下，发现存在最优解使得原图中只有最小生成树中的边在答案里，感觉是对的，写了，过大样例，假设满了，后面对排。

此时时间 1h 不到，200 分，优势在我！

此时的我还不知道未来是怎么样的。

T3

一眼丁真，鉴定为可以 \operatorname{O}(\sum T) 找到每个修改部分和查询真正修改的部分，哈希或 Trie 是好做的。

于是开始苦思冥想非修改部分的匹配怎么做。

口胡了神秘哈希套 Trie，我猜能对，开写。

唉 woc，怎么大样例 3 错了。

查不出来/ll/ll/ll我是菜逼

难道说，卡自然溢出？遂改成 Trie 套 Trie。

改完，此时离考试结束之差 1h。

我要去 WC/ll

我必须对（上头）

woc，怎么还错了，开始调调调。

找出错了，此时还剩 10min。

能赢吗？

赢个蛋，全部，假~掉~了。

T2 对拍？没时间了。

WC？不可能了。

一等？真能过吗？

100+100+0+0 遗憾离场。

考试结束

不用理书包，成为第一个走出考场的学生。

woc T3 怎么是 AC 自动机？我是串串飞舞/ll/ll/ll下辈子一定认真补习串串算法

草！