NOI 2026 及集记

· · 生活·游记

前情提要：

Day -12

来到了青岛。

Day -11 \sim -3

dmy 赛前集训。

在五场模拟赛打出了 [7,77,99,22,82] 的排名。random_shuffle 这一块。

中间两天打 UNR。100+220+180，获得了伍佰分。

Day -2

摆烂。

Day -1 / 报道日

报道。获取物资。

吃晚饭。雀。雀。Graphomata。手机。睡觉。

Day 0 / 试机日

开幕式。神秘节目。dzd 高能讲话。/续标识。神必节目。

雀。雀。

试机。尝试写 game。笔试。3min 做完。继续写 game。怎么最后一个点 T 飞了啊。【***，BUXIELE.jpg】。

摆摆摆。领取密码条。到操场缓解压力。雀。

22:30 睡觉。

Day 1

定了 6:50 的闹钟，结果 6:40 自然醒了。

吃早饭。进入考场。

8:05 开考。

T1 计数，T2 期望，T3 交互。

发现 T1 的这棵树肯定是一条区。然后编了 \mathcal O(1) 种复杂度较高的做法。然后发现可以设 dp_{i,j,k} 表示两个当前右端点为 i,j 且选了 k 个的方案数。复杂度是 \mathcal O(nmk) 的。

先写了个空间 \mathcal O(m^2 k) 的，写了一会就过样例了。然后没发现可以滚动，但是发现我只有 \dfrac{m^2}2 k 个状态，而这么多个 int 是可以塞进 512MB 的，于是把前两维压起来就过 pretest 了。此时大概是 9:00。

开 T2，直接按住一下这个 \min 解一下判一下，然后直接二分，就变成一个简单的邻域查询了。让我追忆一下点分树咋写来着，好的追忆起来了。n 俩 \log，3.5s 包过的好吧。先写个暴力，获得了 50 分，然后写点分树，过了一会写出来了，怎么 TLE 80？卡卡常，诶诶诶我怎么调用了 \mathcal O(n \log^2 n) 次 LCA？改成 \mathcal O(n \log n) 次，直接过了。此时是 10:1?。

开 T3，这什么东西啊。大质数不是完全没法区分吗？？？哦哦哦原来需要根据插进去的位置搞事情。那是不是需要什么，（由二分/三分推广的）多分啊。可以用一些大质数来乘 2 \times 3, 3 \times 5, 5 \times 7, \ldots。但是这不是需要爆搜一坨东西并且判一亿个细节啊。发现可以直接维护一下每个数是否仍然可以候选，然后把剩余候选数最多的那个区间当成分到了那个区间继续分，这样可以省掉一堆的细节。然后发现询问所有候选数可以区分出来所有东西。于是写了个框架，前三次使用类似多分，第四次直接问。获得了 16? / 53（表示询问总长度与得分）。发现写挂了一个地方，改完变成 106/6? 了，调调参变成 90/68 了。发现又写挂了一个地方，改完直接变成 57/84 了？！然后发现我在有多个区间剩余数都比较多的时候会比较劣，于是改成了比剩余数最多的段的 \dfrac 2 3 还多的段都保留下来。又发现有一个东西是没用的，经过这些神秘小优化后获得了 52/88。然后发现乘在询问数上面的可以不需要是质数，只需要不被前 k 个质数整除，这样可以做到更优的 45/93。又经过了一系列的调参，调出了一坨完美的参，可以做到 39/97。然后发现最后一次询问的最后一个数可以扔掉，变成了 38/97（因为取整的原因没有增加分数）。

最后给 T2 卡了卡常，注意到上界其实只有 \mathcal O(\sqrt n)，这样就可以把瓶颈常数砍半。

Day 1 估分 100+100+97=\boxed{297}。查分没有挂。

小 D 声称队线是 270+。讲题，T1 原来可以滚动吗。T2 原来可以单 \log 吗。怎么这个 T3 纯不是题还被猛猛爆标了啊。

晚上摆烂。

Day 499122177 / 社会实践

社会实践啥东西啊。在车上罚坐了 1h。集合发展了 0.5h。罚站晒太阳了 0.5h。参观时长不到 2h，但是从上车到回到整整 6h 多。

下午大摆特摆。傍晚又去操场散步缓解压力。雀。不会 Graphomata。

Day 2

起来吃早饭。

意识到如果这场爆了，那么这就是我 OI 生涯的最后 5h 了。

T1 最优化，T2 看着是 ds，T3 是计数。

T1 首先二分，然后编了一个 dp，写完发现样例 2 恰好 WA 了 k=2,3,5 的点，猜了一下就是只有这三种会爆，于是判了一下补了一个 \mathcal O(nk) 的 dp，于是一共是 \mathcal O(n \log n)，滥用了一下 vector，写完过了所有样例，一交 selfeval 发现 T 了，怎么跑了 1.4s？把 vector 换成普通数组，怎么跑了 0.17s？此时是 9:1?。

T2 先写了个暴力，然后推了几下这个形式可以是一个二分后三维偏序，这咋跑。又推了很多下发现其实是二维偏序第 k 大，这玩意可以树套树上面二分做到 \mathcal O(q \log^2 n)，但是这感觉好难写啊，诶可以分块，复杂度是小常数 \mathcal O(q \sqrt{n \log n})，我按住它能跑，直接开写！……结果反而是暴力改版调了一万年，分块倒挺好写的。然后获得了 72 分，怎么前两个点 WA 了？哦哦哦边界判错了，改完 92，怎么是 T 了询问点 < 10^3 的啊？乱改了下块长就跑过去了。此时是 11:2?。

剩一个半小时，放在 NOI D2T3 的计数题，三重 buff，这我咋会啊，直接按住是不可做，编了个 \mathcal O(2^n n^8) 的 dp 试图冲 n\le 16，写了半天发现原来计数的是颜色数序列的方案数，假光了，于是紧急回去拼裸爆搜和链，剩下 20min 遂摆烂。

Day 2 估分 100+100+12=\boxed{212}。

出来发现有人声称 D2T3 是可做题，还有人声称集训队线 600+。吓哭了。

小 D 260+，吓哭了。

估分网站怎么 704 分 rk 两位数啊，[逆时针旋转大笑]

查分，没有挂。

0+100+(100+100+97)+(100+100+12)=\boxed{609}.

这个分数应该是几乎没有任何遗憾了。所有该拿到的分都拿到了。

发现集线只有 [560,580] 这么少。最后停在了 560。

晚上篝火晚会，感觉不如奶龙山一根啊。

去 355 参加了音乐 party。可惜的是时间有点短了。

Day 3 / 闭幕日

文艺汇演。英文歌神秘翻译。白鸟+蜂鸟+上山岗 夯爆了！zxx NOI rk1 还说批话。暖暖 非常好听！

去自习室唱歌。

闭幕式。突然很难受，很多很多我很崇拜的大哥们都爆炸，甚至退役了。打出了很多我认识/知道的选手的名字。被 15 位选手打出来了，记住你们了喵。搞笑的是女主持为啥连「梓」都不认识，这个字不是十个人就有一个名字里带的吗？？？NOI 2027 rdfz 再会，那我也没得去了啊（）

吃完晚饭，听歌，打雀，码下这篇游记，现在已经 1:30 了。

NOI 2026，结束了。

本来想写点内心情感的，但是不想让 NOI 爆炸的选手们更加难受，所以还是记成了流水账。

祝所有选手们都有幸福的未来。

[此处应有一张徽章大合照，之后补上]