NOI 2025 游记

· · 生活·游记

第一次参加国赛，也是来看看大场面。

7.11

来到绍兴，飞机上在看炸梦二创。和 zh，油渍以及涨跌吃饭，晚上自习尝试对一个没有单调性的东西做整体二分，调到红温才发现整个都假了，赛前能不能不要搞心态 /kk.

7.12

报到日。国赛环境果然好，虽然只有一半床位下面有插座的设计令人疑惑。下午帮弥撒分发徽章，上门送货也算半个面积。晚上和舍友打胡闹厨房。

7.13

试机赛 & 笔试日。上午是开幕式，不过没什么印象特别深的场景。中午不知道要提前集合，午觉睡一半被宿管叫起来，一路上被家长教练电话轰炸。场上撞见了 sk 酱，我喜欢你！怎么试机还是 NOIP，我还是只会写 T2 /ll. 笔试也是没有意外，心态也是稳定一些了。晚上写了一下去年的 D1T2 和 D2T1，保持手感。

7.14

Day 1. 睡眠质量不大好，但是状态似乎还不错，可能和大考对神经的刺激以及风油精有关。

T1

简单题，花了 1h 左右。

T2

最早的方向是区间 dp，后来发现难以优化，同时发现每个值必然对应原序列上的一段区间，于是可以计算出每个区间对应的半环信息，直接 O(n^2) 转移即可。花了 1.5h 左右。

T3

一开始看错题了，写了个假的 dp 浪费了一些时间。发现错误后考虑两条路径对应的约束，一开始以为是一个三元关系，于是写了一个 O(\frac{n^3}{\omega}) 的 bitset 维护 01 矩阵，后来发现是二元的，于是改写作 O(n^2) 的做法，夺得 56pts。

赛后发现有一车 280，不过感觉还挂在队线上。原来可以异或哈希做到 O(n \times 树高)，但是我完全没发现对应的结论，哭了。下午打了会 phi，心情放松了些。晚上有 sk 在操场上的笛子表演，好听。

7.15

社会实践日。原本要去兰亭，那不得热死，还好改成室内了。馆里有很多神秘设施，还有电影环节 /jy，所有的互动式电子屏似乎都被 hack 了，可怕。下午还有电影环节，但是我们三个躺床上了。晚上又是例行的押题环节，zd 说会有字符串和模拟费用流，一看就不是很有道理。讨论了一段时间的数据结构，但是实际上什么都没写。晚上肚子疼。

7.16

Day 2. 刚起来身体状态不大好，吃了点药，到开赛的时候就没啥问题了。

T1

刚开始没啥思路，简单模拟了一下就看出来了一些规律，发现可以变成寻找特定子串的最早出现位置，线段树维护自动机转移即可，花了 1h 左右。

T2

又是指数级神秘题目，发现“按位与相等”这一约束难以直接刻画，考虑容斥，推一推式子就得到了一个形如或卷积的东西。但是这需要对 a_i+1 求逆，所以只能通过 B 性质。此时将每个数改成形如 a\times 0^b 的形式并忽略更高次的 0，直接做就是正确的，可以通过一些单调性证明。于是我们得到了一个 O(2^nn) 的做法，花了 1h 左右。

T3

完全没有正解方向的思路，于是写了一个 O(nq\log n) 的二分 + dp，发现可以拿到 35pts，而且第 8 个点跑进了 4.5s，于是稍微加了以一些常数优化，拿到了 40pts.

赛后发现这个分数好像还不错？油渍进队了，还是太强，这就是 Day 1 280 的力量吗/bx. 晚上的篝火晚会有抽象布条火焰，还有蹦迪曲 SpadeA（？总之还是很好玩。

7.17

闭幕日。 上午是“我与NOI”活动，有好多精彩的节目，感觉各位都好厉害。sk 好闪！下午是闭幕式，Cu Au 竟然是 dzd 单独颁奖，这么有排面。和 sk 道别，明年青岛再见。

感觉这一次的成绩有很大运气成分，心态也因为是 D 类所以好很多，总之明年再战的时候要加油啊。