NOI 2026 夏令营游记

fydj · 2026-07-27 21:41:23 · 生活·游记

前言

文章包含大量主观看法，如果读者感到不适作者道歉，如果读者意见不合那么读者的意见是对的。

选手侥幸进入三倍队线，以 D 类选手的身份参加了 NOI2026 夏令营。

比赛过程中的时间线可能不是很准确。

这次当然达金牌分数线最好，不过深知不太可能达到，于是订一个次级目标，高分银牌，指达到正式选手的前 80 的分数。

具体到每一天，要求平凡部分分打满。每天至少一档非平凡部分分。

2026.7.17

提前一天到达青岛，据说是为了预防飞机延误之类的状况。

飞机上欣赏了《上伊那牡丹，酒醉身姿似百合花般》，但只缓存了前 3 集。

晚上教练请吃牛肉火锅。回到酒店继续欣赏《上伊那牡丹，酒醉身姿似百合花般》，把 4\sim 9 集无倍速看完了。

2026.7.18

报道日。

教练发现了自习室，于是让我们在这里自习。

下午和晚上还是打打模板赛。

考前学长表示不要做新题，于是没有做新题。

2026.7.19

开幕式和试机。

开幕式的艺术太前卫了，看懂了，可以欣赏，但不是很喜欢。

dzd：制度不好。

dzd：让 CCF 管中国足球。

开幕式结束后回宿舍自习。机房网络太差了。写了一下 LCT。

下午试机的题目居然不是 NOIP2025，而是 WC2026。没去 WC2026 的选手也体验了一把 WC2026 的感觉。T1 写了 84 就不会了。

笔试检查了三遍，不出意外地满分了。

吃完饭后，没有像去年一样有经验分享环节。然后在操场上散步。

晚上回宿舍和同学校的超高校信竞生、带病打 NOIP2025 依然 290+、联合省选会摩卡串、广东 E 类队爷、神 YYZ 打 Duel，赢了一把输了一把。输的那一把是 CF1406E，死活调不出来。这里埋下了伏笔。

2026.7.20

NOI2026 Day1。

走入考场那一刻，终于意识到了，原来要考试了啊。

由于密码条发晚了，比赛延迟了 5\text{min} 结束。不过可以提前看纸质题面。

先看题。T1 一眼区间图，区间图是弦图，这是弦图计数？感觉很可做。T2 一眼会 50 了。T3 还是一分不会。

T1 仔细观察，发现树的结构相当简单，列了一下 DP 式可以时空 \mathcal O(nmk) 解决，但当时是顺着 m 这一维 DP 的，不太能滚动，空间爆了。写写写，有 52 分。

感觉有点破防，还是先写写别的题的暴力吧。T2 写了 50，T3 写了 14。

接着回过头看 T1。还是先考虑卡空间，发现顺着 k 这一维 DP 虽然时间复杂度不变，但空间复杂度变成了 \mathcal O(nm)。写了一下，写完发现直接卡过了？！

此时过了 2.5\text{h}。但非平凡部分分已经写完了。

看 T3。先构造相邻质数的乘积，然后构造相邻整数的乘积，大概有了 34 分。但接下来手动删除了询问的一些数，花了 20\text{min}，多拿了 3 分。之后觉得做不动了，于是切换到 T2。

但此时我的 T3 解法中，Q=2。这意味着，还有两次询问没有用上。

T2 发现可以二分答案的整数部分，于是会链了，写完有 60。

然后开始魔怔了。

接着发现答案 \le \mathcal O(\sqrt n)，于是只需要知道离 y 距离 =1,2,\dots,\sqrt n 的点有多少个就行了。

这个可以用点分治解决，于是我们获得了一个 \mathcal O(n\sqrt n\log n) 的做法。

觉得可以通过 10^5，写完还真的可以。最后有点急，调了有点久，花了 1\text{h} 写完。然后有 80 分。

接着比赛就结束了。

出考场，发现全部人都会 T2，更有人说 T3 比找寻着简单一百倍。瞬间破防了。

查分。100+80+37=217。

YYZ T3 60+，但 T2 爆了。lnw143 和我同分。

发现 T3 98 分也不是不可能想到。但好多好多 280+ 的人啊。

晚上就没事做了，写了一下 Phigros 自制谱，把 D/N/A 的前半段采音。但实际上仅仅为了消遣，并没有打算把它完整做完。已经好久没有完整写过一张自制谱了。

只能看看 Day2 能不能翻。

2026.7.21

在这个特别的日子里，我们迎来了社会实践活动。

这次的主办方组织得不如上一次绍兴一中，坐车四小时，参观一小时。

回来还有点中暑的感觉。

下午看了《佐贺偶像是传奇 剧场版》，很欢乐的电影。

2026.7.22

NOI2026 Day2。

T1 先写了一个 \mathcal O(nk\log ^2 n) 的做法。但没法优化。然后把 T2 的 20 分暴力写了。

接着发现 T1 可以贪心，2\text{h} 过了 selfeval。

中间为了查错，写了一个对拍，找到了一个小错误，改完以后依次通过了大样例和 selfeval，觉得没问题了，然后就去看其余题目。这里埋下了一个伏笔。

T2 怎么看怎么不会，思考部分分时觉得思维很混乱，不太能获得其余的分。于是转向 T3。

显然要先想如何判定，发现可以贪心去做，每个节点维护 t_i 表示子树内最多剩多少种颜色没有匹配，c_i 表示子树内有多少种颜色，直接贪心，验证了一下是对的。

接着发现会 \mathcal O(\text{poly}(n)) 的做法了，转移时只需要关心子树间的 \sum c、\max c、\sum t、\max t 即可。

写完我也不知道时间复杂度是多少，大概是 \mathcal O(n^6) 吧，总之可以过 n\le 100，有 48。

接着把链的部分写了，有 52。

还是想着把空间卡卡看看能不能通过 n\le 150。一开始用 vector 试了一次，发现很慢，于是用指针再试了一次。发现虽然空间可以接受，但时间上需要 4\text{s}。没救了。

此时再回去看 T2，依旧没有头绪，就是不能把它形式化地刻画出来，很混乱。看来只有 T3 可能继续拿分。