CSP-S 2024 游记

· · 生活·游记

前言

又一个赛季开始乐。

2022 赛季 CSP-S 真的起飞乐，240 分切绿蓝，当时我初二选手中能排到很靠前的，但是这个省选被过河卒干死了，就很难绷，小 E 你可真会出……考验选手代码能力的……好题。

2023 赛季 CSP-S 打得很烂，T2 没切出来只能说是纯纯的水平低，没什么可说的。最后居然能和整百选手一个分也是中国计算机学会构造水数据带来的奇迹。2023 省选一试我打得真的帅，全省第 39 名本来有希望冲击 D 类的，结果被 Day 2 T1 送走了，这个只能说是水平低，底力题挂了就是似得好，没啥可说的。

2024 赛季我已经是高中选手了，回想初三一年水平没什么提升，中考也考得一塌糊涂，甚至把后两位成绩翻倍也只能排到区 400 左右（不要去盒我中考成绩 qwq）。线下生活也总是受排挤，好在军训文艺汇演时有气质大哥愿意和我一起表演，否则真成小丑了。被建议打完高一如果拿不到 Ag 就 AFO。

顺带一提，某本校 OIer 和 7 个人合唱夜空中最亮的星结果麦克风不够了，4 个人被迫唱和声，也算是一件奇闻了。

初赛

初赛在一所名不见经传的地方参与，赛前训练里基本都是机房靠前的排名。当然这是由于机房很多技术较强的人不愿意去认真研习复杂“毒瘤”的（动辄上百甚至快两百行的阅读程序）程序题目，所以也不算什么骄傲优越的资本；更何况初赛就是复赛的资格，只要是学了点 OI 的都能过。

整个题目上感觉前面的题都比较基础，还有个 10 个点连四个点环的题让我印象深刻。当时卡了好久。完善程序二分题简简单单，找前 k 大的思路和洛谷 Div.3 月赛一道叫什么“庭中有奇树”的题及其神似，反正二分法和堆扩展法也就是常见的唯二解决此类问题的方案了。次短路有点看不太懂，但是还是根据自己的一些直觉之类的蒙出了一些答案。A 好多。

最后出考场发现 A 应该 9 个，但我感觉后两个程序 A 的分布和他们描述不一样，反正初赛过了就行。

复赛

14:00 左右就抵达了考场，一位本校同年级 OIer 问我普及 T4 怎么做，我看了群友的口胡也不太会，不过看他都不会也放心了，没太讲明白因为要遵守考场安静的纪律。

进入考场，同座一位初一学弟一直在膜拜我，感觉心理压力好大。并且想起了初一时单纯幼稚的自己。更大的期望意味着更大的责任，我想起狼人杀中石像鬼的一句语音“让自己变得有用一点，才有活下去的价值。”活在学弟的心中被膜拜，需要发挥出带头学长的价值，更何况我还没参加过冬令营，这个对于 CSP-S 成绩要求可不是 NOIP 对于高中选手的 CSP-S 非零的要求那样简单容易。

14:20 下发了试题解压码，结果发现又是双层压缩。出题人已经不喜欢在解压码里整活了，就是一段随机大写字母和字符组成的很乱的一个东西。我盲狙一波，题目顺序是 duel-arena-color-detect，因为 detect 有点像推理的意思，且样例包很大；duel 这个词我的印象是兔群（即“粉兔 bilibili 很酷不直播”QQ 群，作为小粉兔的粉丝群）中一个 bot 的功能，这题像是魔怔题，color 作为染色问题是可能有难度的，实际上出现在省选压轴、春测签到两个位置让我很难估计这个词代表的准确难度。

最后我发现蒙对了 2 个题，开包看题。

T1 我觉得像是那种很老少皆宜的签到题，但是一开始看错题意了，看成了让最多的角色存活，我一想这样的话不是得小打大来浪费攻打次数嘛；看到样例 1 我又想到是不是每个角色都必须攻击击败，但样例 2 又否决了我的猜想。我就开始思考这个题是不是题意给错了，旁边一位学弟指出，但是老师说没问题。

那就索性先开 T2 吧，什么让人感到生理不适的题，这个题目离谱程度类似于 CSP-S 2023 T4 啊，T3 看完后连平方都没啥思路，T4 不想看，转而回头去写 T2，秉持着 T2 我不想写别人也不想写我写了就赚了的理念。

一开始想通过一个公式来确定运动情况，后来不想推了，就把运动分为匀速直线运动、初始超速的匀加速直线运动、初始未超速的匀加速直线运动、初始超速的匀减速直线运动、初始未超速的匀减速直线运动五类来讨论，因为参数很小所以感觉 long double 不容易溢出或者精度问题，放心地对于后四类运动求解了运动截止的地点。然后分讨了四类运动的速度变化节点；最后把问题转化后就想了个看起来很对的贪心，即排序右端点然后每次尽量在靠右的位置保留检查点，这样的话感觉用了快读时间复杂度还好瓶颈只在排序。

回看 T1，发现其实只需要保留最少得角色即可，那就是每个角色从弱到强依次看看能不能解决掉一个更弱的角色，用了一个队列。

去看 T3，此时因为 T2 分讨在第二个样例（幸好给了组很小的文件样例，不然我真的崩溃了没法调了）卡了好长时间，时间已经只剩下 90 分钟左右了。看起来没给什么特殊性质像是那种动态规划题，平方给到 50 分高分让我不由得想到：（1）如果我打出平方已经能获取很大优势；（2）平方解题难度可能不比正解简单多少，考虑从平方做法入手优化。我设计了一个关于当前位置和上一个异色位置的动态规划，但是这样转移时必须支持查询一个不连续集合最大值的操作，不好弄；我把动态规划改成了关于当前位置和上一个异色位置的数值，这样转移时只用维护全局增加、全局取 \max 、单点求值三类操作了，因为懒标记在最后遍历整棵树取最大值时没下传在第二个大样例挂了一下，不过很快就调出来了。

认为第二个大样例有几组极限数据，时间乘 2 后如果不超时可以认为时间复杂度正确，开 O2 跑完后发现可以，就去看 T4 了。

T4 题意好复杂，最后甚至要优化到常数时间内处理每个询问线性预处理，感觉我还是先从多项式复杂度开始吧，并且没什么时间了；我想到有效的值其实范围很小，可以把不想要赢的人设成 0 ，想要赢的人设成 k+1 ，每次考虑一个人能不能赢和所有新人都输的情况，但是不知道为啥最后挂了，没调完，红温了。

现在想来，如果一个人本来能因为擂主太弱赢，但是因为导致他输的擂主又因为当时的一个很弱的新加入的擂主太弱了所以晋级了，那么他不赢的话那个新加入的擂主也有“责任”，所以这个贪心是不正确的。

最后估分 100+100+100+0=300 ，这是场上预估分数因为学会不愿意公开代码。