BJOI 2026 游记 | 一切都是最好的安排

· · 生活·游记

多次在模拟赛中获得前三，感觉状态很不错。

最后一周了，RP++！

3.7

我的脑回路确实和别人不太一样。

WC T2 > T3，省选 Day 1 T2 < T3。

这就是命运吗？

还好 NOIP 有一定的优势，明天正常打应该问题不大，加油！

The last chance. Believe in yourself——you can do it!

以上为 3.7 Day 1 当天所写。

以下为 3.12 出分后所写。

还是记录一下比赛过程吧，毕竟是倒数第三次参加省选了。

凌晨三点醒了一次上了个厕所，后来感觉过了好久才睡着。

早上起来精神状态不错，吃了早餐就前往首师附。

一开始坐错位置了，准备开电脑的时候才发现不对，赶紧往后挪了一格。

开场前 10min 就可以看题了，把三道题通读了一遍，感觉 T1 是简单题，T2 至少有 45/60 分可以拼，T3 应该分也不少。

开场先写板子，然后简单思考发现 T1 必须得知道每个点的重链长度为任意值的概率，因此容易设计出 dp。写了个前后缀合并，写到一半发现复杂度不对改成了多项式除法，1h 不到过了。

接着思考 T2，思考了一段时间感觉会了 60，因为不太难写所以决定先看看 T3。

T3 是个比较需要观察力的题，首先指数级暴力和 m=1 是容易的，然后可以发现关于模 3 的一些性质，m=2 就是一个前缀+后缀拼一个中间的东西，写完之后写了个拍发现没问题。

感觉 T2 60 分差不多够了，这个题还有很多可以拼的分，于是继续思考特殊性质 B，想了一段时间之后想到了一个 O(n^2) 的贪心做法，用了比较长的时间调过大样例，然后发现第一层循环只有 0 的时候有用，可以 O(n)（虽然没区别）。

接着思考了一会儿特殊性质 C 没有想到特别好写的做法，强行分讨当然是可以的但只剩一个半小时了，所以我决定先把 T2 60 分写了。

回去仔细想了一下才发现串长不是 O(n) 量级的，而且我的 dp 细节可能也没有分析对，又想了一会儿感觉不是很好补救，就决定先把暴力和 A 性质写了。

写完之后大概还有 50min，我又会了 T2 B 性质，于是直接开写，写了 20min 后发现做法有一些问题，但不是很好修正，我犹豫了一下决定去尝试 T3 C 性质的答案分。

最终当然是没有调出来，100+30+44=174 遗憾离场。

下午没有看 QQ，不过还是在洛谷上看到了不少人通过 T2，但我感觉也没有和队线差多少所以也没有特别大的压力（第二天才知道北京有十多个人获得了 200+），晚上很快就睡着了。

3.8

好像睡了将近 9h 的样子，非常清醒。

到的稍微有点晚，发现电脑进不去网站，吸取昨天 fqd 的教训，直接要求换电脑。

差不多开场前 3min 看到了题，仍然是看了一遍三个题，不过没有细读，隐约觉得在哪里见过 T1（赛后发现是 U 群一月的时候有人问）。

一开始没看见 T1 的次数限制，以为随便写 n\log n 就能过，然后就开始写，发现空格键是跷跷板，要求更换。

换完之后写完代码直接过了样例，但是发现没多少分，又想了一会儿发现二分改成暴力可以得到 2n+\log n 的做法，依然没多少分。

进一步思考，想了好久还是没有什么进展，只发现刚才的那个可以优化成 1.5n+\log n，这个时候已经过了一个小时多了，决定先看看 T2 T3。

T2 看着不太好做，没什么能得的分，考虑到 T3 大概率不可做，于是开始拼 T3 的暴力。

想了一会儿只会 24，写完之后仍然不会更多的分，于是决定思考一下 T2。

思考了 20min 没有什么进展，同时发现坐我左边的人好像很激动，似乎过了 T1 的样子。于是我相信一定是我想复杂了，下定决心尽快过掉 T1。

这个时候大概 11:15 左右，我提交了 T3，并迅速实现了 T1 1.5n+\log n 的做法吗，然后忽然发现好像只需要知道所有前缀和后缀的 mex 就可以确定整个序列，然后就会了正解。

用了十几分钟就写完了，调了一会儿，写了个数据生成器随了忘了多少组 n\le100，然后发现最大询问次数 =101？？？以为是 0 在边界的问题，但仔细看了一下没啥问题，然后发现我的数据生成器写的是 n = rand() % 100 + 2，那没事了，11:59 提交。

最后 1.5h，全力冲刺 T2！！！

容易发现 p\ge\frac{n(n-1) }{2} 的意思是这么多次就可以取到理论最大值，然后推了一下发现跟每个点度数的奇偶性以及 k 的奇偶性有关，试了一下发现有的样例输出比答案大 1,3，然后发现总边数的奇偶性不对的时候需要修改，总之大概用了 25min 获得了 25 分答案分。

我赛时怎么都不会想到如果这个时候比赛结束我将进入省队。

之后开始推构造，容易发现转变成了一个要清空一张图（保证有解）的问题，然后我用了 500\times500 的 int 数组存边。

之后发现可以归纳构造，但时间不太多没想边界（以为归纳到 n<k 图就一定是空的），于是考虑尽可能地让度数接近 k-1 地倍数，写了一个这样的贪心试了一下，发现能过前两个样例和 k=3，别的不太对。

当时以为是写错了，检查了一遍发现可能确实是做法的问题，但是只剩 10min 了所以我赶紧检查了一下，并在出现非法构造/超过次数的时候 return，测了所有大样例发现 34 分没有问题（但没注意到大样例 n=100）。

想了一下暴力发现可以线性基，算了一下好像只能过 n\le8，最后 5min 冲刺了一下，没写完但延时了，最终在 13:40 通过了前两个样例（我知道这可能很弱但我也没时间了）。

最后给构造中的某个量加了一个取 \min 防止操作集合大小不为 k，想着能不能水过一些点，又测了一遍大样例没有问题，结束前 2min 交了。

估分 100+40+24=164，赛后听说 T1 只有蓝但我好像靠 T2 T3 的部分分翻了一些人，处于队线附近。

之后在民间的估分榜上应该是 rk12，不挂就能进 E，但和后面的四五个人分差非常小。

之后听说了 Day 1 T3 B 性质 m=3 要特判，但观察了一下 qoj 数据发现没有所以应该问题不大。

但是后来发现我 T2 最坏情况是 O(n^2k^2) 的，所以可能因为构造 TLE 而丢掉答案分，但我不太记得我赛时代码咋写的了觉得很大概率会很快出现大小不对的构造而 return，而且所有大样例都没有 TLE，所以也没太担心。

3.12

出分了，Day 2 T2 挂 18 分，BJ rk14，和 rk13 差 0.25 标准分（Day 2 2 分）。

由于 hjc（RDFZ 主管竞赛的校长）坚决不同意 pyc 放弃名额，所以我彻底与 E 无缘了 /ll

我该在哪里停留？我问我自己。

观察代码发现 Day2 T2 我最后加的那个取 \min 操作导致本来会产生错误构造的东西集合大小对了但构造仍然不对而进入了死循环，直到 p 次才会 return 掉，但由于我使用的是 int 数组暴力更新，所以 14\sim25 全都 TLE 了。

时隔一年再次被 bitset 迫害。

又发现我的 n\le8 暴力在建线性基的时候循环一进去操作完直接 break 了（本来应该放在 else 里面），这是怎么过前两个样例的？？？

同时我还发现线性基只会插入 n^2 个元素，所以我的暴力复杂度其实是 O(\dfrac{\binom{n}{k}n^4}{w})，数组开大即可通过 n\le18。

破防了，但凡 NOIP T3 暴力调出来 / Day 1 T2 写出 C 性质 / Day 2 T1 做得快一点 / Day 2 T2 提交一个只算答案的 25 分代码 / Day 2 不延时 / Day 2 最后不拼暴力检查，我都进队了。

哎，命运就是这么爱捉弄人呢，按照估的分我挂这么多至少是 rk16 了，但没想到最后竟然是 rk14 而且只差 0.25 分，这不是更让人崩溃吗。。。

归根结底还是自己的水平不够，继续努力吧，相信一切都是最好的安排。

APIO RP++，NOI RP++。