CSP 2024游记

前言

• 看来上天已经眷顾我了，是我没把握住啊...

• 世间有太多不完美了，万事总会有一些遗憾...

---

Day -34(2024.9.21)

初赛，不想多说了，就是洗掉雪耻的一天，因为我以前初赛都不怎么好，虽然说从初一连续两年都进普及和提高组的复赛，但是很神奇，每年提高组都过，普及组只能靠学校补录名额进，况且在大湾区赛上初赛也没过，痛失一次宝贵的比赛机会，所以这次不能再输！所以初赛前几天我甚至没复习复赛的知识点，一直在备初赛。

不过还是挺轻松的，J 很简单，不过看错了题目，导致连错两题，没了 $5$ 分，分数差了一点：$89$，卡全国 $10\mathrm{\%}$ 标准线；考提高组时明显感觉今年实力比上一年有进步，也挺轻松的，三道阅读程序看懂了两道，轻松拿下 $71$，遥遥领先于全国 $10 % $ 线，好歹也是前两年都进复赛的选手...

Day 0

在学校小卖部，买了一盒润喉糖和一瓶矿泉水。

润喉糖神力！！！

比较慌张的其实，这次比赛对于我来说有很大的意义。

主场作战，优势在我，和 ljs 同一个宿舍睡觉，晚上 $10$ 点就早早进入梦乡...

---

Day 1（2024.10.26）

上午

由于前一天睡得挺早（相较于平常），生物钟在 $5$ 点就叫醒了我，后面凭着意志力又睡了 $1.5h$ 就起床了，起床洗漱来到饭堂，遇到了 xzk，发现饭堂还没开门，唐等半小时，和 xzk 浅浅回顾了一下知识。

吃完饭先回到不用作考场的机房听一下歌，顺便看了一下以前做过的总结，特别的，记忆中对于某道线段树优化的题还看了不久（铺垫）。

上午考普及组，考前打了学校的模拟赛和ABC都打得不怎么好，本来是信心赛把信心打没了，但还是相信自己，淡然入了考场，坐在考位上，先修养身心。

$8:27$ 解包，阅题，本来和 ljs 说好倒开题的，但看到最后一题的题面后没有多少自信，便回到第一题了。

$8:30-8:40$ 用数组计数，小细节错误调了一下，$10min$ 切出第一题。

得分：$+100pts$

$8:40-8:50$ 一开始看题，感觉那么长，又有点像搜索，仔细看，原来都是忽悠人的，直接照着打就可以了，也是 $10min$ 切出第二题。

得分：$+100pts$

$8:50-9:13$ 一眼看了 T3，感觉很简单，直接用个小 dp 过了样例，发现没有大样例，感到点小疑惑。

得分：$+50pts$

$9:15-11:10$ 回到了 T4 发现还有近两个小时，打算死磕这一题，看懂题目后没什么思路，以为是建图优化（不怎么会），有点小慌；

直接看数据范围，发现 $r\le 100$，豁然开朗，那不就是 $O(rn)$ 预处理，再 $O(1)$ 查询嘛；

一开始很好定义 $f_{i,j}$ 表示到第 $i$ 轮时，最后一个数字是 $j$ 是否可行。

关键难在如何转移，最暴力的肯定是 $O(n^2)$ 预处理两个人是否可以接龙再转移，一时半伙没想到怎么优化了；

插曲 I

拿出藏再口袋的润喉糖，犹豫吃不吃，算了，趁监考老师没看到，撕开包装，快速塞入口中，把包装扔到笔盒里；

吃完糖后，口中一阵清爽，然后就灵光一现了。很显然，这里的 $O(n^2)$ 已经无法优化了，只能再从定义上优化，修改后变为 $f_{i,j}$ 表示到第 $i$ 轮时，最后一个数字是 $j$ 这个方案是否可行，不可行则为 $0$，否则分类，若只有一种情况就单独记录这个来源，有多种情况就赋为 $inf$；

注意到题目中有坑点：一、同一个人不能连续接龙两次；二、每次接龙有长度限制。对于第一个，我属于脑电波对上了，往判断这个人是否可以接第 $i-1$ 轮的龙上想，起初我是用 map 来记录并判断的，确实有效，过了前几个样例，很兴奋；第二个也很容易处理，就是个非常小贪心；

但到倒数第 $3$ 个大样例时就挂了，抱着侥幸的心理测后面的大样例，发现竟然还用了近 $30s$，当时脑子懵掉了；

找了很久的错误，感觉理论时间复杂度应该不会跑那么慢，那应该是 vector 和 map 常数过大导致的，然而 vector 明显不能动，那肯定是 map 出问题了，然后就优化优化，ok，成功优化到了 $4s$，这时候又幸运地发现之前的答案错误竟然全都对了？全部大样例都过了？太好啦；

不过 $4s$ 感觉还是跑不过的，再考虑优化时间，然后我就神奇地删掉了刚修改完地计数判断部分，发现竟然还能过大样例！！！这个操作是多余的，没开 O2 时间优化到了 $2s$（其实是不会考场上开 O2），蛙趣，CCF的少爷机+开O2+限制 $2s$，那感觉应该是过了，啊啊啊啊好兴奋，竟然能 AK 啦。

得分：$+100pts$

插曲 II

心情激动的我想喝点水平复一下心情，结果不小心打翻了水壶，所幸没有水碰到电脑部件，举手示意监考老师帮忙擦干净，就开 NOI Linux 检查了。

$11:10-11:40$ 当我检查到最没有把握的 T3 时，我随手测了个很大的数，发现我的 DP 输出不了，立刻明白，答案可能会很大，会爆 long long，于是改用 string 的 DP，当我改完再输入一组最大的 $100000$ 时（为什么我不多搞几组，啊啊啊），能输出正确答案，不过出结果时机子卡顿了零点几秒，可是考场上的我没多想，以为稳了，就没继续改了（留下遗憾）。

得分：$+0pts$

$11:40-12:00$ 反复检查，重新测大样例，打坐喝水，盯着大屏幕的倒计时，小眯了一会儿。

$12:00$ 不明不白地带着遗憾离场...其实那时刚出考场时是兴奋的。

本应得分：$100+100+100+100=400pts$

期望得分：$100+100+50+100=350pts$

中午

中午吃饭时谈了一下早上的题目，发现大多数人 T3 做法都和我的不一样，当我说出用 DP 做的时候，ljs，xzk立刻就告诉我会 MLE，我人傻了，思考良久，发现对哎...

饭后回到宿舍，发现 ljj 的 J 组后两题的所有思路和我一样，应该和我同分了，还听说，T4 难住了大佬 ljs，hk，众人估计红橙黄绿，但听 xzk 说 LA 群已经开始热火朝天地聊 T4 是下位蓝和上午上位绿，不管了，去睡觉了。

醒来后，先去机房听歌水谷，带了两颗润喉糖。

下午

考提高组，有点小紧张，不过没多大关系...

$2:27$ 解压，看题。

$2:30-2:45$ 第一眼 T1，以为会像 GDKOI-J 时出逆天贪心，推了一下，很简单的贪心（怎么又和上一年一样放签到题）

得分：$+100pts$

$2:45-4:45$ 看了 T2，题面过长，一开始没咋看明白，还要求公式？太狗了，先跳去看下，T3 题面简洁，但看起来是个不好做的 DP，又回到 T2，认真看了一下题目，发现第一问很好求，可以直接用前缀和维护区间测速仪的个数，再直接用题目好心提示的公式求出当前车辆的移动区间，判断区间内是否有测速仪即可；

在分析第二问，一开始没思路，偷吃一颗润喉糖，接着就发现可以转化为线段问题，反着来想，其实就是区间线段最小线段覆盖问题，那就可以直接用排序+贪心解决就可以了，不过精度问题+细节+玄学问题调了我大半天...

得分：$+100pts$

$4:45-5:50$ 开 T3，很显然先预处理每个数上一次出现的位置，选择转化题意，由于上一题的影响，我就转化成了线段，然后就想偏了，以为不用所有点都染色（白白浪费 $1h$）；

插曲 III

由于有蓝红两种颜色，那时脑子恍惚出现了赛前复习看到的那一题，不过感觉不一样，就跳过了（啊啊啊，与正解擦肩而过，呜呜呜）。

就是这道题，赛前复习到的这篇文章。

当时想着先冲部分分，再优化嘛。

定义 $f_{i,j,0/1}$ 表示第 $i$ 位染 $0/1$ 颜色，前一个与其不一样颜色的位置在 $j$，转移忘了，不过一次就过了样例，可惜大样例错了，一直在思考转移哪里错了，时间就这么过去了...

$5:50-6:00$ 把仅剩的一颗润喉糖吃了（挽救了我一下），看了一下超长 T4，勉强看懂，不过题目信息挺抽象的，感觉很难做，超级难，只能冲 T3 了。

$6:00-6:20$ 吃完糖脑子清醒了不少，再看题目，发现刚刚弄错题意了，时间不多了，只好先打 $O(2^n)$；

得分：$+25pts$

接着直接干 $O(n^2)$，发现可以直接定义 $f_{i,j}$ 处理到第 $i$ 位，前一个与其不一样颜色的位置在 $j$，转移的话，其实说实话我也不知道怎么想的，我甚至没打草稿，头脑一热谁便乱打就过了大样例。

得分：$+25pts$

$6:20-6:25$ 那时以为 $250pts$ 也不算差了，就去开NOI Linux检查前面代码了（现在看来也算挺后悔的，不过人生如此，总会有遗憾）。

$6:25-6:30$ 打坐，祈祷，闲下来再看 T3 的转移方程式子，突然发现可以用线段树优化，但确确实实没时间打了。

$6:30$ 略带遗憾离场。

本应得分：$100+100+100+0=300pts$

期望得分：$100+100+50+0=250pts$

两场都没发挥到最好，没事，就这样吧...

晚上

回到家，上Q群讨论，发现 sssy 的人分数都挺高的，有好几个 $300+$ 的，还打听到大佬们全都是用二分做的提高组 T2，就只有我直接硬代公式，那时就有点小慌，怕挂分...

还怕 J 组的 T4 会超时，只能静等出分...

---

Day 10(2024.11.4)

whk 二检的前一天，已经等了一周了，GD 还不出分数线，应该不会像上一年那样提前出了，结果下午下课来到机房，登上洛谷，发现 【初分已公布】，犇犇也都聊得火热了，心跳加速了。

打开 NOI 官网，发现一直转，很卡，虽然等了几分钟，但对于我来说就是煎熬，终于进去了，先看 J 组，点进去 $100+100+50+100=350$，和我预测的一样；

接着就是重要的 S 组了，手点进去的时候不断的发抖，$100+100+50+0=250$，一分没挂！！激动得我飞奔回教室，发现没人，又飞奔回宿舍告诉了老妈，再次回到教室坐下，才发现全身已是汗。

小道消息：GD J 组一等 $260$；S 组一等 $180$。

关于 S 组的分数线，我还以为很高呢，起码有 $230$ 结果...以前都是希望分数线低，怎么自己考高了一点就盼着分数线高了呢，我怎么成这样了...好吧，说实话，我现在已经开始希望能在 NOIP 上能考好且祈求分数线低一点了...