CSP2022 & NOIP2022 游记

退役了。

CSP-S

赛前几周做了几套模拟赛。一开始都是一百来分甚至几十分，后来慢慢地找到了状态，基本都能上两百了。

但 DYH 的模拟赛不给样例解释是真的坑啊。。。

比赛当天有点紧张，在车上没睡着。

找到座位后罚坐了十分钟，然后监考老师贴了解压密码—— $Belief2022$ 。然而我不小心把 $B$ 打成了 $b$ ，结果解压成功了。后来发现好多人都没解压出来，原因是 $b$ 确实是小写。。。

开始看 T1 。仍然有点紧张，读完一行就把上一行忘掉了。被迫停顿了一下，然后继续看，发现有点难度，看来今年要爆零了。

往下翻，一看数据范围笑了——这不是可以 $n$ 遍 Bfs 吗？估计就是先预处理一个数组然后再怎么拼一下就好了。结果想了十分钟只想到一个 $O(n^3)$ 的做法（事实上还是假的）。想到先浏览一遍题目的原则，就去看 T2 了。

T2 一眼像个博弈论，而且好像 $n\times m$ 太大，矩阵压根建不出来。一看还有个区间询问，估计是个神仙博弈论 + 线段树题，溜了溜了。

T3 是个语文题，不想看，滚了。

T4 一看是棵树，仔细一看 $k\leq 3$ ，发现好像可以树上倍增。但由于赛前不开 T4 的 flag，先滚了。

这下糟了，三个神仙题，只有第一题像个签到题，还不会做，咋办捏？

只得开码 T1 的 $70$ 分。结果码着码着发现还得 $O(n^4)$ ，就停下来继续想。想了 $15$ 分钟无果，只能先跳咯。

过去半个多小时了一分没拿到捏，看来只能爆零了捏。

结果仔细看了看 T2 发现就是个区间最值 + 分类讨论题。但由于心态不稳，状态不佳，怕分类讨论挂掉，只好放弃思考，直接上 $8$ 个 st表——正数最大，正数最小，负数最大，负数最小。然后再开两个数组存个 $0$ 的情况。询问的时候直接枚举 $25$ 种情况。时间复杂度 $O(n\log n + q\times 25)$ 。算了一发空间，稳得一批。

差不多复制粘贴了四十分钟，然后测一波小样例，发现挂了。仔细一看，发现枚举答案的时候最大最小写反了。改了改，然后过了大样例。

这下心里稍微有点底了。依然不想读又臭又长的 T3 ，于是滚回去做 T1 。

想了一会儿仍然不会。后来看一眼数据范围，发现 $k\leq 100$ ，就开始幻想复杂度关于 $k$ 的算法。但 $k$ 当然是 Bfs 完就没有任何作用的。故又想了一会儿后放弃了这个想法。

再想了一会儿，脑袋一拍发现其实只要枚举每个节点能到达的节点，并且要求这个节点能到达 $1$ 号节点，然后维护分数的前三大节点，最后统计答案时枚举 B 和 C 就好了。时间复杂度 $O(n\times m + n^2\times 9)$ ，很稳。

码了一会儿调了一会儿，在两小时左右通过了大样例。

这个时候不再慌张了，开始慢慢研究 T3 。发现 $O(n\times q)$ 可以每次 Dfs 判断，一看数据范围有四十分。想想正解应该是个线段树。但想了一会儿没想出快速判断的办法。有点不甘心，于是没码暴力，先滚去 T4 了。

果断打破了 flag ，开始码倍增。码了十来分钟发现实在太难了，直接 Ctrl^A + Backspace ，然后光速码了个 $k=1$ 的部分分。

看了看数据范围，发现有很多“随机数据”。想想直接把链扯出来暴力 dp 就完了。开码。码完测个小样例，发现挂了。百思不得其解，差不多搞了二十来分钟后才发现原来这玩意是可以跳出链的！心想凉凉，只有 $k=1$ 的分了。

想要借此机会看看大数据的强度，就运行了一下 $k=2$ 的大数据， fc 一波，竟然过了！心想这数据强度也太低了吧（实际上是想假了）。

只剩一个小时不到了，于是滚去 T3 码了个暴力。大概还剩半个小时的时候过了样例。看了看输出文件，发现全是 NO ！这数据强度有屁用！（然而赛后发现其实还是有几个 YES 的，只是没找到。）还想狗一波大样例，结果直接未响应了。。。

回来码 T4 但是我脑袋依然不清醒，完全没有意识到 $k=2$ 是跳不出去的，于是把 $k=3$ 直接拆了，开始码了一长串的东西，尝试去写跳出去的情况。差不多最后几分钟码完，测了个大样例发现还是过了。

检查了一遍文件，然后出考场了。

出考场后发现 zzh T1 挂了 😦 ，最后发现是变量重名 + 队列写成了栈（即广搜变深搜） 😦😦😦 。 ym T4 没看出能跳出链，没调出来 😦 。 zhy 看出了 T3 是个内向基环森林，还发现了只要所有点出度为 1 即可 orzorz ，但 T1 写了个弗洛伊德挂了十五分。

后来发现我纯脑瘫， $k=2$ 压根跳不出去，痛失 $32$ 分。

预计 $100 + 100 + 40 + 44 = 284$ ，民间数据最后一题多水了 $4$ 分。 CCF 数据一分没挂，还是 $284$ 。

但为什么“不可以，总司令”有 $45$ 分啊！而且听说出度和为 $n$ 再判断就可以 AC 了。什么水数据啊。但是正解的 Sum Hash 确实牛。没学过的新算法，想不出来不怪我。

T1 数据也太水了吧，不开 long long 都不见祖宗。

T4 确实是个倍增，但不是我能写的。

总体来说还算正常发挥。

NOIP

最后一场比赛了。但心情很平静。

赛前看了一波点双边双，结果给压中了（虽然边双本生也会写）。

密码不正确。。。 PDF 打不开。。。后面发现用谷歌浏览器才行，这是为什么呢？

这次有点勇，直接顺序开题，并打算搞掉前两题再啃面包。

T1 长得像个送分题。推了推式子，发现可以构造 $f,g$ 两个函数分别表示每个点往右最多几个点以及往下最多几个点。对于 $C$ 的情况直接枚举左上角，尺取法算一下就好了。对于 $F$ 的情况要稍微复杂一些，推出式子后发现脑袋不大清醒，于是先滚去 T2 。

结果 T2 是个构、造、题！一巴掌给我打了回来。

先码了个 $C$ 的情况。码完后测了样例，发现最后一个样例凑了个恶臭数字。。。为毛大样例这么小捏？难道就为了凑数？

想了想 $F$ 的情况，发现只要尺取的时候区间加就好了，维护一个 $f$ 的前缀和即可。四十分钟的时候过了样例，跑路。

去看 T2 ，觉得不简单，先滚蛋了。

看 T3 ，一眼看出边双，然后发现缩点完之后是一棵树，直接树形 dp 就可以了。在草稿纸上画了画各种情况之后就开码了。边双十分流畅，一遍码出。很快码完了，光速过了两个小样例，然后第三个样例挂了。干瞪眼了十分钟，屁都没查出来。于是打算写个暴力对拍。写了一会发现暴力比正解还长，还假掉了，果断 Ctrl^A + Backspace ，手捏了个小数据，模拟了一下感觉没问题。

很快就 10:30 了，心里很慌，感觉这次凉凉了。 T3 样例之间差距太大了，根本调不出来， T2 又是个神仙构造题，只好跑路去看 T4 了。

不，啃个面包先。

然而 T4 是个牛逼数据结构。感觉线段树不可做，考虑莫队。结果发现加点要 $O(n)$ 。发现有随机数据的性质，故可以将加点优化成 $O(\log n)$ ，总复杂度 $O(n\sqrt n\log n)$ ，但莫队常数小应该能过。

然而突然我意识到压根删不了点。想了想分块预处理，发现行不通。最后浪费了半个小时，还是写了个 $O(n^2)$ 的区间 dp 跑路了（然而实际上是可以删点的，又想假了）。

这时我意识到了我所有筹码都压在了 T3 上，于是开始死磕。又干瞪眼了十几分钟，我突然发现我的转移没有考虑子树外的军营。修修补补了一会儿，一测，还是没过。然后又花了十几分钟，代码写了删，删了写，一直不知道在干什么。

后来我突然意识到还有儿子之间互相到达需要考虑。然后又搞了半天转移方程，还是过不了。

还剩一个半小时不到（但我以为只剩一个小时不到）的时候，我突然发现可以对于每个子树单独算子树外没有军营时的贡献。差不多于剩一个小时的时候写完，自信 fc 过了大样例。

然后我的分数就定格了我开始在 T2 和 T4 之间反复横跳，最后在多次研究 T4 无果后，正式开始想 T2 。发现 $k=n\times 2-2$ 时可以空出一个栈来，于是先写了这 $15$ 分。测了测样例，发现过了。然后就开始乱搞，每次找最不容易消掉的地方放卡牌。最后十五分钟码完了，手模了一下发现好像过了第二个样例的第一个小样例。

然并卵，InfOJ 上爆零了捏。

草，多测没清空。

清空多测后 Luogu 35 ， InfOJ 30 。

zzh 看错题了:((((((( ，他以为 T3 可以进攻无数条边 ::😦(( 。

ym T3 没调出来 :< 。

有人说 T4 是板板题？？？orzorz。

InfOJ 上民间数据 $100 + 0 + 100 + 20 = 220$ 。

希望别挂分，希望省一线低一点。

再见啦， OI 。

晚上睡觉的时候想了一下，发现又脑瘫了，莫队的删除和加点一模一样 😦 。

好吧，也只能这样了。

出分了，一分没动。

这次数据有点毒啊，把随机给卡掉了 😦(((((((((((((((((((((

仔细想想，有意思的是，学了两年线段树，考场上没有写过半棵（两年都是压轴。。。）。