又一年

其实也就半年而已，毕竟我 CTS2024 的游记还是写了的。

在 noi2023 之后的某个周末，我终于意识到一直这样混日子下去也确实不行，于是我决定把目标还是定为冲国家队，然后如果没进就放下这件事，去读预科。

实际上我后来做的事也不算和我一开始的打算完全背道而驰：首先我当然没进国家队，但考虑到我在 CTT/CTS 的成绩好像还挺好的，我实在是不愿意就此放弃，但继续一门心思地冲国家队我觉得再训也很痛苦。于是我拖延症犯了，决定把问题留给后人的智慧：读预科也不是不能训，到时候根据具体情况看主要把精力放在哪里。

CTS2024 一个月后就是联合省选。我想了想，发现实际上我 省选/NOI/CTT+CTS 任意一场爆了最后的结果都是一样的：反正就是进了集训队然后结束了。所以倒也不怎么紧张，反正如果真的没进省队，也只能说我本就不可能赢到最后。

因为省选其实已经是将近五个月前的往事了，所以关于我当时做了什么，我也只能说我 “大概” 是这样做了。

Day1 我大概立刻发现 A 只需要进行一些分类讨论就可以解决，要注意细节。B 我好像画了一会也明白怎么做了，但一开始想的做法好像复杂度没有保证，后来应该是修了一会修好了。于是我就把 AB 写了，并给 A 写了个对拍，应该是花了 2.5h。我当时恐怕对自己的水平还是抱有充足的自信，于是我觉得还要冲击更高的分数然后开始想 C，但花了一点之间会了 32 分做法后就毫无进展了。最后我自认为 100+100+32 离场。

然后 Day1 晚上同学告诉我我 B 挂了，云斗上挂成了 24 分高分，Day1 总分 156。我大受震撼……了吗？我当时的想法应该是虽然任何一场爆了然后结束的方式的结果都一样，但这样因为省选一个题挂完了结束还是有点荒诞。不过我想了下 2023 年省选我好像从写的分往下挂 100 分也还是能进省队，那过了一年我总还是不能变菜了（为什么不能呢？），明天正常打能进。

顺带一提，我 B 存在某个时刻写的代码是正确的，但我后来感觉我代码逻辑写得太混乱了于是我稍微改了下，但改之前和改之后的逻辑并不等价，不过共同点是能过最大的样例。然后我最后交上去的代码好像在样例一就是不对的，只能说很幽默。

Day2 我一开始看 A 应该并没有什么头绪，不过我换到 B 的时候发现这好像是我最擅长的集合幂级数题！我立刻得到了一个枚举 Bell 数的做法，写了一下发现能过所有样例，优化只要做 DAG 容斥并对一元插值即可，我在 50min 通过了这题大样例。回到 A，我还是很没有头绪，硬做得到了一些复杂度很高（不过确实是 poly 的）也很难写的做法。又经过了 1h 艰难的思考之后我终于发现记录很少的一些信息实际上就可以让转移封闭，不过代码确实很好写。我应该又是在 2.5h 通过了 AB。不过考虑到昨天的教训，我知道 OI 比赛其实还是要对拍的，于是我给 A 写了个 O(2^{2^n}) 的逆天复杂度做法和我的代码对拍，把 B 的 Bell 数代码和我准备提交的代码对拍，但没有拍出任何问题。我还检查了一些其他的问题，于是时间走到了 3h。C 看上去完全莫名其妙，即使对于没有部分分的一个非常简单的情况我也分析了很久才得到结论，而且当我尝试对这个情况拓展时我发现我完全不会。在只剩 35min 时我意识到这样想下去也不会有什么结果了，于是我开始乱猜结论，在只剩 15min 时猜中了性质 B 的结论，并发现这个性质的优化只要写个线段树而已。Day2 的估分是 100+100+24。

然后 Day2 下午，我就去北京了，路上得知了其他同学的情况。

省选最后真实得分是 100+20+32+100+100+24=376，这也是我的最后一次省选。我一共参加了 2021/2023/2024 三场省选，得分分别是 376,377,376，不得不说很有趣。

我最后也应该以和去年一样以第 8 名进入了省队（我确信我去年是第 8 名，但写这篇文档时我没法上网，我不确定我今年是不是第 8 名）。这次省选高二没有人退役，shz 和 5ab 都进了，学弟 wsy 和 xsc 也进了，是近几年 hez 进省队最多的一年。当然现在我已经知道，也是近几年金牌最少的一年。

到北京后我开始上预科的课，我只选了 程序设计实习、代数结构与组合数学、AI 基础 三门课，所以倒也确实挺闲的，经常可以在 1318 训一整天算法竞赛。不过到了北京没人管我了，训练强度当然也算不上大，毕竟我感觉有点累了就摆了不训了，也很难说这样训了四个月到底我的水平提升了多少。

在 1318 的时候也经常有学长建议我应该早点学点英语，如果上大一时英语很差后续会遇到很多麻烦。不过我到现在也还是没学：我理性上能理解这确实是对的；但感性上，恐怕我还是固执地认为，这不是最重要的事。

我做出要去读预科的打算，其实应该是因为我对我越发混乱的生活感到恐惧，我认为我需要找到一个支点。算法竞赛可以是一个很好的支点，但不能一直是。但我读了半年预科，我也还是没能找到更好的支点，这某种程度上倒也是一种无功而返。

那回到算法竞赛，如何呢？

我 6.25 左右就考完期末考从北京回来了，回到机房训了两周，然后考了下学考（复习了足足两天，每天坚持一半时间摸鱼）。

7.7 我到达了重庆，联考集团在 noi 前安排了一周的集训。周一是 hez 的题，然后是我准备的于是我没打；周二是 bdfs 的题，我做了一整场 A 得到了一些进展但没有对应的部分分，于是获得了暴力分；周三是 hsefz 的题，其实也四舍五入是我准备的，不过我感觉这场再不打的话就没有练手的机会了于是我打了一下，但在开场前就大致知道三个题怎么做的情况下，我 FST 掉了 A 和 B 获得了 100 分高分；周四我忘了是哪个学校的场了，三个原题我终于 AK 了一次；周五我又对着 T2 写了 1.5h 假做法，最后 T3 被卡常了。

五场联考下来我发现好像我也不是总是能取得比较好的成绩，我真的还挺有水平的吗？不过好日子还在后头呢。

周六周日是 UNR，UNR Day1 我比较顺利地通过了 AB 的 pretest，在 C 我想了一个极其奇怪的交替分治的做法并写了 2h，最后虽然调对了但只能跑过暴力的那档分。比赛结束后我发现我 C 的复杂度分析是错误的，实际上就是和暴力一样的复杂度。然后我 B 把 occ 对 63 取 \min FST 成 20 分了，UNR Day1 取得了 100+20+6 的好成绩。UNR Day2 在通过 A 的 pretest 后，我认定 C 和 UOJ 的 ”许愿树与圣诞树“ 的做法是类似的，需要用 LCT 所以我很难写完。于是我全力思考交互题 B，但没有进展。最后 100+40+40。

UNR 可以说又一次集成了我比赛时的所有问题：经常不加验证地狂冲一个假做法、不按照部分分做题、不对拍觉得不会挂、太早对题目下论断。最终我取得了 UNR 铜牌的好成绩，不过我倒也没有太难受，和省选一样，在任何一场比赛失败的分支最终都导向一样的终点。

顺带一提，hez 在今年 UNR 的战绩是两银三铜。

不过如果可以不失败得那么早的话，我还是乐意再做一些挣扎的。于是我最终将目标定为求稳一定要进队，尽量不要写假做法。

笔试不必再提，只能说下发去年选手的答案确实挺幽默。

Day1，我一开始完全不会 A 的任何做法，只观察到其实答案是具有单调性的。又分析了一下问题之后发现实际上等价于判断所有颜色出现位置的集合构成的可重集是否相同，那么这应该哈希就行。B 竟然是交互题，不过直接像线段树一样一层一层取最小值就可以做到 t=20，恰好 n-1 次比较。因为比较次数相对更松一些，所以把线段树相邻层适当合并应该就能做到更小的 t。C 字典序最小当然是要转逐位确定，我发现其实 u \to v 路径上与路径方向一致的边的数量可以用 1 \to v 的下行边数减去 1 \to u 的下行边数加上 u \to \operatorname{LCA}(u,v) 的边数刻画，那么这可以进行差分约束建模，只需要判负环就可以知道是否有解，这样需要判 n 轮，每轮要对 n 个点 n+m 条边的图判负环所以是三方的。我在 40min 开始写代码，在 1.5h 获得了 100+91+24 的分数。B 91 分感觉也不太用再做了，但 C 怎么优化呢？

这就是折磨的开始了，我先想了 30min 如何优化判负环，毫无进展。我意识到我可能 “太早对题目下论断” 了，于是我转换了一下思路，发现长度为 1 的路径会直接确定掉一条边，接下来这条边两边的点可以合并起来从而递归到子问题，而所有路径长度至少为 2 时有交替定向方案是显然有解的，这样就得到了另一种判定有无解的方式。但这有什么用？朴素的实现仍然是平方的，还要做 n 轮判定，这仍然是一个三次方的做法。如果判定成功的话，被缩掉的边可以被势能控制，但如果失败怎么办？是要想办法能在真的向下递归之前就知道这条边能否以某种方式定向吗？这看上去就很复杂。

我觉得 Day1C 应该还挺难的，应该会像去年一样是部分分容易得而通过较为困难的题目，于是我将目标转为获得 64 分，但三方做法恐怕还是不够的。我试着对新的判断方法的性质进行分析从而取得优化，在又一番折磨后我终于得到了从一个所有路径长 \ge 2 的局面出发，确定一条边看不断向下递归最终会如何停止的 O(m \log n) 做法，于是整体是 O(nm \log n) 的，但这个做法充满细节。

写到离比赛结束还剩 1h 时，我终于调对了这个做法，这个做法可以直接通过 48 分。我此时才开始看特殊性质，A 好像就是我之前想的交替定向啊？B 性质则好像是最小字典序 2-SAT，不过我之前确实对此有一些研究。又写了 40min 我拼到了 64 分。因为目标是求稳，我检查了三个题，发现 A 我的哈希实际上可以被精心构造的数据卡掉，于是我加了另一种哈希方式做双哈希，现在应该没有问题了。100+91+64。

出场得知 shz AK 了？原来 C 其实从一个路径长 \ge 2 的局面出发，任意一条边给任意一个定向都一定有解，证明就是考虑交替染色的构造，所以判定永远是成功的，这部分复杂度被势能控制。所以 C 的 O(nm) 做法实际上非常好写，我想了一下进一步的优化，也确实不难。我感觉自己有点搞笑，但 255 应该也不至于低于队线，既然我一开始的目标就是求稳，也不能算错。

Day2，A 给我的第一感觉是数论王朝复辟？但事实上我并列不出一个关于答案的公式。要对一个分数做判定会是一个类辗转相除的形式，于是我尝试递归到子问题，但试了几下也还是很不合理。接着我尝试找规律，但除了一些非常浅显且完全不充分的条件我什么都看不出来。不过我仍然只是感觉有些幽默，最后我打开最后一个样例，发现这个 1e6 级别的样例的输出是 1e8 级别的，所以一个 O(ans) 的做法就可以通过 85 分。而对于一个 O(ans) 的做法，我只能说直接做就好了。此时已经过去了 80min，不过我还是只感到很幽默。B 看上去是一个比较正常的优化 DP 题，我很快写了一个 O(n^3) 的做法确认了转化的正确性。凭借经验，我觉得做树分治会比较好，因为这题是后代的 DP 值自祖先转移而来，应该做有根树点分治。我推了几下似乎得到了一个做法，看上去还比较合理，于是我开始写。

赛场上的时间总是过的很快，在经过 3h 的时候，对着对拍出来的一个挂的数据，我突然意识到我的做法是假的：树分治会把问题切成几个子问题，但对于分治重心上方的子问题，其内部的转移的权值会受分治重心下方的点的影响，这并没有真正地递归到子问题。

到头来，我还是在 noi 写了假做法。此时到底有哪些选择呢？可以把 B 扔了去全力做 C，也可以两题都拼点暴力，或者继续做 B。我看了一下 C 感觉是非常需要性质分析的题目，并且我还丝毫没有思考过这题。考虑到 B 之前的做法可能修一修还有救，而且 C 的暴力分看上去不多，我决定继续做 B。冷静下来，我发现把 B 我之前点分治做法的最后一部分拿出来并做一些修改，应该就可以解决原问题。又稍微确认了一下正确性，我开始全力冲这题，在只剩 40min 时通过了 pretest。我又花了 10min 写完了 C 的 A 性质和 B 性质的平方，BC 性质应该就是之前我做过的一个原题，但我最后也没有调出来。85+100+20。

出场发现好像又是一个比较平庸的得分，不过或许也够进队了。shz 今天求稳了，没有过 B 不过 Day1 很高所以最后还是比我高 20 分；5ab Day1 爆了今天和我差不多，xsc 则是 Day1 和我差不多 Day2 爆了，都是 ~520；wsy 两天都不是很好，没到 500 分感觉是不太行了。D 类选手 zjy 两天加起来和 shz 差不多高，zsj Day1 太低了，Day2 得分也是 ~200。

此时我们还认为今年能进四个集训队，但随着消息开始流通，今年的队线最终定格在了 538，所以是两金三银。这意味着 5ab 退役了，下一届六个人并没有人能提前进集训队，因而明年必然有人进不了省队。5ab 文化课很厉害，希望能明年在 PKU 和他重逢，会赢的！

校外也有很多选手爆冷出局了。今年确实是一场没有容错的比赛，D1B 和 D2A 两道题完全没有区分度或是反向区分，要进集训队不能在 D1C 和 D2B 的任何一题犯错（均不能得低分，如果两题都是中档分的话总分会非常极限）。为其他没有进集训队的选手祝福！

那我自己，又该何去何从呢？又学了一年 noi 排名顺利翻倍了，CTT/CTS rank6 似乎也不能成为下一年就一定能进国家队的保证。OI 就像是抽卡游戏，我一开始的几抽就已经抽到很好的牌了，真的还要押上剩下的筹码抽到最后吗？

总之，我仍然还是什么都不知道。