CSP&NOIP 2022 游寄
TianLuen
·
·
个人记录
9.14
数学老师催我交试卷，否则不让我上课；语文课前一分钟交流即将轮到我；语文、英语默写没背；语文作业欠了半个月；英语作业没做完；几天后就要初赛……
综上所述，停课。
9.15-9.17
陆续有人加入停课行列。这几天，做了几套初赛卷。我有题上应该就一两年的初赛没刷过了。不知道今年难度如何。
9.18
CSP 初赛。考试前一小时，我们在押题、复习、批判主定理。
开考，拿到试卷，看了前两题，感觉蛮正常，real time 前几天正好对大纲刷过。然后看到后面宇宙射线题，我：坏了，基数排序，忘记看了。也就两分，不要紧。
后面选择问题不大，盯着那个有趣的死循环看了一会，然后继续做了。
三个阅读程序，感觉水温有点不对，甚至又出现了基数排序，大寄。
完型一，我也不知道这玩意怎么弄，结合着特殊情况蒙题，甚至对了 4 个。
完型二，一眼眼熟，以前学过。定睛一看，tmd 一个选项考了 12 分，剩下 3 分白送。
考完后的反应：苏州分数线 90 +。
对着一份答案看，90 没有了，感觉大危。
9.19-9.26
恢复文化课。信息，只管晚上练练。
数学大寄，班里倒一。
至于初赛，民间答案估分大致在 77 左右。后来常州先出了分数，这个分数在常州大约排 40 名，按苏州名额算，非常危险。
几天后苏州出分，我只有 75，分数在苏州排名四十出头，其中有几个同分，而给满名额则分数线恰好截到我的分数，还是很危险。理论上应该是压线过，但不排除被线压过的可能。
有一个集训，计划参加。
9.27
正式出分。苏州额外加了 16 个名额，分数线来到了 72.5。我们学校总共过线了 4 人。
此时一位同学不知道从哪边整来了个名额，以远低于分数线的成绩进入了第二轮。所以我们学校进第二轮的共 5 人。
9.28
## 9.29
学校运动会，由于我没有项目，于是到机房训练。
## 9.30
上午机房训练，下午赶去（正好国庆，路上堵得很），晚上住在附近酒店。晚饭价格高得离谱。
夜里有场 CF，开打。先切了 CF 的 AB 题。
## 10.1
调完 AB 题，看 C。我对博弈论一无所知，于是尝试找规律。最终经过归纳，还真找到规律，直接输出，甚至过了，但是就怕 C 被 system test 卡掉。
早上惊奇地发现 C 过了，B 被卡掉了。稍稍上了点分。
上午模拟赛迟到了几分钟。先看 A 题，感觉很蒙，最后放弃思考，写暴力拿了 $90$ 分。再看 B 题，感觉不难，码了一会交了看 CD。C 是字符串题，尝试现学 manacher 失败；再看 D，感觉毫无头绪。最后几分钟发现 B 没过大样例，寄。最终出分一看，大寄。
中午 zja 点外卖，点了一份餐具。于是一双筷子被掰成两双筷子，把水杯当饭杯，再用上薯片罐，属于是八仙过海。
下午把 AB 两题补了。听了 DP 的课，完全不理解，我感觉我应该去入门组。
## 10.2-10.7
继续集训。
6:30 - 6:55 起床、洗漱
7:00 - 7:30 早饭
7:30 - 12:30 训练
12:45 - 14:00 午饭、休息
14:00 - 17:00 训练
17:30 - 次日6:30 晚饭、休息
一天晚上 zzx 那边点了份巨贵的外卖，很丰盛。筷子勺子是齐全的，但是缺少容器。接着又是一发大显神通，zja 和 thh 一个人拿锡纸折了个碗，一个人拿锡纸折了个盘。我肯定也需要一个容器的，看到桌上有张圆形的锡纸，于是我拿起来折了个过滤器，效果还蛮不错的。
其中有一天休息。正好那一天不知道怎么，中午开始我头痛得厉害，想补习知识点也撑不住，于是睡觉。下午可能睡了五六个小时吧，除了食欲之外都恢复正常了。那天晚上不知道谁点的水果披萨，感觉一点都不好吃。
最后一天下午返程。交通还算顺畅，不像来的时候那么堵。至此，线下集训结束。
## 10.8~10.16
学了一星期文化课。不过每天晚上还是去机房的。
## 10.17~10.25
有几天停了半天文化课。
## 10.26
晚上接到紧急通知：关于 JS-CSP-J/S2，它 SPFA 了。
## 10.27
中午接到紧急通知：关于 JS-CSP-J/S2，它 NOIP 了。
还好~~散装~~江苏拆成了三个考点。考点离学校不远。
复习了一下线段树。
## 10.28
比赛前一天，基本还是在机房待着，中间出去上了节数学课 ~~（数学老师盛情难却）~~。
感谢班主任送了我一盒巧克力。
复习了一下最短路。
## 10.29
复赛。上午到校，考前最后放松了一下。正午从学校出发，预计是一小时到考点，实际只用了半个多小时，由于考点还不让进，就在附近坐了会。稍微看了下之前的网络流板子。
令我比较疑惑的是，考场不让带饮料进去，因为里面提供水。我觉得么，理论上来讲把饮料的标签撕了就行，但是还是不给带进去。不过水杯可以带进去。这是为什么呢？
开考前的试机，写了个快读的板子（然而后面没用上），键盘手感一般，不过比去年 NOIP 考试时用的好。初始的鼠标灵敏度太逆天了，赶紧改了。
拿到了试题，先浏览一遍。看了下 A 题，嗯，图论。A 题里面那个**只经过 4 个不同的景点**让我有点好奇，这个 4 肯定不是乱给的，这就是这题的切入点。然后再看看 B，看着还蛮简单的，有区间查询，那肯定就是线段树了，前天刚复习过。然后瞄了眼 C，这题面怎么这么长，不看了。最后是 D，发现是树上问题，看下数据范围，有 $k\le3$，大概就是 D 的切入点，但很显然我不会。
开 A。
浅浅分析了一下，考虑到中转次数有限，就想到了用最短路进行预处理。于是开始写 dijkstra。写完了，随手一测，甚至一次性写对了。但是仔细一想，这玩意似乎要全源最短路？但是我不会写 johnson，这就尴尬了。于是写了个 floyd，测了下 `n=2500`，好了，铁定寄了。那怎么办？挂在没认真学 johnson 上了？于是抱着尝试的心态，试着用 dijkstra 跑全源，结果发现跑得出奇地快，是我低估了 dijkstra 的效率了。
好，预处理部分写完了，接下来就是处理怎么走四个景点。四个景点，这让我想起来 10 月初的一场 ABC 的一道题，好像是求矩阵异或最大值来着，做法是折半搜索。那么这题折半枚举可行吗？是可行的，每一半正好是 $n^2$，拼起来的复杂度正好也是 $n^2$。
赛时做法：
首先对于全部 $n$ 个点，执行 $n$ 遍全源最短路，处理出 $i$ 到 $j$ 至少要经过 $dis_{i,j}$ 条边。
然后，枚举 $i,j(2\le i,j\le n,i\ne j)$，在满足 $dis_{1,i}\le k+1,dis_{i,j}\le k+1$ 的条件下，计算出从 $1$ 到 $j$ 的最大分数和次大分数 $a_j$，同时记录下得到最大和次大分数时经过的点 $b_j=i$。
接着，枚举 $i,j(2\le i,j\le n,i\ne j)$，即枚举路径 $1 \rightarrow b_i \rightarrow i \rightarrow j\rightarrow b_j\rightarrow 1$。在满足路径相邻两点的距离不超过 $k+1$、四个景点互不相同的条件下，计算出这条路径的答案，取最大值。因为要保证四个景点互不相同，所以不能只维护 $a_j$ 的最大值，还要维护其次大值。**事实上，还应当维护第三大值，不然会漏解。我赛时没有考虑到这一点。**
写的过程中稍微遇到了一点问题，以至于出现了样例 2，再过大样例，最后过样例 1 的奇怪情况。不过还好，最后总算是过样例了。
开 B。
这玩意一看就是维护一个静态的数据结构了，由于我不会写 ST 表和树状数组，所以我写了棵只能查询区间最值的线段树。线段树甚至也是一次写对的。
之前刷板子的时候养成了封装数据结构的习惯，这个习惯甚至派上用处了。
很显然，这是一个贪心。这个贪心需要一个简单的分类讨论，根据第二个人区间最值的大小，分三大类六小类处理。这时，我发现需要维护第一个人的总最大值、总最小值、负最大值、正最小值，第二个人的总最大值、总最小值。很简单，开六棵线段树呗（
赛时做法：
对于 $a，b$，正如上面所述，一共开六棵线段树（**或者其它可以用来查询区间最值的数据结构**）。
对于每组查询 $l_1,r_1,l_2,r_2$。
1. 如果 $\max\{b_{l_2}:b_{r_2}\}$ 与 $\min\{b_{l_2}:b_{r_2}\}$ 异号，则答案为 $a_{l_1}:a_{r_1}$ 中正数最小值 $\times\min\{b_{l_2}:b_{r_2}\}$ 与 负数最大值 $\times\max\{b_{l_2}:b_{r_2}\}$ 的较小值。**注意考虑不存在正数最小、不存在负数最大、全为 0 的情况。**
2. 如果 $\max\{b_{l_2}:b_{r_2}\}\le 0$，则必然取 $\min\{a_{l_1}:a_{r_1}\}$。如果其值为正，则 $\times\min\{b_{l_2}:b_{r_2}\}$，否则 $\times\max\{b_{l_2}:b_{r_2}\}$。
3. 如果 $\min\{b_{l_2}:b_{r_2}\}\ge 0$，则必然取 $\max\{a_{l_1}:a_{r_1}\}$。如果其值为正，则 $\times\min\{b_{l_2}:b_{r_2}\}$，否则 $\times\max\{b_{l_2}:b_{r_2}\}$。
开写。虽然一开始分类考虑不周，不过总体来讲也没被卡过久吧。
开 D。
这时考试时间还有两小时不到点。$k=1$ 的情况，可以写个 LCA，但是倍增 LCA 我怕写挂，而且性价比一般性，拿不满 20pts。$k>1$ 的情况不太会弄，但肯定也和 LCA 有关，可能是要树剖？应该不会。
开 C。
题面太阴间了。这玩意意思不是很懂啊，我理解为是判断每个点的出度是否都为 $1$。本来想写全分的，但怎么看都不对劲，最终到考试结束也就随便写了几个操作，还不一定对。
考完的感受是：前两题质量不错，第三题质量就差一点了，第四题难了点。图上问题考了三题，有点多，不过如果是数论我更会寄。
所以结束时的估分是 200-。考前两天复习的一个线段树，一个最短路，甚至都用上了，蛮好的。希望分数少挂点。
## 10.30~11.7
回头稍微处理了一下文化课。
## 10.8
出分了。嗯，好像远高于预期。我 A 题的做法是假的，只维护了最大和次大，没有维护第三大，但是意外地得了 100pts。我 B 题的做法也是假的，主要是分类没有完全分清楚，但是意外地得了 95pts。我 C 题的做法完全假了，但是意外地得了 50pts。D 题没来得及写。最终得分 245pts。
## 10.9~11.11
文化课。
## 11.12~11.24
九成停课。
## 11.25
看了眼模板，发现绿题还有 3 个 tarjan 和一个博弈论没写。thh 说不太可能考 tarjan，于是就扔一边了。
考点省常中，下午出发出常州。有趣但又没那么有趣的是，我们这里高速下来必须进行核酸检测，常州高速下来核酸想做都被拒绝。
晚上各自外卖。隔壁四个人不知道在干啥，以至于后来都有人上门叫他们声音小点。
夜里也没干啥，稍微休整了一下就睡了。
CF 阴间场，不打。
## 11.26
早上 $6$ 点起床，精神还可以。早饭是每人一碗小馄饨 + 一杯豆浆 + 一个大饼。吃完馄饨已经差不多饱了，喝完豆浆已经不能再吃任何东西了。收拾了点东西，就去考试了。
省常中，看上去比我们学校要好不少。但不管怎么说，这里防疫松得离谱，考生和本校学生全混在一起，没有隔开。
没过多久就排队进考场了。我是二考场。一考场走了。很快，有个人过来，把我们二考场也带走了。意想不到的是，我们上了一个楼梯，然后发现楼梯通往机房楼道的门锁了，那个带队的打不开门，跑路了。整个考场的人在楼梯上被罚站半节课。后来我们最后进了机房，离开始还有半个小时。
到了 $8$ 点半，试题仍然没有下发。直到 $8:35$，题目才发下来，于是考试延长了 $5$ 分钟。
拿到了试题，先浏览一遍。看了下 A 题，好家伙，CCF 是吧，让人眼前一亮。A 题那个形式化题面我足足看了五分钟，觉得应该没什么问题，可以考虑前缀和瞎搞。然后再看看 B，喵了个喵？那个 $k=2n-1$ 和 $k=2n-2$ 很有意思，是关键信息。然后瞄了眼 C，好一个图论，还求方案数，一眼不可做。最后是 D，题面很简单，但是毫无头绪。
开 A。
前缀和肯定要的，于是我写了前缀和和前缀和和前缀前缀和（？）。经过一番调试，发现前两样例对了。测到第三个样例的时候，好家伙，答案是 $114\ 514$，我的评价是，惊世骇俗。一小时写完，然后没看了。
赛后发现这玩意多测好像要清空来着。
开 B。
想了一个小时，无果，拿 $k=2n-2$ 的分数跑路了。
开 C。
粗略想了一下，这题要缩点，要缩掉边双连通分量，算法是 tarjan。
好像有人在考试前两天说不太可能考 tarjan 来着。
没办法，考前没复习 tarjan，只能现推了。我只知道 tarjan 的核心是 dfn 和 low。写出来一个，随便试了下，好像对了。
缩完点之后剩下一棵树，然后……就不会了。
无奈，写了个 $2^n$ 暴力。tarjan 写了和没写一样。
开 D。
算了算了，写 $n^4$ 撤了。
综上所述，本场考试我以失败告终。
明年，最后一年，再战。
## 12.5
查分了。分数远低于预期。这叫风水轮流转，上次运气特好，这次运气就特差了。
得分是 10+0+0+0=10，历史第二低。我不理解为什么 T2 T4 能卡掉我全部分数。
我们学校一半人 T1 都 A 了，但是 T3 没一个人得分。嗯……
AFO...暂时的。明年是最后一年了，也看我干了这么多年，要是最后只能沦为 CSP-JS 一等，那可真是遗憾。但无论如何，今年的赛程就此过去了，虽然结果并不圆满。
## The End