NOI2026 游记 - A Grounded Ascent

NOI2026 游记 - A Grounded Ascent

Intro

7.8至7.16 NOI 2026代码源赛前公益集训游记

四周是绿叶，是蝉鸣，是一缕童年的怀念。

盛夏缓缓而来，朦胧午睡醒来后，这段文字忽然出现在脑海中。我翻出初二时期的摘抄本，在并不成熟的仿写里找到了这句话。泛黄的字迹显露出当年的稚嫩；如今的我已经学会迎合科任老师的偏好，写出许多不同字体，可这句话的字形却再也无法复现。两年的「磨砺」最终磨平了少年的心境，许多事物也如同这句曾被我写在每篇记叙文开头的话一样，被尘封在角落。

恍然间发现 APIO2026 游记 最后一节的话已经失去了时效性，也该把它放出来了。

Verse

7.18 中午在崂山聚餐，下午安全抵达 cyyz，和 WC 时的感觉很不一样，不知道是季节的原因还是心态的原因。

第二天开幕式上印象最深刻的是《大海，我们来啦！》，但并不是因为节目太雷霆，而是因为伴奏是《大海啊故乡》的变奏（甚至有一段就是直接用的原曲），唤醒了一些小学和初中的美好但不美好的回忆。越想越会怀疑过去的自己做的决定，最后只能以另一个世界线也会有很多怀疑，世界就是在矛盾的循环中向前之类的话安慰自己。

下午笔试平稳 100pts，这个试机为什么不是 NOIP 是 WC，这下不能大战 sale 了啊。尝试取得 paint Sub4 的 4pts 答案分未果。

由于开幕式对着大空调吹了 1h+ 回去鼻炎直接发了，我 chovy 才好了一周不到啊。下午 + 晚上直接梦游状态，ARC 也打不了了，戴着口罩才能入睡。

Chorus 1

7.20 凌晨 3:00 就醒了，到 7:00 才想起来其实可以看世界杯。

还是没能避免「考前综合征」，明明考前心态则好，唔。可能也有鼻炎的因素，反正挺难受的。

进去冥想一下先，欸好困难啊，好像几个月没有冥想过了，怎么更烦躁了。到 8:00 了还没发密码条，果然又延时 5min 了，那我说啥。

看题，T1 计数，T2 DS，T3 神秘 cake 状交互。做了下 T1 得到层数 \(\le 2\)，结果打了个喷嚏转头就忘了。

到8:20时，结构仍未刻画出来。我觉得状态不太对，先去做了T2，得到\(O(n^2\log n+q)\)的做法。随后调整答案式子，发现可以像01分数规划那样二分，从而转化为树上邻域数点模板，直接使用点分树。于是我以为自己会了，但又觉得不对：为什么只能做到3log，是否还缺少某个性质？按理说这是静态问题，数据结构层面应该可以直接做到2log，可我怎么都想不出来。感觉鼻炎影响了思路，总觉得需要线段树处理区间查询，但静态问题显然直接用前缀和即可。继续观察式子后发现，不等式一侧是\(n\)，于是猜测答案取得的层数不会太大，但又觉得不太稳妥。先写一个\(O(nq\log n)\)的程序验证正确性，8:40在SelfEval中得到40分。

简单看了下 T3 发现只会 eps 分，那咋办。于是策略变为先做完 T1T2 再拼 T3。

滚回去做 T1，这下想起来只有两层了，然后经过了一些按层 dp 的尝试未果。于是尝试从左往右加入线段，发现只用记录右端点最大的线段和右端点第二大的线段的右端点（也就是最后一个被覆盖了两层的位置）就可以转移了，可以做到 \(O(nmk)\)，真能过吗？

选择相信机子速度和自己的常数，没怎么调 0.7s 通过了 SelfEval，那感觉不用卡了。此时 9:40 在 SelfEval 上取得了 \(100+40+0\)。

继续做 T2，感觉 3log 的点分树可以取得 eps 分就没有写。试图做换根状物，由于没有写点分树搁置了暴力移动答案的想法，赛后才知道相邻两个答案位置真的不超过 \(1\)。

最后半个小时还是只有 \(100+40+0\)。紧急拼包，给 T2 改成 50，然后加上链取得 60。做 T3，先问了个 \(2\times 3,3\times 5,5\times 7,7\times 11,\cdots\)，可以花费 30 左右把质数确定到长为 60 左右的区间内。但这里脑抽了最后一次询问把整个区间都问了，实际上只用问质数。同时这个做法可以做非质数但我太急了没拼，在 SelfEval 上得到了 \(10+3+0\)，蚌。

最后 \(100+60+13\) 遗憾离场，很明显我爆了个大的。感觉是个人都比我高，好像确实是，Day2 成为 Ag 保卫战了。

同校最高分是初三 D 类 @XiangXunYi，也是同校唯一通过 T2 的选手，则我们的正式选手在干什么呢。原来 @spdarkle 和 @paper_ T2 分别写了 2log 点分树和基于结论的根号取得了 80 和 80 的高分。虽然也很炸裂但都比我一个是人就会的 60 好吧。

得知 @spdarkle T1 T2 都被卡常，别人的同复杂度都过了，而他取得了 \(92+80\)。@Grisses 似乎很爆。祝他们 Day2 好运。

得知 @Nangu 294，太牛了，祝他顺利进队。

Bridge

社会实践，6:00 起床说是，头痛，晕车。神秘早餐，不想吃，头晕：

经过车上不知道多久的优质睡眠后抵达海军博物馆。参观了军舰，印象最深的是：

看到「文化大」后面感觉应该是「革命」二字，因为这两个字在后面也出现了多次所以确定了自己的想法。

花了 40min 速通博物馆的四个展区，极限卡点集合，但等车等了 inf 小时。回去大概一点，发现中午的饭很合胃口，土豆丝和油麦菜给到夯，再加上没吃早饭 & 昨晚上人不舒服吃的泡面直接大吃特吃了一波。

下午和教练、@XiangXunYi、@Grisses 一起打牌 mood swings，上手之后发现从弃牌堆拿牌的牌特别牛，在后期可以拿到牌堆里的强卡，甚至可以拿从弃牌堆拿牌打的牌进行套娃。靠狗运拿到了很多 Myth 级别的卡，有两局都是前期倒一后期翻盘，是不是暗示我 NOI 也这样（）。

Chorus 2

打 Ag 保卫战，欸诶欸。

开场看题，怎么计数在 T3，T2 依旧 DS。简单做了下 T2 T3 感觉应该 T2 是能做的，但 T3 感觉不会 \(n\leq 16\)，那咋办。

然后做了 inf 小时 T1。首先二分答案转 01，问题变为能否选出大于等于一半的段是 \(1\) 更多，且这些段至少有 \(\lceil\frac{k}{2}\rceil\) 个。发现有个 \(k>5\) 的包，而且大样例都是 \(k>5\) 和 \(k\leq 5\) 几乎对半给的，那说明要分讨了。特殊性质还有一个 \(k\) 是偶数，所以偶数有什么用呢？发现不管我怎么分，\(1\) 段都最多比 \(0\) 段少一个，且 \(1\) 段大于等于 \(0\) 段的条件是存在至少一对相邻两个 \(1\) 段相邻（边界也算）。同时发现对于 \(k\) 是奇数就是把至少一对成为至少两对。

写了个暴力 dp 发现能过大样例 \(k>5\) 的部分，说明思路对完了。先拼了个 \(k\leq 5\) 的暴力 dp，算上二分是 \(O(nk^2\log n)\) 的，带很小的常数所以应该能过。

然后想如何改进 \(k>5\) 的判定，感觉肯定得做线性，不然没有过的道理，那就只能贪心。急了 1h 不会做，于是直接树状数组改进 dp，然后以大常数 2log 喜提 SelfEval 75。

不知道几点钟的时候跑去做 T2。先花了 10min 回忆 Prufer 还原树，带 log 的做法是维护小根堆，每个点在最后一次出现之后变为叶子加入堆，每次取出堆顶就是叶子。假设 \(x\) 是最后一次出现更早的那个，则我应该求出 \(x\) 弹出堆的位置就行。这样只用考察 \(<x\) 的元素，这个东西的数量是有单调性的，所以我可以直接二分。因为需要对 \(r\) 扫描线来维护每个元素的最后一次出现，且查询需要对位置二分的同时维护 \(<x\) 的限制，所以这是个动态二维偏序，显然可以树套树然后外层树二分做到 2log。

看起来是个正常人这里都应该会了然后花少量时间就可以通过。但我的状况并不正常，在想怎么求从 \(l\) 开始到 \(x\) 最后一次出现的位置堆里面会剩下多少 \(<x\) 的数，因为这个过程可能会有 \(>x\) 的顶上来。赛后才发现一旦出现这个情况后面 \(<x\) 的数就一定是 \(0\) 个，支持二分的单调性转头就忘了，也是 Day1 区完 Day2 区这一块。

然后望着 SelfEval \(75+0+0\) 感觉要 Cu 了急哭了开始狂暴拼 T2 非常简单的 52，30min 写完调完在不知道几点钟取得了 \(75+52+0\) 的超高分数，同时忘了后面其实还有包可以拼。

然后继续狂暴想 T1 不会，特别烦躁于是看 T3，发现 \(n\leq 16\) 还是不会，那咋办。发现链会特别麻烦的做法，那咋办。

还剩 1h 的时候算了下分，假如 \(100+173+(75+52+0)\) 刚好 \(400\)，这比前几年 Ag 线低而且今年的题体感很简单，则肯定完蛋了。假如我拼上 T3 的 \(8\sim 12\) 分可以有 \(408\sim 412\) 但也很悬，则感觉我需要通过 T1 才能拿到 Ag。

于是没有拼 T3 暴力继续狂暴做 T1，感觉这个状态确实不可能想出贪心所以直接大力卡常，发现某个转移的转移点可以用一个把其它全部偏序掉（赛后发现实际上就是贪心把一个 \(1\) 单独分一段），可以砍掉巨大常数。然后在 SelfEval 上 0.8s 直接过了，2log 偷过去的来了。但我自己造 \(n=10^6\) 且 \(k\) 是奇数会直接爆到 1.2s，那咋办。

最后 10min 感觉真卡不动选择相信 SelfEval 和 systest 一样强所以跑去拼 T3，幸好代码能力没有荒废 5min 就拼上了 8pts，最后 \(100+52+8\) 离场。

@paper_ 过了 T2 翻上了 500，狂暴膜拜。

@spdarkle 说他 T2 没调出来，大样例 2 挂了一组，最后 10s 不知道暴力粘过去有没有 Ctrl+S。我说大样例 2 的那一组我写暴力的时候也挂过应该算是 corner，问他为什么不交一下 SelfEval 看看多少分他说那就是最后的时候才 diff 出来只挂一组，SelfEval 已经跑不出来了。

经过了一段提心吊胆的时间，好在复评的时候 T1 没挂，则就是 \(0+100+(100+60+13)+(100+52+8)=433\)，Ag 应该还是有的。

@spdarkle T2 暴力由于有 \(5000\times 5000\) 次 cerr 忘记删 T 飞了成为 8pts 并以一分之差抱憾铜首，D1T1/D1T2/D2T2 但凡哪个地方多出来一分都能躲开最坏结局，只能祝他高三顺利了。

Outro

嘉年华太抽象了，居然歧视文科生（）。

第二天《我与 NOI》没去，因为以往的文艺汇演感觉一大半都在唱歌，然后大部分都唱得很一言难尽。再加上头还是很晕就窝在宿舍里睡觉了。

闭幕式 dzd 说要学习国外的颁奖，结果诞生了名场面，还是太会挑染氛围了。

晚上飞机从 21:55 一直晚点到 23:49，快 3:00 才到家，幸好马上可以享受长为三天的假期。出门半个月，对重庆火锅甚是想念/ll

Hook

感觉写到这里才是真正的 Outro 部分，欸又管不住倾诉欲要写大作文了，这种时候应该加上免责声明如有不适立即退出就是了。

说没有遗憾是假的，不是因为牌子颜色，而是因为两天都没有打出该有的分数。某种意义上来说这场 NOI 我就只是拼了平凡的暴力而已，体感上很不尽兴。rk153 这个结果和这一年的所有比赛比都是最差表现，更别说理论上水平应该有所提高。

还要不要继续这件事情确实要考虑的因素很多。从功利的角度来说高一 Ag 退役确实是很好的选择，两年时间对我来说想要拿一个高分并不困难，甚至按某些老师的说法有不小概率上 T/P 的裸分线。但也正是如此，涵盖我在内的很多人都会觉得「有点可惜」。

说来可笑，真正让我下定决心的是 NOI2027 的举办地点，北京，这个承载了我不少美好回忆的地方。那就说好了，带着办一次公开赛、打一次 THUPC 及更多的执念继续走下去吧。不管过程多艰难，不管结果多难堪，为了 occasional 的最本真的感动而接受常态化的苦痛本就是人类的天性。

May this journey lead us starward.