CSP-J/S 2023 游记 - 洛谷保存站

本文章同步更新在 [cnblogs](https://www.cnblogs.com/twilight-star/articles/17957377)。

### Update on 2025.5.28
因为这篇文章是初二写的，~~当时心智不熟~~，所以写了很多废话，把一些考前训练的情况写了下来，显得有些偏题。为了不那么啰嗦，我把这一部分放在了最后。

# 正文

这是本蒟蒻第二次参加CSP比赛，特此开一篇游记。

# 初赛篇

## DAY 1（2023.9.16 SAT）
今天考初赛，上午普及，下午提高，在成都石室中学考。

上午考普及，遇到了初三学长lht和zjc，其中zjc还跟我一个考场。做题做的还是挺顺的，发现今年普及组没考位运算？？？这玩意放普及里算难的知识点。

普及组好像有一道题没有正确答案，所以广播说要该选项，~~为了防止你猜出答案，还贴心的给你改两个选项~~。CCF出的题挺有质量的。最后一道甚至是原题，就是[这道题](https://www.luogu.com.cn/problem/P2758)的代码。做完还有 $ 40 $ 分钟，检查完就睡了一会儿。

出考场觉得分数线可能上 $ 80 $ 分（夸张地说）。

下午考提高，zjc分到隔壁考场去了。

选择题有一些题不会，随便懵了一个。~~不是，怎么提高组才考位运算啊，还涉及到越界问题~~。 完善程序最后一题实在看不懂了，只能懵了一个，然后做完仅剩 $ 10 $ 分钟，赶紧检查。

怎么感觉今年的题是两个极端呢？一个贼难，一个贼简单。

出考场遇到了JMR，他说今年考的很简单，还给我解释了一大堆我听不懂的东西。

## DAY 10（2023.9.25）

出分了，普及 $ 88 $ / $ 76 $ ，提高 $ 71.5 $ / $ 53 $ ，侥幸通过。

JMR普及 $ 98 $ ，提高 $ 92 $ ，tql，orz。

# 复赛篇
  
 ## DAY 1(2023.10.21)
 
 上午普及，下午提高，考点在嘉祥外国语学校。
 
 跟JMR，SZZ等巨佬一个考场，感觉有点紧张。
 
 为啥嘉祥的主机放在脚下面啊，有点难放脚。
 
 普及组开题，原以为 $ T1 $ 是道签到题，发现毫无规律，怎么也推不出来，废了半个小时，决定先看 $ T2 $ 。
 
  $ T2 $ 感觉像贪心，每一次找最右侧的最小值，但我最后用的 $ ST $ 表维护的，时间复杂度 $ O(n \log n) $ 。
  
 上了趟厕所回来，感觉不甘心，这签到题我怎么可能做不出来？想着有什么性质，突然茅塞顿开，每一次的个数都 $ \times \displaystyle \frac{2}{3} $ 向下取整，每一次会删掉 $ \mod 3 $ 余 $ 1 $ 的数，，过得了 $ 10^9 $ 的数据。
 
 写完只剩 $ 2 $ 小时了，怕打挂了，写了个对拍拍了 $ 6 $ 万多组数据。
 
 继续看 $ T3 $ ，瞬间明白这是一道大模拟，怎么 $ CCF $ 又在 $ T3 $ 放大模拟啊。
 
 打了半个小时，过了样例，发现过不了大样例，改了 $ 10 $ 分钟，过了。
 
 喝了好多水，又去了趟厕所。
 还剩 $ 40 $ 分钟，不知道为啥我很慌，看了一眼题，直接打了一个 $ Dijkstra $ 的板子，打完还剩半个小时。
 
 不知道为啥，一上考场就没有拿特殊性质的激情，以及打暴力和对拍的热情了，四道题只有第一题打了对拍。
 
 然后后面耍了半个小时。。。（不是我怎么不对拍啊）
 
 蒋神一出考场就给我说很简单，他觉得他能 $ AK $ 。
 
 中午吃得有点饱，只睡了一小会。
 
 一脸懵的状态来到提高组考试。
 
  $ T1 $ 愣了半天才看到 $ 1\le n\le 8 $ 的数据范围。这不直接暴力吗。
  
  打了半个小时，过了大样例，自己随便造了组数据，结果把自己 $ hack $ 掉了，查了半天才发现没有初始化。
  
 转身看 $ T2 $ ，发现并不可做，直接打 $ n^3 $ 的暴力，想把它优化到 $ n^2 $ ，想了半天也想不出来，这时候感觉头有点晕。
 
 暴力打挂了，重构代码。。。
 
 过得了大样例，但明显这道题至少需要 $ O(n\log n) $ 的算法，死活想不出来，决定先搞 $ T3 $ 。
 
  $ T3 $ 又是大暴力，开了一堆 $ map $ ，打完了前三个操作，突然有点想上厕所，去了回来后就开始头晕，也就是用脑过度了，啥都想不起来，感觉就像中暑了一样，头跟发高烧一样热，什么都思考不了。
 
 测了一下 $ T3 $ 大样例，发现前三个操作也有问题，但我的大脑已经支撑不了我改题了。
 
 真的无语，只得看 $ T4 $ ，本以为是树形结构这道题会好做很多，结果发现更不可做，不只是大脑死机还是我太弱了（应该两个都有），反正我死活想不出来，想打特殊性质，码了 $ 70 $ 行发现打挂了，这时只剩下半个小时，又晕又慌，苦恼自己死活想不出来。
 
 在绝望与挣扎中慢慢死去。
 
 走出考场，人已经懵了，什么也想不起来，又遇到了JMR，他见到我的第一句话就是“今天的题好简单”，询问了一番发现他每道题的大样例都过了，他觉得他能 $ AK $ 。
 
 如行尸走肉般走出考场，SZZ跟我聊天，我说：“我考的太差了，只能明年再来了。”SZZ还安慰我说：“考好也只能明年再来。”对此我只能评价一句：“6。”
 
 回去测了一下小图灵，普及 $ 100+0+100+35=235 $ ， $ T2 $ 又挂了，真的无语，提高 $ 100+45+0+0=145 $ ，但在洛谷上是 $ 100+50+0+5=155 $ ，又寄了。得知JMR普及 $ 385 $ ，提高 $ 400 $ ，祝贺他吧。
 
 破防了。
 
 沉默了一晚上。

## DAY 2(2023.10.22)
 
 崩溃了一整天。
 
 一上考场就紧张，用脑过度导致提高组崩盘，普及提高全军覆没。
 
 这也就是我的问题所在。
 
 平时普转提模拟赛 $ 300+ $ ，提高模拟赛 $ 200+ $ ，结果普及才 $ 200 +$ ，提高才 $ 100+ $ 。
 
 祝老师说正常人上考场缩水 $ 10\% $ ，而我直接缩了 $ 60\% $ 。
 
 考试时太紧张了，平时基本上每道题都会对拍以及测极限数据，结果正式比赛啥都忘了，要么感觉没法打暴力，要么打的就是暴力。。。反正普及加提高一共就只拍了一道题，而且自己也没怎么造数据。
 
 ~~完了，又有人要说我们年级菜了。~~
 
 考完后内心是极度崩溃的，想不出正解，打不出暴力，骗不了性质。
 
 平时打模拟赛想不出正解时都会尽可能骗分，这次，突然不会骗了。
 
 去年是不知道有大样例，今年是太相信大样例，普及 $ T2 $ 甚至过了大样例后没对拍。
 
 考之前给自己太大的压力，感觉必须得 $ AK $ 普及组，这下好了，一等都差点没了。
 
 考试的时候满脑子都是循环播放的音乐，放完这首放下一首，根本没法停下，就算是最后死机的那段时间也是这样。
 
 回家后父母和祝老都说如果用脑过度，就趴一会，休息一下，总比一直晕乎乎地打代码好，打一遍有打不对，到头来还得重构一遍，浪费了不少时间，然后越来越慌，一直想着自己一定要高分通过，一直死磕。
 
 最后不仅连芝麻没捡到还丢了一个西瓜。
 
 如果当时早点放手提高 $ T2 $ ，尽早地去打 $ T3 $ ，也许一等就稳了。
 如果当时头晕就趴着休息一会，稍微好一点再去打 $ T3 $ 和 $ T4 $ ，也许就能拿到更多的分了。
 
 但这个世界上哪有这么多如果呢？
 
 理想很美好，现实很残酷。
 
 天天想着 $ AK $ 普及组，提高组 $ 300 $ 分，不如静下心来去做好每道题，哪怕做不出来也要把能拿得分全拿了，不放过一丝的希望。
 
 还有一个问题，平时模拟赛后改错不积极，如果考到原题，那还不得错？
 
 做题看题解看得太早了，基本上想个 $ 10 $ 分钟想不出来就去看题解了，至少应该把赛场上那种死磕的力量发挥出来，实在过不了再看啊。
 
谁没经历过失败？谁的人生就是一帆风顺的呢？只要我们放平心态，尽自己全力，无论成败，我们一定都是成功的。

没有谁的人生是由一场考试决定的，从哪里跌倒就从那里站起来。

所以我们应该放平心态，不说超常发挥，就算是正常发挥，我也应该是双一等（毕竟明显感觉今年普及 $ T3 $ 比去年简单得多，提高 $ T1 $  、 $ T3 $ 也简单很多）。

要养成一种习惯，题题先打暴力，想出正解后再对拍，过拍后测极限数据看一下常数是否过大。

希望未来看到这篇游记的我不再重演悲剧，不畏挫折，勇往直前。

$ Try $   $ your $  $ best $  $ to $  $ realize $  $ your $  $ dream $ . $ We $  $ will $  $ never $  $ surrender $  $ ! $ 
 
 ### DAY 4 (2023.10.24)
 
 改了一下题，提高 $ T2 $ 是一道 $ Trie $ 树，维护一下每个点被经过了多少次。普及 $ T2 $ 只用维护当前节点到 $ 1 $ 号点的最小值所在节点，没必要用 $ st $ 表，还容易写挂，关键还要多一个 $ \log n $ 。
 
 ### DAY 8(2023.10.29)
 
 出分了，普及组 $ 100+0+100+70=270 $ ，提高组 $ 100+35+0+0=135 $ 。
 
 发现自己普及 $ T4 $ 题读错了，我以为可以在每个节点停留，然后这样还有 $ 70 $ 分。。。
 
 提高1=应该没了。OIerDB上我是 $ 6 $ 级，洛谷上只有 $ 5 $ 级，一问才知道洛谷必须要 $ 140 $ 才能六级，我的蓝勾就这样没了。。。我提高 $ T3T4 $ 随便拿个特殊性质就蓝勾了。。。
 
 ~~果然不出所料，CCF用脚造数据~~。
 
 明年再战吧！！！
 
 虽然有很多遗憾，但怎么也补不会来了......
 
 听听《大海》，放松一下吧......
 
 真的好崩溃......

本场比赛的失败原因：
1. 过于想考好，导致考试时压力太大
2. 天天作白日梦，幻想着自己能薄纱全机房
3. 不对拍
4. 没经验，没怎么参加过大赛
5. 菜是原罪
6. 急于求成

# 考前模拟赛记录

## 2023.9.12 TUE
祝教练让我们打一场模拟赛，~~不是怎么初赛前几周疯狂练初赛，而初赛前最后一节课练复赛啊~~，祝老师说是普及转提高难度的。

JMR坐我对面，压迫感十足。

拿到题，看见 $ T1 $ 就觉得不正常，手玩了一下就写 $ T2 $ 去了。

$ T2 $ 随便推了下结论打了几十行就去看 $ T3 $ 了，看完后一脸懵，想着建图跑拓扑排序，最后发现写假了，转而去看 $ T4 $ 。 $ T4 $ 一开始看起来有点像 `` dp ``，但怎么也推不出式子，换了种思路，用拓扑排序做。

蒋神提前 $ 1.5 $ 小时交卷， $ 0+100+100+100=300 $ 分，T1挂了。

我开始有点慌了， $ T4 $ 打完后回看 $ T3 $ ，想了好一会也想不出来，提前 $ 0.5 $ 小时，交了。

好家伙， $ T1 $ 挂了，后来跟JMR一谈就发现我们俩错的一样，没有特判除以 $ 0 $ 的情况。。。 $ T3 $我多测没清空，连暴力分都没拿到（暴力有 $ 50 $ 分）。

最终得分 $ 0+100+0+100=200 $ ， $ rk2 $ 。

最后问JMR把 $ T3 $ 问懂了。有点像[这道题](https://www.luogu.com.cn/problem/P4310)

## DAY -27(2023.9.23)
今天祝老师又让我们打模拟赛，这次蒋神直接坐我旁边。

打开题， $ T1 $ 随便看了一下，随便写了一个结论，感觉不可能这么简单，写了个对拍拍了一万多组，过了。

$ T2 $ 一眼看去，毫无思路，~~反正没思路的题多半是DP~~，直接提桶跑路。
 
 再看 $ T3 $ 时，似乎是道图论题，而且是最短路，在 $ m\le  5\times 10^5$， $ n\le 10^5 $ , $ k\le 50 $ 的情况下直接 $ k $ 遍最短路，时间复杂度为 $ O(kmlogn) $ ,并且带了一大堆常数，测了一下 $ 70 $ 分的数据，感觉能拿。
 
看了一眼 $ T4 $ ，妥妥数论题，胡乱用 $ O(n) $ 的时间算错排，然后拿了个 $ n\le 10 $ 的暴力，溜了。

最后只得看 $ T2 $ ，推了一会式子，发现很复杂，时间复杂度为 $ O(n^3) $ ，而且 $ n\le 10^5 $ 。。。

想到可以用排序优化，这样就是 $ O(n^2) $ 的了。

溜了溜了。。。

然后最终得分 $ 100+ 75+30+10=215  $ ， $ rk1 $ 。

一问才知道，隔壁蒋神 $ 100+100+0+0=200 $ ，他懒得打暴力。。。他说 $ T4 $ 他想到了一种 $ 55 $ 分的做法。

最后听了蒋神讲题，看了题解， $ T3 $ 最后可以用拓扑排序优化，又因为边权为 $ 0 $ 或 $ 1 $ ，可以不用优先队列。

如果不是蒋神不打暴力，本蒟蒻怎么可能 $ rk1 $ ？

## DAY -22(2023.9.28)

去外地的路上，没什么事，参加了某省一场线上模拟赛。

$ T1 $ 看了一眼，猜了一个结论， $ 6 $ 分钟交了。
 
  $ T2 $ 只会暴力，还打了两个版本，感觉差不多，随便交了一个，真的不会优化了。
  
 $ T3 $ 是道数论题，推了半天推不出来，拿了暴力分就跑路。
 
  $ T4 $ 怎么也打不出暴力。。。
  
 最终得分 $ 100+90+20+0=210 $ ， $ rk5 $ 。
 
 看题解，知道 $ T4 $ 是道差分约束，正解比暴力好打。。。
 
  $ T2 $ 还需用并查集优化。
  
 我太蒻了。。。
 
 ## DAY -18(2023.10.03)
 
 晚上没什么事干，随便刷了[一道紫题](https://www.luogu.com.cn/problem/P5304)，太难改了（应该是我太蒻了），顺带写了[一篇题解](https://www.luogu.com.cn/blog/hard-plan/p5304-gxoigzoi2019-lv-xing-zhe-ti-xie)。
 
## DAY -17(2023.10.04)

又刷了一道紫题，发现可以写题解，写了[一篇题解](https://www.luogu.com.cn/blog/hard-plan/p4652-ceoi2017-one-way-streets-ti-xie)交了。

## DAY -16(2023.10.05)

返程路上没什么事干，又去跟之前的人打了一场模拟赛。

$ T1 $ 是个方差问题，最后推了一下性质， $ 23 $ 分钟交了。
 
 感觉题比 $ 28 $ 号的题要难，死磕 $ T2 $ ，受[P8817 [CSP-S 2022] 假期计划](https://www.luogu.com.cn/problem/P8817)的影响，直接维护树上当前节点可达的最大值与次大值。
 
 先打了一个小时，过不了大样例，只能打个暴力，搞对拍，拍出来几组错，甚至有一处把 $ = $ （赋值）打成了 $ < $ 。
 
 改了 $ 2 $ 小时，终于过了大样例，第 $ 154 $ 分钟交了。
 
 然后看 $ T3 $ ，感觉能拿特殊性质，拿完就溜了。
 
  $ T4 $ 概率与期望 $ + $ 计数题 $ + $ 有理数取余，直接溜了。
  
  最后得分 $ 100+100+0+0=200 $ ， $ rk1 $ ， $ T2 $ 全场唯一 $ AC $ ，我把 $ T2 $ 扒过来了，[看这里](https://www.luogu.com.cn/problem/T387415)。
  
  $ T3 $ 把 $ n\times (n+1) $ 写成了 $ n\times  (n-1)$， $ 20 $ 分没了，悲。
 
 ## DAY -13(2023.10.08)
 
 [这篇题解](https://www.luogu.com.cn/blog/hard-plan/p4652-ceoi2017-one-way-streets-ti-xie)通过了，本蒟蒻第一次通过题解。
 
## DAY -7(2023.10.14)

每周模拟赛 $ (1/1) $

~~中午最后一节课困得要死，中午死活睡不着，下午头昏脑胀，晕的很，无语~~。。。

祝老师之前说今天考的是提高难度的，结果拿到题感觉完全不像，明显是普转提的难度。

看了题，趴着推 $ T1 $ ，实在是困得不行，只能多喝水，随便搞了一会儿就出来了，是个拓扑排序，这道题看起来跟图论没任何关系，但就是个图论。为了验证它的正确性，所以搞了个对拍，~~拍了六千组，出数据的程序炸了几次~~。。。但思路是正确的。

$ T2 $ 裸的暴力 $ dp $ ，没什么说的，懒得对拍。

$ T3 $ 是一个树上问题，甚至有点想用树链剖分，发现没必要，随便维护一个值，溜了，又懒得对拍。

还剩 $ 2.5 $ 个小时，看了一眼 $ T4 $ ，感觉像图论，发现不是，是个 $ dp $ ，维护了一下，把 $ O(n^3) $ 压成了 $ O(n^2) $ ,然后题意描述的什么鬼，想了半天想明白了。

蒋神提前 $ 1.5 $ 小时交，压力直接给到在场所有人。

提前 $ 1 $ 小时，我也交了。

最终得分 $ 100+100+100+38=338 $ ， $ rk1 $ 。甚至蒋神也是 $ 338 $ 分，最后一题都是 $ 38 $ 分。

祝老师让我们看第四题的 $ std $ 的代码，不是，怎么跟题意写的不一样啊。

祝老师说这三道题都是 $ atcoder $ 原题，回题面一看，跟 $ pdf $ 的  $ T4  $ 完全不一样， $ pdf $ 上翻译时多加了一句话，导致题意完全不一样。而数据又是从 $ atcoder  $ 上搬过来的。。。

赛后 $ 2 $ 分钟，改过了。。。

本来有机会 $ AK $ 的，我从来没 $ AK $ 过任何一场比赛（包括入门赛）。算了，终究是我太菜了。

[Kenkoooo](https://kenkoooo.com/atcoder/#/table/) 上 $ T2 $  $ 1500 $ 分？

原题：

T1：[[ABC216D] Pair of Balls](https://www.luogu.com.cn/problem/AT_abc216_d)

T2：[[ABC175E] Picking Goods](https://www.luogu.com.cn/problem/AT_abc175_e)

T3：[[ABC187E] Through Path](https://www.luogu.com.cn/problem/AT_abc187_e)

T4：[[ABC212E] Safety Journey](https://www.luogu.com.cn/problem/AT_abc212_e)

## DAY -4(2023.10.17)

~~终于有机会打提高模拟赛了~~。

$ T1 $ 想了半天，发现是个二分 $ + $ 差分，写完即溜。
 
 ~~算了，还是拍上吧。~~
 
  $ T2 $ 读了题后一脸懵，是一道计数```dp```？！好吧，真的不会。。。
  
  $ T3 $ 读完先把 $ n\le 8 $ 的暴力拿了，再看一眼 $ n\le 14 $ 的做法，想到了状压```dp```，但是感觉空间会炸，就没写。
  
  $ T4 $ 真的不会，随便打了个暴力，过了样例，然后就开始罚坐。。。
  
  最终成绩 $ 100+0+20+7=127 $ ， $ rk $  $ ？ $ （鬼晓得我多少名，有的人交了好几次，甚至还现场改），发现自己真的好逊，难怪有人说我们初二的有点逊，而我就是最逊的那一个，qwq。算是一场静心赛吧。
  
真的有点破防。

## DAY -2(2023.10.19)

考前的最后一场模拟赛。

虽然逊，但还是要努力。

$ T1 $ 乍一看是一道扫描线，有点像 $ NOI2023 $ 的 $ T1 $ ，但发现这道题性质不一样，更简单，因为 $ xy $ 轴是每个矩形的对称轴。
 
 维护一下其中一个象限，最后答案 $ \times 4 $ 就行了。
 
 再看 $ T2 $ ，推了一下结论，发现一个惊奇的事，答案跟给出的图没有任何关系！！！相当于说给的数据是干扰项。
 
 感觉不真实，先做 $ T3 $ 吧。
 
  $ T3 $ 明显的```dp```，随便列了一下状态转移方程，发现情况好多。
  
  一个一个打完后，过了样例，自己随便造了一组数据，结果过不了。
  
 发现几处笔误，改了过来，还是过不了。
 
 发现少讨论了一种情况，加上了，过了，但是没过大样例，把范围开到极限，过了！？
 
  $ T4 $ 一脸懵，随便写了一下 $ n\le 20 $ 的暴力，打了个 $ O(n^5) $ 的暴力。
  
 交了，最终成绩 $ 100+95+100+10=305 $ ， $ rk1 $ 。
 
  $ T2 $ 结论猜对了，但没判不合法的情况。
  
  $ T3 $ 赛时改了 $ 1.5 $ 个小时，改对了。

正在渲染内容...