NOIP2025 游记

· · 生活·游记

我怎么是 SH-0001。

8:30 开考。

8:45 过 T1。

我草这个 T2 是啥玩意？T3T4 是啥玩意？谁家 NOIP 出这么难？推了一下发现 T2 只需要统计 121 状物，再推了一下发现 O(n^2) 随便做。但是式子推错调了一会，最终 9:30 通过。

T3 一开始想到几个基于记录子树 mex 的 dp 状态，但都没法低于 O(n^2m)。后来灵机一动发现这玩意相当于链剖分然后每个点选祖先当中最长链加贡献，这个就随手 O(nm^2) 了。写完 76 分跑去看 T4。

T4 这啥玩意？部分分看着有点像倍增分块但我也不会倍增分块啊？仔细想想原来 L>\frac{n}{2} 是保证中点一定在区间里面，这个可以分治维护，每次处理过中点的区间，结合 ST 表，复杂度 O(nq\log n)。

但正解应该是 O(nq) 啊，这咋办。写了一下 O(nq\log n) 发现直接过了大样例？啥玩意我草。不过检查了一下发现 query8 没卡满，自己手造极限数据就过不去了。

这个时候灵机一动想到设立一个阈值 B 暴力处理长度 \le B 的区间，这样就能解决 L 很小的情况。弄完之后复杂度依然带 \log，不过这次跑得更快，可以通过 L=1,R=n。

所以这玩意凭啥能过啊？

回来想 T3，对着式子瞪了一会发现关键状态非常少，剩下的类似一个延迟贡献，可以并查集维护。这样写完是 O(nm\log n) 的，但是并查集不太可能被卡。

这个时候剩下 1h 不到，在 Linux 上测完大样例然后开始玩 Emacs 小游戏。然后就结束了。

出来发现 T3 长剖就能做到平方，但我为啥没想明白呢。T4 做法直接套值域分块就可以去掉 \log，但我场上直接否定了这个做法，令人忍俊不禁。