NOI2025 游记

· · 生活·游记

省流：D1T2 爆了。

这篇文章憋了很久才写，但是最终效果可能还是很烂，见谅。

Day -？

高强度模拟赛，被 Milmon 偏序了。（正常现象）

UNR Day 1

开场给 T1 猜了个结论，对着大样例缝缝补补，一直不过红温了，直接跳了（~2h）。

T2 感觉见过类似的，试图写一个（复杂度不对的）暴力维护，写了好多k，没过样例。

此时已经三小时多了，只有 T1 的 10 分。直接回去重写了一遍 T1，很快过了，然后写 T2 56 分，然后 T3 不会非指数级的做法，就回去调 T2,最后能过样例，但是 pre 莫名在很小的点 RE 了，不知道咋调，开摆。

出场发现整个机房没一个过 T2 的，无敌了。

晚上把 T2 过了，研究了好久 Enucai 的 T3，发现 jbw n=6 拍挂了，憋笑。

UNR Day 2

开场不会 T1，先打了个 a=0 的表，找了半天规律，终于有 60 了，然后对式子编了个 dp，发现可以扩展，2h 才过。

然后 T2 是交互，先跳了，T3 啥都不会，打了个 4 分，代码验证后发现没有决策单调性，寄！

想了好久 T2，大概还有一个半小时的时候会了一个归并排序+二进制分组的 2log 做法，开冲！！！最后因为莫名 RE 没调出来。赛后 1min 发现是没 return ans /qd 再加上把单组询问大于一亿的拆开就有七十多了，哈哈。

最后下位银。D2T2 70+ 就有前 50 了，难过。

Day 0

上午准备了一会笔试，感觉随便 AK 了。

下午去报道，没啥认识的人。去了 2202（希望没记错），感觉人太多了，没多久就回寝了。最后好像也没干啥。

Day 0.5

上午去听开幕式，确实听笑了。

下午去试机，为啥篮球馆这么热？？？/tuu

可能被拍了一些神秘照片。

选座位的时候 wmh 缠着，选了我旁边的位置。

机试啥也没干，笔试 3min ak 了，剩下的时间趴着。

发现 wmh 成功 99，大为震撼。

为啥要把选手关起来？？？

Hunster 在三分线用矿泉水瓶投（高的）篮筐，结果水瓶在篮筐上立起来了/jy

发现原来那题和题库里不一样。

晚上好像也啥也没干。

Day 1

进场，先看了题。T2 没看懂，T3 感觉很可做，随便画了画，不会做。

先做 T1，首先根据 APIO2024 T2 套路地算边的最短路，然后每个点维护出边最小值，更新是一个 s_r-s_l 的形式，可以用 Segment Tree Beats 维护区间取 min，写写写，小调一手，九点多通过了 pretest，此时认为优势在我。（flag）

然后做 T2，发现这个形式怎么这么像之前模拟赛场切的一道题，回忆一下做法，记得是先把 -min 改成 -1，然后就有一个 O(nV) 的 dp，注意到转移形如 reverse 后取前缀 max，所以连续段很少，只有 O(1) 段，然后就可以做了。回到这一题，感觉至少第一问是可以做的，冲冲冲，调了好久，一直过不去大样例，瞪眼取了一个子段后发现结论是错的，原因是那道题性质的证明用了无权值。这时已经十点半了，有点慌，赶紧跳了。

T3 观察了一下样例，发现怎么都是 2 的次幂？观察大样例发现真是，然后就嗯猜次幂上是啥。先猜了子树内有小于等于一个只出现一次的数，没过样例。然后就换一个方向猜。考虑枚举两次操作，若有相同的 LCA，那么把左边两个缩等价类，右边两个缩等价类。发现能过 A 性质。剩下在补上一个样例形状把两个深度深的点缩等价类，就对完了。写了个倍增 LCA，获得了 56 分。仔细思考，发现可以枚举要合并的点，查矩形内有没有点，可以树套树，有 80 分。经过思考决定写。12 点左右获得了 80 分。

回来做 T2，先拼一点暴力。写了 A 性质，写阶乘的时候发现第二问读错了，那这不是要找一种不重不漏的刻画吗？？？完全不会。想了想，发现 A 性质有 poly 的记搜做法，写了，调了半天，多了 8 分。此时只剩十多分钟了，想了一会，隐约感受到了正解的刻画，但是被相邻 -1 的条件限制了，不好写。最后也没有写更多分。

出场，发现 Hunster 和 wxy 都过了 T2，但是 T3 一个 8 一个 0，fsz 280，zxx 也是没过 T2。看了会群发现 T2 是人均题，那大众分不是 280 了？？？

为啥查分还要把选手关起来？？？

群里有人说 60+ 280，我们都不信。但是晚上教练打电话说正式选手至少 40+ 280，那没救了。只能寄希望于 Day 2 区分度高一点了。

晚上又啥也没干。

Day 1.5

为啥有教官啊？

是谁因为水果忍者掉队，还是我用 QQ 叫回来的，最后被鞭尸一整场/cf/cf/cf

夜宵去拿了父母取的外卖，怎么寝室里这么多人啊？

晚上睡前写了个题，点进题解发现 fsz 写过题解。

Day 2

开场看题，T2 题面怎么和 D1T2 这么像/yun，T3 怎么看上去就这么难？？？

做 T1，想了想就会了，半小时过了。

做 T2，首先套路地记 F(S,T) 表示两个集合的 and 分别为 S，T 的方案数，然后记 G(S,T) 表示 and 至少为 S，T 的方案数，然后子集反演。最开始把系数写成了 popcount+1 ，一直不会做，写了个暴力发现好像系数是 2^{popcount(S\cap T)}。发现 G(S,T)=f(S)*f(T)*g(S\cup T)，但是 g 需要 1+a_i 的逆元，这下看懂 B 性质了。上了个厕所，回来很快把 B 性质过了。然后想了想，感觉可以用模数不为质数的技巧记录 0 的个数，因为肯定非负所以正确性有保证，写完在 10:17 过了 pretest。

然后做 T3，想了半天贪心都不会做，最后写了个 dp。发现有值的一定是区间，用左右 O(1) 个点去更新就可以大常数 O(n) 了。观察大样例发现差的不是很多，于是写了在上一次答案附近倍增，写完有了 35。感觉 E 性质可以分块，复杂度好像是 O(n\sqrt{45n}) 开冲！写一半发现还要记长度，那就还要多个 \sqrt{45}，硬着头皮写完调完，发现常数冲天，没救了。最后遗憾离场。

听好几个 FJ 省队讨论，好像他们都没上 200？那可能还有救？

Hunster 不会 T2，但是会 T3 没写完，有点寄。fsz 245。

看群里的分数线越涨越高，最终到达 571，没救了。这个金牌究竟是谁在拿？？？

【数据删除】

晚上去了篝火晚会，前面一直在 run，导致去小卖部买了好多水。

后面好像又点了外卖，三人寝有好多人。

晚上没看群，错过了一些东西。

【数据删除】

Day 2.5

优质睡眠。

看了我与 NOI，被盐酸科普了椅子，有点忍俊不禁。

中午【数据删除】，赶在闭幕式前吃完了外卖。

下午闭幕式，快被热死了/fn/fn/fn

和我比较熟的除了 fsz 和 wmh 全寄了，是不是我给你们上了巨大 debuff/kel/ng

晚上跑路了。

没有人找我换徽章，果然我是不知名选手吗/ng

假如没做过那题，结局会不会不同呢？