NOI2026 游记

· · 生活·游记

先说一下为什么没写吧，如果你熟悉我的写游记习惯的话（一年都没写了怎么熟悉？）就会知道如果一场比赛我爆了个大的话就不会写。所以一年都没写游记就说明这一年比赛全爆了个大的。

  1. noi2025 day2 死磕集合没有把暴力写成式子啥都没做出来，还因此没时间写 t3 暴力了。

  2. csp2025 t4 不会延迟钦定技巧还没有往容斥思考结果吧会做。

  3. noip2025 t2 看了好久才搞明白结构，还因为把组合数卷积可以解决的问题思考了 dp 怎么做浪费了巨久，导致 t3 O(nm^2) 差一个字符没调出来。

  4. wc2026 t2 没有想明白建图细节打算写个暴力看看情况，结果没看到可以在非整数点出发没调出来。

  5. 联合省选 2026 d1t2 不知道为什么思考了一些奇奇怪怪的方向浪费时间，最后写的 dp 记了步数，思考了能不能压一维状态进值域，先思考了个错的就没尝试了，没发现把步数压进值域就对了也没发现倒过来 bitset 是可行的（没发现倒过来考虑的时候要稍微改下状态定义），写了 60 还挂了 5 分。

  6. 联合省选 2026 d2t3 写了后面的包但是因为 day1 心态有点烂了懒得拼前面的包了（这个其实是爆小的，但是为了凑字数写在这里了）。

  7. apio2026 t1 对学习了延迟钦定后的自己非常自信，依然没有思考容斥，并且思考延迟钦定做法的时候还没有意识到直接合并一段比把一段结构拆开一个个合并劣，甚至没意识到直接合并是 O(n^4) 的（虽然后面得知可以优化），导致写了巨大久只有 65，接下来我甚至尝试去优化，最终导致 t2 爆 0。

经历了以上种种，noi 2026 我的目标就是拿个 ag 得了（可能也有些幻想），但是别爆个大的依然是我的目标。

最后你看到了这篇游记，说明我只爆了个小的，接下来详细揭秘一下过程。

赛前集训

十分搞笑的是，虽然我正赛爆了好几次大的，模拟赛确总是打的勉强像个人，使得我一度怀疑模拟赛是不是题目风格全错了，但是也说不定是打模拟赛的过程让我的策略优化了？

Day1

进场先看 t1，琢磨一下发下结构大概形如一前一后两条线段轮流向后扩展，直接 dp 可能是比较高的复杂度，但是我们把向后加线段的位置一个个向后推（或者说前缀和优化？）就可以做到 O(nmk)。开写，调了一些诸如必须联通的 bug 之后在 1h 时通过了 selfeval。

接着看 t2，推了一下很快会了 O(n^2) 做法，瓶颈是一个单峰优化（推到这我还没证明是单峰的，但是很显然不单峰做不了），再仔细推了一下发现是最小平均数前缀，那么确定是单峰的了，并且不需要对所有根都去二分了，因为相邻的根变化量是 O(1) 的所以最优答案（同时也是决策，因为是最小平均数）变化量也是 O(1) 的，用点分树和前缀和维护可以做到 O(n \log n)。

想到这里我有点拿不定主意，noid1t2 这么 dirty？但是思考了一下没有其他的发现（最优决策点虽然很小但是容易分析出是根号的），只好开写，大概还剩 2h 时通过了 selfeval，但是再测一遍发现被卡常了，又花费了 30min 卡常。

然后就是爆小的环节了，t3 嗯构造一万年会了个锤子，对着 A 性质做了一万年又会了个 19 分的锤子做法，想了下搜和随机化但是发狂了认为没道理，最后发现第三个 sub 还能拼结果没写完，33 遗憾离场（查分时发现挂成 32 了）。

一出场问了一下发现爆了个小的，全是随机化和搜索高分，那能咋办？安慰下自己 day1 比对线低几十分 day2 打上对线也能赢。

Day1.5

社会实践没啥好说的，晚上随机散步。

Day2

进场依然先看 t1，发现 t1 就是个大的，编了下做法发现大概会了，写写调调好久发现 k \leq 5 还需要特判，又写写调调在 2h 时通过了 selfeval。

看 t2 很快会了暴力，然后马上意识到只要使用树套树维护一下就对了，很显然这个题不过肯定炸了，没办法硬着头皮开写，又是一段痛苦的时间，最后在还剩 1h 时通过了大样例，提交 selfeval 荣获 40 分。

发现大部分点跑了 2+eps 秒，并且我需要对一个询问查两次，仔细思考发现特判一下就可以查询一次，获得 84 分，又对树套树卡了卡常（去掉了意义不明的 pushup）获得了 100 分。

还剩 30min 做 t3，但是我发现由于我几乎没写过树套树，导致我以为空间是 O(n \log n) 的，但是实际上是 O(n \log^2 n) 的，开 200 倍不知道为什么过了 selfeval，仔细思考发现空间是一倍 n \log^2 n 加若干倍 n \log n，开 400 倍刚好够，改了下代码确认还能跑过。这个时候没有啥时间了，给 t3 写了个 4 分代码就结束了。

看上去 day2 上 200 的并不多，存在一个时间段我还以为我翻了，结果很快意识到其实没救了。

一个幽默的事情是，day2 对线是 208，我确实几乎打上了对线，然而于事无补。

不过这又能咋样，抽奖失败也只能受着了，不想启发式算法写代码太慢也是我自己的问题。至少保住了 ag，明年加油吧。

文艺汇演（我与 NOI 主题活动）很好看，能不能只参加这个啊？