NOI 2025 惊险翻盘记

· · 生活·游记

Day -?

七月初就是 mx 的赛前集训，打的都不太好，基本没发挥出啥水平。

UNR Day1，T1 做了几乎 3 个小时，同时做法细节很多，过的时候头已经有点痛了，后面看了 T2 和 T3，T2 一开始就感觉是模拟费用流，然后就似了。看了看 T3，不过一开始不知道为啥感觉 DAG 可达性是对的，后来才发现不对，不过已经没啥时间加乱搞了，最后获得了 100+38+24 的高分。

UNR Day2 倒是还行，T1 很快过了，T2 一开始没啥思路，一个小时过后发现我还在胡思乱想，甚至不会合并两个独立集，然后简单思考了一下怎么合并两个独立集就立刻得到了一个分治的 O(\log^2n)-O(n\log^2n) 的做法，大概就是显然若干条链可以拆分成至多两个独立集，所以直接做就好了，写了有点久，写完过了 60+ 分。

然后加了点优化，简单卡了卡常，最后发现分治分成 10 叉树比较优秀，可能是刚好是满的导致的，最后获得了 202+eps 的分。

好像刚好卡进去，希望 noi 也能有好运。

Day -1

感觉没做什么事情，就做了两道题就睡觉了，试图保持平时的状态

Day 0

上午开幕式，感觉小品很抽象，dzd 讲话还是很劲爆，下午笔试的时候坐在了 WC 时候的位置，希望能继承一下 Au（。

笔试检查了若干遍，总之满了，不过写了下 NOIP T4，发现 1log 会极限被卡常，不过我赛时写的 2log 怎么轻松通过了？

一郭的笔试怎么 99 了，原来是申请加时错了，感觉确实有点坑。

晚上没做题，看了看做题笔记，因为去年的 noi 感觉可以说是很多套路，比如感觉 d1t3 和 agc025e 基本上没啥区别啊？然后和教练在操场随机游走了 45min，心态 ++。

Day 1

怎么这就 Day1 了？怎么这就 Day1 了？怎么这就 Day1 了？

上午要求起的很早，不过还好正常睡觉也能睡够 8 个小时，集合的时候感觉还有一种在梦里的感觉，直接快进到开题吧。

打开题一看，这个 T1 不是最短路板子？怎么连 J 组都不如了，我们 noi 是不是要没题了，20min 快速 rush 完。开 T2，感觉这个形式我前几天在看某道题的时候见过，不过我忘记那个题咋做了，有点红温，然后开始编一些结论。

比如肯定要考虑怎么把一个区间删空，通过打表发现给旁边的贡献值至多只有两个，简单分析一下可以奇偶分类视为一个匹配的形式，通过 Hall 定理求出上下界，然后猜测只有这两个值可能取到。

直接做是 O(n^2\log n+n^3) 的，不过我有点唐所以没发现这个东西可以前缀和优化，不过还是写了，在 2h 的时候获得了 60 分。

然后感觉这个分数还可以，看看 T3，然后感觉 A 性质看上去比较能做，做了几乎有一个小时发现我咋这都不会做，红温于是先把 T2 拼了特殊性质得到 75 分。

然后回到 T3，想着我再不会这玩意就该倒闭了，于是开始观察样例，思考答案为 2^k 有什么用，通过观察样例 1 发现两条路径有交就会形成限制，然后观察样例 2 发现限制就是在并查集上给交路径的两个端点连边，想了想感觉很有道理，直接开写，写完就过了 56 分。

当时一算，感觉 231 也还行，不过先看看能不能更高再说，这个时候只有 1.5h 了，先发现 T3 的 B 性质直接做就可以做到 O(n\log^2n)，花了半个小时写了这 24 分，然后回去看 T2。

然后我突然发现我之前写的东西怎么可以前缀和优化？这下糖丸了，于是直接上前缀和做到了 O(n^2\log n)，中途是一些比较惊险的卡常，最后在最后五分钟卡进了 90 分，过不了是因为空间需要开 21 个 n^2 的 int 数组/cf。

出来一问，发现全是 280，顿时感觉自己要垫底了，不过后来发现并没有那么多，队线大概在 256 左右吧，那其实还行，不过仔细一想，去年 Day1 240+，Day2 爆了的人并不少，还是挺紧张的。

Day 1.5

NOI 典中典之走一个上午的路。

晚上只写了一个题，和教练继续去下面随机游走，心态 ++。

晚上睡眠还行，比 Day1 更紧张。

Day 2

开题了，感觉 T1 是个结论题，T2 不知道是啥东西，不过我好像不太会这种玩意，T3 好像是 ds，微距了。

那当然先做 T1，做了 20min 发现了结论，写了个暴力过了 55，然后 20min 写了个线段树，注意了一下精细实现，40min 的时候过了。

然后开 T2，先往各个方向想了一下都不知道怎么做，然后感觉这个 B 性质看上去非常奇怪，不知道干啥用的，这个时候感觉脑子不是很好使了，一直在想一些杂七杂八的事情，过了可能有一个小时才想到容斥感觉可以做，然后进一步发现可以用除法做容斥，那么 B 性质就有用了。不过这个时候我只会 3^nn 的 B 性质，感觉根本没啥分啊。

尝试优化，不会，尝试扩展，不会，到了 3h 的时候我感觉这样要爆了，就直接写了 8^n 的暴力和 3^nn 的 B 性质，这东西只有 40 分，对我甚至没有发现暴力可以做 4^n。

已经 3.5h 了，非常红温，开 T3，发现单次询问 O(n\log n) 有 35 分，准备先做这个，做了一下发现可以奇偶分类，然后枚举一个答案，对后面维护一段前缀至多进行多少次操作（由 0 数量决定），以及至少进行多少次操作（由 1 数量决定），然后如果所有位置都满足 l\leq r 就是对的。

赛后听 wmh 说这东西可以用差分约束理解，感觉很有道理。

写了个 O(qn^2)，大样例过了，一开始以为不能二分，后来发现想的那个 hack 其实也是可以二分的，然后加了个二分过了 35 分，这个时候只有 50 分钟了。

不过这个时候我认为 T2 是很难的题，应该不会有很多人过，不过事实证明大家还是太恐怖了。

然后我看了看 T3 庞大的部分分表格，感觉数据随机比较有说法，把小数据判掉，然后直接无视 3 那个限制是不是比较对啊？

没时间了，只能写这个，需要写一个线段树，好在细节不多，大概 20min 写完了，一测发现 sample 5,6 都过了，不过交上去只过了 AC 性质，没过 AD 性质？？？

不是哥们 AD 不是纯随吗，这都能不过的？？？

有点红温，只有 25 min 了，不过我突然想到，3 的限制本质就是可以选反向的点，只不过会额外增加 \lceil \frac{i-j}{3} \rceil 的代价，直接用线段树维护 \mod 3 的答案就可以了！！！

wdf 我少了一整个题的分？？？

这个时候感觉大脑已经一片空白了，我觉得把细节讨论清楚之后就用颤抖的双手给线段树加维护的信息，我不知道我写的对不对，但是我知道如果不对那肯定没时间调了。

最后 5min 的时候，我通过了小样例，测第二个样例，没有 diff 的勇气，肉眼对照一下前几行，没看出问题，提交 selfeval，在漫长如一个世纪的等待后，看到了 100 分！

我瘫坐在座位上，感觉心率非常高，算了一下总分，5+100+(100+90+80)+(100+40+100)=615，这没道理进不了啊。

最后玩了一下 tetris（。

体验了一把悬崖边上的感觉，太哈人了，不过当时我认为大家都是过 T3 没过 T2。

出场的时候感觉路都走不稳了，问了一下大家，yj 把 T2 过了 100+100+40，zwh 和 ljw 都是 100+68+35，我觉得队线应该也就 200 左右，不过 czj 和 szh 好像有点寄，szh 好像 T3 暴力调出来就有了/ll，cwtq 和 lsh 好像也有点寄，祝好！

然后中午在群里讨论，发现 T3 好像没有过很多人，原因好像是大家都写的贪心而不是直接描述限制或者差分约束（。

然后发现 T2 过了一万个人？？？顿时感觉冷汗直冒，这要是最后没调出来，555 肯定是寄了。

运气真好啊，感觉下午人都是旷的，直到查分，才知道 T3 的 std 是直接维护贪心选的位置，本来是防 ak 的，只不过让我钻了空子（。

最后我们学校进了 4 个，也算是还行的结局了吧。