CSP-J/S 2024 第二轮游记——战至终章，无怨无悔

· · 生活·游记

前置 Links：CSP-J/S 2024 第一轮游记——展翼高飞，梦想起航

不知道为什么要这么早开坑，反正开了。

tb 的初三学生活动异常丰富，不仅有在初一初二小灯开运动会（只剩下我们给初二的 jl 和 gcx 远程掐表了）时候的月考，还有什么“动员大会”（每名同学在班上的战旗上签字，弄得特别中二）。

十一假期开始卷题，发现的问题就是我连 freopen 都写不对了，别想多，其实就是把 , 写成了 .。

回状态。月考重回年级 rk 1（不就是某六边形同学失误挂分了嘛）。

时隔好几个月重回机房，打了自己熟悉又陌生的 Heartquakes 模拟赛。没想到赛时自己的排异反应这么严重，短短几十天就不适应 OI 比赛的节奏，于是跟教练申请去机房外面透透气。隔着实验楼那灰黑的玻璃望着澄澈又湛蓝，却被玻璃蒙上了一层纱的蓝天，不禁忆起去年备战 CSP 的无忧无虑，去年几近 AK CSP-J 的踌躇满志。年岁长了一岁，然而我却在即将比赛的重要关头退缩了。怎么会这样？我尝试推开玻璃，可无论我怎么使劲，也无法推开那年久失修的窗户，恰似我无论怎么努力，也无法提升我那不堪入目的 OI 成绩的现实。我不禁怀疑：究竟是自己的能力不行，还是究竟未尽全力？或许我与成功之间就隔着那层看似脆弱却无法推开的玻璃，也许就是因为持续的自我怀疑，让自己失去了最后搏一把的力量和勇气。

So_noslack 模拟赛，喜提 AK 一份！晚上冒雨跑了个 3 公里，心情愉悦。体测，1000m 拿到个人 PB，3 分 07！

老师一再强调即将到来的期中考试的重要性，好吧，期中刚好夹在了 CSP 与 noip 的正？中间。

赛前一天跑了个 3km 放松身心，喜提 10 分 59 秒完赛。

晚上躺在床上，本以为自己会在人生中最后一场 CSP-J 的前一晚失眠，估计自己是太困了，加之嗓子火辣辣的疼，倒头就睡。

Morning

本次 CSP HA 的考生中，郑州的考生被分到了“河南经贸网络信息中心”考点，地市的考生被分到了“郑州大学”考点。

早上起来，发现嗓子更疼了，吞咽好似有异物感，于是意识到有可能是扁桃体发炎了（我一年不弄几回这样的病都不正常），狂吞白开水。7:25 准时到达河南经贸，吃早饭，下车与同学们会和。考点的门非常小，经初步讨论，我们 tb 的考生被安排在门旁边的一个大铁门边合影留念。

大概是 7:55，考点的门打开，很多人涌了进去，遂失去集体拍照机会。旁边还有很多存包柜（貌似有好多考生存包啊，手机啊之类的），我利用人类智慧通过了第一轮安检，并把包带到了考场门口（最后愣是没带进去）。

第二轮安检，找到自己的位置，不出所料，黑屏的电脑与“保持安静”四个字。试键盘，键盘很舒服，但是 \ 的键位貌似有些奇怪。与初二小灯 fmx 找卫生间，并吐槽卫生间质量真差。

考场内大约有个 100+ 人左右，但让我惊讶的不是考场的规模，抑或是房间内的闷热，而是考场内小学生的数量。没想到，信息竞赛也逐渐走向年轻化，望着这些稚嫩的脸庞，我想到了一个词：“后浪”。他们还年轻，或许还能再参加不下 3 次 CSP-J 的机会，还能享受更多时代的红利，而我，只剩下这一次机会了。不拼尽全力，还待何时？

敲缺省源，更改编译指令，写了一个 fc 的 checker，似乎万事俱备，只欠东风。

开题，四道都是传统题。看了第一题惊呆了，看样子 CCF 继承了初赛时的风格，T1 竟然这么水？！在旁边的小灯还在询问监考老师诸如“压缩包怎么下”“密码是什么”“怎么打开”“怎么下载 DEV-C++”等抽象问题时，我飞速地通过 T1，耗时 6\text{mins}。

T2 看着像一个跑地图的玩意，显然复杂度中会有一个 \mathcal O(nm) 打底，然后怎么还有个 k？！仔细一看发现好像 k 和 nm 是独立的两个玩意，直接暴力枚举可以做到 \mathcal O(nm+k) 的复杂度，那不是稳过？！并在内心暗自想 CCF 为什么给了 40 分的 k=1 特殊性质——然后，挂了。诶怎么回事？看我解决方案——狂喝水……突然发现，存二维数组时的偏移量貌似和平面直角坐标系的 x,y 轴方向是不一样的，然后迅速改 dx[],dy[] 数组，在开赛 37 分钟时通过此题。

开 T3，好数学啊。突然意识到数字 8 需要的小木棍数量是最多的，于是全填 8，然后——样例又挂了。对于 n=18，貌似输出 208 比 488 小一点？然后观察特殊性质，为什么与 n\bmod 7 有关？考虑 n\bmod 7 后的结果。经过我大概一面 A4 纸的计算和模拟，我成功通过了小样例（不是是个人都能过嘛）。然后想测大样例，但是——怎么没有大样例？！抽象的 CCF！注意到这题貌似是个瞪眼题（当然你说是个 Ad-hoc 也行），给大样例太容易被瞪出来，我暗自原谅？了 CCF。

这时是 9:37，我狂灌水的后果是非常想上厕所，于是看了个 T4，举手要上厕所。回来写了个 T3 的拍子，大概拍到了 n\leq 50 的数据发现没问题，然后开 T4。

写了一个搜的代码，大致思路是记录每个数出现的位置，然后每次接到一个新数的时候往这些数出现的位置跳。诶？！怎么过不去？！原来多测没清空。然后 AC on Sample 1,2,3…，TLE on Sample 4？！甚至连 n\leq 100 都过不去。完了。

考场闷热无比，加之我嗓子疼，狂灌水，很快陷入了想上厕所+水喝完了的困境。善良的监考老师给我一瓶矿泉水，帮我渡过难关。

但是思考了两个小时都没有取得什么进展，最后给 T1 写了个拍子，过了一遍 T2 的大样例。疑似 100+100+100+15=315 遗憾离场。zxh 应该是 AK 了，user 不用问显然 AK 了，听说考场有神仙打了 T3 的表，大概有个 100 行（那他还没找到规律？！）。

出考场之后，tb 组织了拍照活动，只是效率极其之低。zzy 和 zzy 貌似被 Ad-hoc 住了，于是各自挂掉了一些分数。lrh 和 zxh 都写出来了 T4，只是 zxh 的大样例跑了 1.5 秒，而 lrh 的跑了 16 秒。另外地，二人在讨论按 zxh 的做法做 T3 貌似当 n 非常大的时候，可以用一串 2 来替换那些 8。诶？zxh 的做法不就是我的做法？！是不是要假完——

Afternoon

进场，跑错考场。好像有个应该去郑大的考生跑到经贸。灯一直在闪。

进场前听高二同学临阵磨枪 exgcd 板子，不由地骄傲——我可是什么 S 组知识点都没复习的呢。这次不得狠狠挂一发？

听说包会非常大，先不发大样例。开赛，怎么一直没有密码？怎么密码输进去不对？我急中生智，把 ？ 改为 ? 输进去，开题！根据去年的经验，T1 会非常简单。果不其然，读了题之后，虽然没有发现 n\leq 8 一类的垃圾，却也意识到，这个题貌似就是一个 sort 然后乱搞一下完事。考虑每一条龙只能砍比它弱的龙，那么贪心地想，就让第二弱的龙砍最弱的龙，以此类推。于是写出一个 \mathcal O(n\log n) 的代码，经过一系列调试，轻松地通过了样例。这时不超过 14:45。怎么大样例还不发？！

读 T2。意识到自己好似学过一点高中物理关于加速度的知识，信心大增（后来发现貌似也没啥用）。读题发现每辆车貌似只会在一段区间内超速，然后发现可以下载大样例了。然后 T1 的第四组样例挂掉了。赶紧改，记录一个 rest 变量记录这次砍完之后还剩下的龙的数量，如果下次能全部砍掉则砍，若不能砍完则 rest 加上对应的数值，15:06 pass。

回看 T2。发现该题可以抽象成有 n 条线段，需要在线段上选数量最少的点，使得每条线段上都至少有一个点。第一个问题是如何把这些线段搞出来，想到要二分每个摄像头，判断在这些摄像头是否超速即可。但是……好像没有想出来怎么选点，啊啊啊怎么办！后来贪心地想到，若删除这个摄像头不会改变原来一辆超速的车超速与否，则删掉这个摄像头，否则保留，这样的时间复杂度是 \mathcal O(n^2) 的，于是将前面的过程也改为 \mathcal O(n^2) 复杂度，于是在大约 16:00 时通过了 n\leq 3000 的数据，于是开 T3。

T3 很像一个 dp，考虑设 dp_{i,j} 为考虑到第 i 位，上一个红色的是在第 j 位的答案的最大值，那么转移就是 dp_{i,j}=\max dp_{i,k(k\in [1,j)}（真的是吗），写了半个小时无果，于是写了一个时间复杂度为 \mathcal O(2^n\times n^2) 的暴搜，可以拿到 20 分。

快速开 T4 呀，现在已经是 17:30 了。题目很长，读了半天都没太读懂，还有一些变量是要我们求出来而不是 cin 进来的，比如 K。开始想着写 B 的性质（毕竟，有 24 分呢！）。但是写了半天发现假了，因为我貌似？无法逐一判断究竟是哪几个选手赢了比赛。然后赶紧改写 A 性质，发现当 r_i 是 2 的幂次时好像不需要添加选手就能判断出谁是冠军，于是写了个暴力模拟代码：对于第 k 轮比赛，将胜者的编号汇总到 2^k\times x(x\in \mathbb N^*) 处，最后只需要询问第 m_i 个选手的编号是几即可。但由于我搞混了能力值与编号，一直到结束前 20 分钟才调出来。小丑，我。

血拼 T3，但纵使战至最后一刻也无济于事，最后预估得分 100+60+20+16=196。

出来跟同学们讨论，貌似他们都上 200 了，突然意识到好像 T2 的 A、B 性质不是乱写（只要是超速的车都会在最后一个摄像头被判超速，所以只需保留最后一个即可）吗，于是喜挂 20 分，80\rightarrow 60。此外，大家都写出来了 T3 \mathcal O(n^2) 的 dp，甚至 lrh 差点写出了 \mathcal O(n\log n) 的做法，只是由于时间原因没写完。

烂完了。

赛后发现 zzy S-T1 直接写了个求众数的代码上去，我总觉得不对最后发帖求助发现是对的（怪不得 Hack 不出来），所以我考场上瞪大样例为什么没瞪出来？！发现大家没几个写出来 T2 暴力的。

貌似 T2 转化为线段覆盖之后可以 \mathcal O(n\log n) 秒掉，诶？！

Summary

这次考的其实挺废物的，挂掉的分包括但不限于 J-T4 写 dp 和记搜能多出来的分；S-T2 的 n\leq 10^5 的 A 和 B 性质（甚至是满分）；S-T3 的 n^2（哪怕是 n^3）的 dp 和 S-T4 的 n\leq 8 的 12 分。思考原因发现是思路没打开，有时候过于兴奋反倒漏掉了更好的解法。如果 S-T2 写出 60 分解法时能冷静一下再多想想，如果 S-T3 能在几乎绝望的时候想到写个记忆化优化 dfs，那么结果显然会好很多。

不以物喜，不以己悲。

或许，还有一场 noip 挽回这一切；或许，这场 noip 也会消逝在风里？

聆听风的回答，望向新的期许。

全文完。