NOI 2025 游记

· · 生活·游记

游记是要写的，不然多年以后可能都记不起自己的比赛分数了。

07.07 - UNR Day 1

T1 是构造题，两个小时过了。然后死磕了一场的 T2 没写出来，最后 T3 暴力也没调完，破防了。

结果全世界都比我高，得调整状态了，不然银牌都拿不到了。

07.08 - UNR Day 2

T1 拼尽全力终于战胜，感觉这个题很厉害啊！发现 T3 暴力分数少得可怜，于是后面两小时都在做 T2，用生日悖论 + 根号平衡乱搞搞，居然获得了七十多分。

出榜发现 rk32，看来我还是擅长交互题（）

最后两天的总榜荣获 rk51，算还可以的成绩了，不过如果想拿金牌还得加把劲。

07.09

白天坐高铁，前往绍兴。

晚上在酒店里写 [WC2018] 通道，细节有点多，写了一晚上，代码能力还是太低下了。

07.10 ~ 07.12

最后三场模拟赛了！

第一场 T2 没调完，第二场 T3 没调完，第三场 T1 没调完，平均下来喜提 rk30+。如此状态，如何 NOI？

十二号下午去报到，宿舍条件非常好。晚上和室友玩你画我猜，权当是复习算法了（不是）

07.13 - 开幕式

早上开幕式，“我认识鲁迅比较早了”，“美国制度好”。

下午是笔试和试机，CCF 终于把笔试题换了，不过还是拿下了 100。

试机是 NOIP 2024，趁此机会做了一下 T4，结果秒了 O(n \log^2 n)，赛时的我在干什么？

晚上忽然意识到明天就要考了！紧急 rush 板子，但是还是未能完成目标。

十点熄灯。凌晨醒了几次，不过并无大碍。

07.14 - NOI Day 1

开考先读了一遍题，感觉 T1 看着像根号分治优化建图，T2 大抵是 DP，T3 可能是结论题。

然后做 T1，根本不用根号分治，直接建分层图就可以了，疑似普及组题混入 NOI？

然后我就开始犯糖了，由于身边的人不知为何都没开始写代码，我怀疑了半天做法的正确性。写的时候也很紧张，接连写错了好几个细节，将近 9:30 才过 pretest。

天崩开局，感觉要完了。赶紧去卫生间洗把脸，调整一下状态，结果在路上接连遇到了四位同省选手，没绷住（）

回来以后接着开 T2，这时候清醒多了，很快就想到了 O(n ^ 3) 的 DP，拿到了 60 分。

数据随机的情况下合法段一定不长，那么从 \min(1, i - 500) 转移就是对的。改了改，没想到不仅过了 AB 性质，还把所有点的第一问都过了，直接拿到了 85 分。

这时刚刚 10:00，我又活了？

很明显，T2 用排序 + 二分 + 树状数组能优化到 O(n ^ 2 \log n)，但是不太好写，也不一定能过。

反正不差这 15 分（伏笔），于是去做 T3。先推 A 性质，在纸上写写画画，很快发现了两条性质：

于是大胆猜测答案就是 2 的幂次，指数就是上述两种情况之和。

那么扩展到一般情况，只需考虑子树内出现次数恰为 1 的颜色，将第二种情形改成等价类的个数即可。

但是我又犯糖了，不知为何 xor hash 都能写挂，导致样例的答案全错了。我还以为是结论错了，白白浪费了一个多小时的时间 /ll/ll/ll

12:00 的时候终于过了 56 分，此时 241 分。

这时我把 T3 的 AB 性质看反了，以为 O(nd) 只能过 64 分。那我想，T2 有 15 分，T3 有 8 分，我选择 T2！

写到一半忽然发现 T3 O(nd) 有 80 分，此时还剩 40min。重新评估了一下，T2 有 15 分，T3 有 24 分，我选择 T3！

然后......不出意外又要出意外了，我没有调完 T3 的 80 分。

最终 Day 1 分数定格在了 100 + 85 + 56 = 241，属于是优势场打崩了，估计还是状态没调整好。

出场和 hz 交流了一下，他直接斩获 100 + 100 + 80，太强大了。

下午去查分，并没有什么人挂分。队线大概 256，正好差了 T2 的 15 分。

晚上想了想，我本来也没有金牌实力，银牌已经是很好的结果了，心态平稳了一些。

07.15 - 社会实践

早上去了科技馆和城市规划馆，内容是有趣的，解说是无聊的，于是脱离大部队自己去逛。

下午播电影《人生大事》，没啥意思，提前回宿舍了。

晚上继续复习模板，终于把会的板子都写了一遍。

忽然发现自己还不会 FWT，不过考前不宜学习新算法，明天也不可能恰好考到这个内容吧（伏笔）

仍然是十点熄灯。

07.16 - NOI Day 2

开考先做 T1，很快发现了结论，30min 过了 O(n ^ 2)。

优化到单 \log 只要加个线段树就好了，但是并不好写。先去看后两题。

然后看到 T2，脑中蹦出了几个词：集合幂级数、FWT、子集卷积 —— 心脏骤停，看来 Day 2 也要没了。

但是我不甘心，所以还是硬着头皮来做这题。

低头写写画画，但是没有取得任何进展。抬头已经 9:30 了，大惊失色，于是先回去把 T1 写了。

十点的时候过了 95pts，最后一个点被卡常了。优化了半天，只能卡到 2.5s，只好先弃了。

然后去做 T3，想了想发现贪心是对的，这样就可以 O(qn \log n) 了。写了一发，过了 35pts，稍微卡卡常就过了 40pts。

这时候，我知道自己银牌已经稳了。最后两个小时，我打算全力冲击 T2。

考虑容斥，去计算 g(X, Y) 表示 X \subseteq f(P), Y \subseteq f(Q) 的权值和。直接做是 O(8^n) 的，稍加优化可以 O(6 ^ n)。

进一步优化的难点在于 a_i = 998244352 会使得中间结果可能为 0，不存在逆元。这时忽然想到：可以把每个数写成 a \times 0^b 的形式，在这种形式下去做乘除法运算就好！

成功做到 O(4 ^ n) 了，拿到了 36 分。

但是我犯了一个很严重的错误，没有把 | X \cap Y| 拆成 |X| + |Y| - |X \cup Y|，而是直接枚举 X \cup Y 和 X \cap Y。

最后推到了一个 OR 卷积的形式，只要会 FWT 就能做到 O(n \times 3 ^ n) 了，但是我不会。

此时已经 12:30 了，彻底绝望了。最后半小时做了一些象征性的转化，但是并没有取得实际的进展。

最终得分 5 + 100 + 100 + 85 + 56 + 95 + 36 + 40 = 517，没戏了。

出场又遇见了 hz，他拿下了 100 + 100 + 35，金牌已经稳了。

不久前还是朝夕相处的同学，而如今已经是两个世界的人了，实在令人感慨。

回去重新想了想 T2，发现把 |X \cap Y| 拆开再做 OR 卷积就过了，这下这下了。

下午查分并没有挂，听说队线 571，还是差在了 D2T2。

晚上去打球，被虐爆了。九点多的时候精疲力尽地回到宿舍，十二点睡了。

07.17 - 闭幕式

早上去参加了我与 NOI 活动，歌舞表演很不错，但是演讲全是批话哥，怎么会是呢。

下午颁奖典礼，JX 拿下了 1 金 3 银 3 铜 1 铁，而我们宿舍恰好是 1 金 2 银 1 铜，鉴定为二项式系数。

hz 并列 rk17，成为了 JX 的第三块信息金牌。

pa 和 lzh 都 Cu 了，为他们感到深深的可惜。

晚上收拾行李离开绍兴一中，回望身后这个无数人梦想的汇聚之地，只感觉一切都像是一场梦。

结语

又一年的 NOI 结束了。亲眼见证了金牌的诞生，也看见了金牌的可能，梦想中的图景也渐渐清晰了起来。

让我们明年再会！