联合省选2023 游记

· · 个人记录

前言

考前完全不紧张。

虽然 \text{NOIP} 挂了 130 分，但还是苟进了校线，按平时模拟赛算也都能进。

在考完 \text{NOIP} 后认真思考过自己的 \text{OI} 生涯，发现除了升学以外基本什么都得到了，那么即使退役也没什么遗憾了。

可是做过很多次 \text{NOI} 寄了的梦，十分真实。我的感受并不是对于前途的担忧，而更多的是空虚。

一开始，我会被这样的梦弄得很紧张。

但我之后又开始想，即使我进了集训队，也总有一天会退役。无论是什么时候退役，这种空虚的感觉是不会改变的。所以对于我来说，省选退役、\text{NOI} 退役、\text{CTT} 退役、\text{CTS} 退役，甚至是遥不可及的 \text{IOI} 退役本质上没有任何区别。这样一想，我心态就变得很好。

Day0

再次来到合肥考试。虽然上次来还是在初三，但是看考场时还是感觉非常熟悉，仿佛刚刚才来。想起了两年前的省选，当时一起参加的人除了我都已经全部退役了，不禁感慨物是人非。

晚上还是不紧张，睡觉之前听了会歌，结果睡觉时满脑子都回荡着那个旋律，到很迟才睡着，不过好在睡着了。

Day1

看题，感觉是一道数据结构签到，一道图论找性质计数，一道大数据结构。样例给的很多，我很喜欢。

先想着把第一题写了。一开始胡了个线段树做法，准备写之前决定花几分钟想想有没有更简单的做法，然后发现直接差分就行了。8:50 就解决了这题，感觉大样例应该有点强度，就不管了。

然后花了十几分钟读完 \text{T2} 和 \text{T3} 的题面，想着先给 \text{T3} 打个暴力，重点做 \text{T2}。想了一会儿，才会 \text{T3} 堆合并的 O(nq \log^2 n) 做法。赶快写了，写完大概 9:20，一下过了将近 10 个样例，非常舒服！

还有很多很多时间，想着把 \text{T2} 做出来就稳了。

这个每个连通块只有一个向外连的点是个很强的性质，便往上面去想。想了不少时间，才发现在树上割掉的所有边构成一个连通块。

拓展到图的 \text{dfs} 树上也是这样，但返祖边感觉很麻烦。又觉得是一个边双要么全割要么全留，但很快就把自己 \text{hack} 了。

又想了一下，发现可以认为 \text{dfs} 树上一条返祖边构成的环，要么全割，要么全留。有这些性质就可以 \text{dp} 了。

不是很好写，但我还是写完了。外层枚举是 O(n) 的，内层 \text{dp} 是 O(n^2) 的，但最大的样例几秒就跑出来了。

感觉不是很稳，就写了个指数级暴力开始拍。

加了一些剪枝，大样例能秒出，但是一条链还是寄了。又发现 \frac{n}{i} < n \bmod i 时，以 i 为连通块大小是没用的。加上这个优化，时间复杂度就变成了 O(n^{2.5})，能拿 65 分。

加完剪枝，继续挂上拍，大概 11:00，觉得优势在我。

先去看 \text{T3} 有没有特殊性质能拿到。发现除了 \text{C} 什么都不会，还在思考过程中将问题转换成了完全不可做的东西，导致完全失去了想出正解的机会。

已经 $11:30$ 了，觉得也想不出来什么东西，不如再拼点暴力。$\text{T2}$ 中 $k=0$ 的 $10$ 分是不难做的，但我对着拍写了很久才过，写完已经 $12:00$ 了。 然后我在想要不要写 $\text{T3}$ 的 $\text{C}$ 性质，想到去年差一分就进了省队，还是决定把写了。写得飞快，在 $12:25$ 就过了样例。感觉很稳就没拍了。 按照题面的编译指令测了下三道题，没什么问题。然后肉眼检查 $\text{T1}$，也没什么问题，就下考了。 出考场发现 $\text{Kostlin}$ 把 $\text{T3}$ 切了，还说 $\text{T3}$ 是简单题，很震撼。感觉我校今天考得都不错，所以大家都不挂分的话我只有大概 $40$ 省选分的优势。 回宾馆问了一圈，发现 $100+75+54$ 不是很高，很多人切了 $\text{T2}$ 或者 $\text{T3}$，$\text{Linshey}$ 直接狂暴阿克！ 疯狂对拍，发现没挂，民间数据测出来也没挂分。那就比较稳，有 $40$ 分的优势。 晚上突然有点慌，怕明天翻车。想了一下考试策略，明天的 $\text{T1}$ 是关键，只要能写出来，后两题拼点暴力就比较稳。希望明天能有一道 $\text{AGC-style}$ 的计数题放在前两题的位置上，这样就稳了。 晚上比昨天睡得好。 --- ### Day2 开题，先没有通览全题，只开了 $\text{T1}$。 发现所谓的“关键题”非常难写，但觉得必须把冲出来。想清楚了就开始写，中途写了一个输出状态的东西，把状态调对后就直接过了所有样例，此时只有 $9:40$，感觉很稳。 测一下极限数据，发现跑了 $\text{7s}$。认为两个红棋不区分，状态数除以二，跑了 $\text{3.5s}$。把 $\text{vector}$ 换成邻接表，就只跑 $\text{1.5s}$ 了。感觉评测机比本地快，而且数据不可能很满，就跑路了。这时大概是 $9:55$。 开 $\text{T2}$，一眼建图，然后分树和基环树讨论。基环树可以线性，树应该不难 $O(n^2)$。先写了把树和基环树分开处理，每部分直接暴力枚举的东西，感觉写了很久。 然后写基环树，对着拍调，一直不对，非常自闭。到 $10:45$ 时还是没调出来，心态有点崩。在 $11:20$ 终于调对。 然后写树，先确认问题转换的对不对。写了个暴力，一直不对，以为假了，其实是变量名打错，到 $11:45$ 才调对。 这时 $\text{T2}$ 只有最暴力的 $20$ 分，心态不太健康。 赶快改成 $O(n^2)$ 的树上背包合并，到 $12:10$ 写完。然后发现加几句话就能把特殊性质 $\text{ABC}$ 都过掉，加了之后测了几组极限数据，再测样例时发现 $\text{WA}$ 了。然后发现有个东西加错了，很快就改对了。这时是 $12:30$。 时间不早了，赶快冲了个 $\text{T3}$ 的 $10$ 分暴力就去检查文件了。 出考场发现我校其它同学都没发挥好，我是不是翻到队长了？那有点寄啊。 发现外校老哥 $\text{jwz}$ 有点猛，拿到一个 $\text{A}$ 类名额。那我校可能要退役一个了，惨。 之后测民间数据，发现没有挂分，全国排名大概在 $30$ 左右，证明了只要稳健就能进集训队。希望 $\text{NOI}$ 时能稳健一点。