CSP 2022 游记

· · 个人记录

Day -?

还有十天就要 CSP 了。

而我还在和联考的 T1 斗智斗勇。

感觉不如2019....水平

Day 0

black_trees 神说要面基。

询问了一点特征。感觉明天能面到。

Day 1

中午吃了点好的（神秘虾和神秘牛肉和神秘番茄鸡蛋 ← Meatherm 本体），然后一点半到考场。先找到了 smallbasic 和季老师。有点紧张，也找不到话说，有点尬。

我：季老师猜一下今天 T1 考什么

季老师：（掏出手机）这年代谁猜考什么啊，肯定猜题目英文名啊

我：（凑过去看了一眼）笑麻了.jpg

看到了很多熟悉的名字，什么 match, permutation, game, sequence, ....都在联考里面出现过大于一次。

真的很难蚌得住。不知道为什么能整出这种绝世好活。

然后来了一车面包人，看了下是绿色校服，应该是 cdfls 的。我瞬间想去找 black_trees，然后发现...诶怎么没什么符合特征的。

没找到 black_trees，不过我妈不知道咋的怎么把 grass8woc 神认出来了，有点震惊。我直接边走边拜谢。感觉 grass8woc 无论从哪个方面都非常 strong 啊！而我不仅 oi 菜，两年了也还在 178 的憨憨身高一点没动过，流泪...

问了下 grass8woc 神，black_trees 神还没到，但是已经开始排队了，于是只能站过去。

排队的时候前面插进来一个 cdqz 高一的神，可惜不认识。smallbasic 后面站着 cdqz 接下来两届的女队和未来的女队！我直接也开始膜拜。

然后进校门的时候尬住了...因为我没打印核酸报告（这东西不是昨天打包发过去的吗？为啥还要检查，问号），然后手机又关了，只能到一边去弄。于是开始慌了。还好我妈的手机山也能看我的核酸记录，于是不用开手机就顺利地进去了。

然后进考场的时候大家都在说高新的机房好豪华...我第一次去的时候也这么觉得，感觉太酷炫了！我还是第一次用比 CCF 评测机快的机子（i7-12700）打比赛。不过有个事情有点尬，就是卡常要多卡一点。昨天去跑分网站下查了下和 i7-8700K 的对比，看起来时间限制要乘以 60%。

进考场找到座位，发现是挨着坐的，空间有点小，东西不能全摆在桌子上。键盘敲起来有点抖，检查了下发现是两边的小支架只支起来一边...询问把它弄成这样的人的心理状态.jpg

然后就是喜闻乐见的那一句：

考试期间原则上不允许上厕所！

我直接。已经在想怎么向学会举报了，NOIP2021 和联合省选憋了两个半场，今天直接不准去了，破大防。

然后，宣读考试规则：

...

上厕所需要举手向监考老师示意。

嗯...到底该相信谁呢。

不过我赛前上了厕所，也没喝太多水，问题是不大的。

14:30

考虑 hfu 老师说的，考试要严谨！于是我决定认真通读四道题，就算题面长也弄懂意思。

T1：感觉有点难。不过 n \leq 2500，看起来也不是不能做？

T2：矩阵？要二维线段树查询吗？哦是 A,B 两个序列啊...猜一波每个人的选择都很极端，要么最大要么最小。

T3：这问的是啥？任意时刻图是否是若干个环？

T4：这不是直接树剖？啊，k 是什么玩意？哦 k \leq 3 啊，那考虑线段树维护 DP 吗？哦不对...好像最优方案可以走出当前链...感觉也不能做。

正在我考虑要怎样度过这不能上厕所的四小时的时候，ngg 直接举手：老师，我要上厕所！

15:00

想了下 T1。因为复杂度支持 O(n^2) 乘一点小东西，于是首先考虑枚举。想了下，枚举 AD 困难，AB 同样困难。于是最后把目光定在了 BC 身上。

最后得到了一个看上去能做的做法：预处理出新图，新图中两点有边当且仅当原图中距离 \leq k+1。从 1 出发开始做 BFS，对于每个点 x 维护集合 S_x，其中 v \in S_x 当且仅当从新图中存在 1 \to v \to x 这一条长度为 2 的路径。

考虑枚举 B 和 C，并从 S_B,S_C 中挑出点权最大的两个点，和当前答案取 max，最后得到的就是答案。

这就是全部做法了。写完之后发现有很多小问题：需要判断新图中是否存在 B 到 C 的边，即原图距离是否 \leq k+1。

同时，如果 S_B 中点权最大的点是 C，那只能选择次大的点；此时，另一个问题也同样暴露：S_B 中如果不存在次大的点，那就不存在一种合法的路径。同样的问题在 S_C 侧也存在。

改完了这个问题，就顺利通过了大样例。但是细心的你会发现，大样例不但 n,m 很小，点权也同样小。因此，我花了 10min 写了对拍。

15:20

在运行对拍之后，发现一些小问题：

设 b,c 分别表示 S_B,S_c 中第一个可用的点，如果 b=c，那么还需要在 S_B 或 S_c 中选择一个新的点，这又需要在 S_B 和 S_C 中继续枚举。这个过程中，也可能出现找不到合法的点的情况，仍然需要判断。

加上这个判断之后，顺利通过了 1000 组数据。接下来要做的事情就是检查极限数据的运行效率。

然后...RE 了。检查发现，读入时数组越界，进一步定位到读入边时端点不满足 u\leq n？？？？检查 gen，发现我第二行输出了 n 个而非 n-1 个边权...

重新运行对拍，顺利通过了 500 组数据。

进行静态查错。突然发现，我判断 b=c 时写的东西是错的！而且有访问越界的风险！！！

花了 10 分钟重构了这一部分。重构完代码看着清晰了很多，居然比之前短一点。稍微改了改过了对拍，过了大样例，然后挂了 5000 组对拍，去看 T2。

15:50

T2 有正有负有 0，不难想到分类讨论。钦定 A 选正数，那么 B 的策略一定是优先选大负数，其次选 0，最后选小正数；如果 A 选 0，那么答案一定是 0；如果 A 选负数，那么 B 的策略和刚才相反。

那么如果 A 选正数，怎样确定它的大小呢？仔细一想，似乎只会选到最大值或最小值。选负数同理。于是对于每种情况取 max 即可。

于是可以用 ST 表做到 O(\log n) - O(1)。但想了想，这个东西较为难写。用线段树不影响复杂度，合并的部分也简单了许多。把线段树封装成 sturct，这样两个序列可以共用，不用写两份代码。

稍微改了改，过了大样例。仔细阅读大样例，发现强度不低，几乎可以省掉对拍和极限数据检查。

将前两道题扔到虚拟机里编译并跑了一遍。我可不想在冲 T3 T4 的时候突然被告知 T1 T2 CE 了或者跑不动了。

诶，T2 怎么跑了两秒多？我不会做法假了吧...哦没事了。好像没开 -O2。看来记忆有误，noi linux 2.0 是 -std=c++14，但是并没有默认 O2。

16:40

确保 T1 T2 没有问题。举手申请上了个厕所。

上厕所的时候碰到了 iee。但是不敢说话，怕被认为是作弊。

洗了下脸，回考场的路上活动了下像是新安装上的四肢。感觉舒服了一点，就是有点小困了。

回去再读了下 T3。看了下样例，好像之前想的有问题，并不是一定要是环。仔细思考了下，两个条件可以被描述为：点出度为 1，并且一定能走到某个环里。诶这不是基环内向树吗？

一细想，每个点出度为 1 那一定是基环内向树森林了，于是第二个限制直接没用了！现在考虑维护操作，是不是就每个点出度 +1,-1，以及设为 0 和某个定值？那我不是赢麻了？

说写就写。写了大概 30 行才想起来，操作 2 和 4 不是设为 0 和定值，而是对于一堆点 +1 和 -1，因为操作的是一个点的入边而非出边...

可惜啊...

可惜啊...

啊这不是暴力有 60？我直接继续赢麻了。用 set 维护边是否被删掉，直接做就行。

再看 T4。k=1 秒了，n \leq 200 好像能暴力最短路。数了下能过 9 个点，有 45 分的高分。这样估分就有 305？感觉很高了。

写了下顺利过了所有大样例。

18:00

测了下所有程序，确保不会暴毙。

然后想了下 T3 怎么做，感觉可以根号分治，然后不知道怎么分治，就没做了。

18:30

考完了。问了下 XK，说有 300，iee 也有 200 好几十，感觉大家都挺厉害的。

去找 hfu 老师，hfu 说我还不错。

然后和 XK 一起吃了个饭，瞎吹了几句，就回家了。

23:50

测完了四道题。

T1 没白拍一个半小时，没挂分。

T3 小挂 10 分。原因是，当 4 操作不存在时，每次做 2 操作都会遍历整个边集，而不考虑整个边集是否已经被操作过。于是，对于菊花图，每次操作复杂度高达 O(n)，n,m,q 同阶时，整个程序退化为 O(n^2)，导致无法通过测试点 11\sim 12。

于是民间测试得分：100+100+50+36=286。

不过有初二的神仙 320，感觉非常厉害！记得上次和他一起联考好像全场就他切了 T3，当时就非常印象深刻。感觉再练一年，甚至明年就有希望进 E 队。

感觉大家都好厉害啊。崇拜。

总的来讲，今天算是发挥得最正常的一次。去年 NOIP 算是爆种了，其它时候都一般般...能正常打比赛真不容易啊，呜呜。