NOIP 2025 游记

· · 生活·游记

开场依旧通读题面。

T1 怎么感觉有点难？想了一小会发现按照奇偶分下类就差不多能做了，那还行。T2 怎么感觉也有点难？想了一段时间发现不会做，那咋办。T3 这个东西复杂度怎么能跟深度扯上关系的？完全不懂。对 T4 没有一点感觉。今天题怎么这么难。

感觉 T1 不用急着写，先去想了一会 T2。试着对着策略进行了一些反悔，好像只有形如丢掉两个 w=1 换成 w=2 的策略才有用。那可能有点头绪了。

花了 10min 左右把 T1 打了，测完样例对着代码盯了一会就扔了。回来继续想 T2。试着将不合法方案在第一个 w=1 的物品处计数，好像就只有对当前价格和下一个 w=1 的物品位置有限制了，那是不是可以数了！不过细节可能有点多。

对着后面的题看了一会感觉不是很会，决定开始写 T2。写的时候发现细节错了一大车，不过好在都能修，对着 10 行左右的关键代码调了 1h 左右才过样例。造了组极限数据测了下速就扔了。

抬头发现已经 10：30 了，怎么前两题花了 2h。

开 T3。对着这个东西贡献延后计算一下好像有一个 O(n^4) 的背包，前缀和一下能 O(n^3)，但这不是和 m 完全没关系吗。

画了一些 m=2 的样例玩了一下，感觉这个东西的结构很树剖分，可以给每个点找一个 \operatorname{mex} 最大的儿子继承 \operatorname{mex} 信息。那弱化成给每个点钦定一个重儿子是不是也能求最大权值。考虑给定一个树剖分，每个点的贡献应该就是链深度历史 \max，那是不是记一下链深度和历史 \max 就能 O(nm^2) 了。

感觉这个分很够啊。想了一下不太会优化就把这个写了。突然发现好像写 n=4000,m=50 过不了 n=360。怎么没有 n=360 的大样例。

剩下大概 1.5h 给 T4。想了一段时间还是只会单调队列 O(R-L) 求单次答案，不过拼上 AB 性质好像有 40pts。写完这个大概还有 1h。

想起来 CSP 写到最后啥都没检查，于是决定先提前检查一下。盯了一圈发现 T1 没判 m\le sum 的情况，赶紧修了一下。

感觉 T4 获得更高分数的概率比 T3 高一些，剩下的时间还是在想 T4。模拟赛里好像有个题就是对着序列硬上分治之后就能做了，于是试了一下分治。好像转成后缀 chkmax 了，那是不是比较能做，这么牛的。直接开写，好像很快就写完了。测了一下最后一组大样例发现只跑了 2.3s 左右。把 L\le 32 的部分拿出来用 B 性质处理掉就跑进 2s 了。

把 T4 部分分整理了一下就没多少时间了，最后检查了一下就交卷了。

最后 100+100+76+95=371。