NOI2025 游记

· · 生活·游记

day -\aleph_1

noip 348，省选 328，D。

day -\aleph_0

大战期末考，没一科写完的，我为什么要考啊/ll。总分 399，感觉要 <noi 了

day -6

unr 笔试，有三个题不会，97pts。

day -5

unr day1，但是我早上去抽了个血，所以 9 点才有电脑，就给自己 +5min 吧。

然后就是乱想，想了很久终于会判断 t1 的合法性了。然后构造有一点点码量，11 点的时候过了。

然后想 t2，发现首先 b_i 只会匹配向前向后第一个区间和为 0 的位置。然后就是每个点度数 \le2 的二分图选 k 个最大权匹配，并且这个图其实只有链。所以每条链跑一个反悔贪心即可。然后就是合并凸包，O(n\log n)。

然后写+调 2h 没调出来。然后赛后 1min 调出了。不管了，就当自己过了吧。

但事实是 100+4+0=104。甚至多拿了 4pts。如此成绩，如何 NOI？

day -4

unr day2。

不会 ABC。

在大约 2h 才发现 A 可以从大到小填数，设 f_{i,j} 表示目前最左边的是 i，a_i=j 的方案数。然后你发现只要 i 和当前填的数之间合法即可。可以做到 O(n^3)。一开始想的有点问题。最后在 3.5h 拿到了 90pts。感觉 100pts 不是不能考虑，但是跳了。

然后就是 B 10pts，C 4pts。B 我想的是先搞一个比较大的独立集出来，然后把剩下的数加进来 check 一遍，然后多 check 几次就能把边连完，但是感觉可能也是 n^2 的。C 分治完两边维护到 mid 的前 k 大/小应该可以有 O(k^3n\log^2n) 之类的东西？但是要写李超，还有依托分讨，还不一定对。所以 O(n^2k) 4pts 跑路。

最后是 90+10+4=104。如此成绩，如何 NOI？

day -2

学考，都不太容易。

day 0

抵达，舍友都是 gtyz 老哥。到达机场居然还有小点心，好吃。

然后摆了一天。

day 1

上午开幕式。dzd：美国制度比较好。

小品还可以，比之前的神秘歌舞好多了。然后就来了一个神秘舞蹈。

下午笔试，AK 了。写出了 traverse，没写完 edit。

怎么明早 7:10 集合啊？

day 2

半夜醒了 3 次，其中包括被子太厚热醒了。

上来发现 A 是绿题，只要把状态设成边就行，30min 过了。

发现 B 一段 0 是从中间往两边操作，第一问容易 O(n^4)，然后把分段改成从两边往中间操作的方式就可以 O(n^2) 了，第二问避免算重的方法是固定左边开始没有和为 0 的段。但是我不知道为什么做了 3 个多小时。

C 想了很多东西也只会 8 分。最后半小时发现答案好像是 2 的幂。然后题面特意保证了有解。那是不是什么联通块个数状物啊！想了想好像还真是这么回事。然后写了个 n 方，获得了 56pts。然后发现我写了 n 方 lca，改成正常一点的就可以过完全二叉树了。但是没时间了，痛失 24pts。

最后没挂，100+100+56=256。

怎么这么多 280，我为什么要写 O(n^2)-O(1) lca???

下午四人东操出了首个全局 S+（S S S+ S S+)，但还是吃二了。

day3

神秘社会活动。但是很【数据删除】。但凡让我自己参观呢。

晚上终于打到羽毛球了，感谢借我拍子的好心人。

day4

发现自己好像一个题都不会。

发现 A 连续 2 个 1 很有用。

发现找到最开头的长度 >1 的 1 的连续段就差不多做完了。再判一下 ans=0。

发现 B 有点难，仔细想了一会发现是这么干。

一下就写完了，这时候是 10:20，2.5h 大战 C，优势在我

吗？

你发现你应该尽可能先用进攻去填防守，那你只要求出目前最需要进攻的前缀要进攻几次，后缀和完求一下最值即可。这样是 O(nq\log n) 的，但是跑得快，40pts。

这个我怎么能写+调 2h 的？然后就没时间了，下播。后面发现这个特殊性质 AD 是不是后缀 min 的位置期望下可能是是 n-O(\sqrt{n}) 的（因为小值域），然后直接模拟？不知道对不对。

最后是 100+100+40=240。

一共 0+100+100+100+56+100+100+40=596，砍下 D 类 Au。GD 疑似有 11 个正式 Au 和 3 个 D 类 Au，能不能多给几个省队名额啊。

晚上又给我打到球了，感谢另外几个借我拍子的好心人。