NOIP2025游记

· · 生活·游记

好消息：请神请到 littleone 了。

坏消息：请到 NOIP2024 时候的 littleone 了。

考前又没睡好。

开题，贪心，组合，dp，ds。怎么跟去年一模一样。

先把 T1T2 秒了吧。

诶我怎么秒不掉 T1，冷静想想。嗯对只有一个物品会选超过两次。然后怎么做啊？有点急了。哦其实可以枚举选了几个 x。

看看 T2，刻画一下条件，好像就是贪到最后可以用 w=2 换掉最后面两个 w=1，形如 a_y+a_z<a_x，好复杂，这计个毛线。枚举 x,y 好像可以，随便组合一下变成 O(n^3)。

把 T1 写了，再写个 T2 的 O(n^3)，对了。直接范德蒙德卷积。我去最后一个样例挂了，弱智吧。哦组合数要预处理到 2n。

10:13，优势在我，估计 T2 不存在简单做法。

T3 是不是状态只记 mex 就能转移了来着，不对空闲点并不等于 sz-mex。那多记一维，有点唐。这个转移形式是不是很特别，第二维是取 max。呃，我会延迟贡献，记 dp_{u,i,j} 表示 u 子树 mex 每 +1 对答案贡献 j，且有 k 个空闲点，好像还是不能 O(nm^2)，但是很有前途啊！

11:00 码完，稍微有点急。看眼能得多少，48，有点输。诶是不是第二维构成一次函数？？？哦不对，那肯定是凸的吧。嗯样例 12 确实是凸的。

闵和一下？写了个优先队列 dsu，写到一半发现忘记存刚刚的 dp 了，亡羊补牢。草启发式合并根本没有降低复杂度，写 vector。草，好难调。

怎么就剩一个小时了，一定要留 50 min 给 T4。
一定要留 40 min 给 T4。
一定要留 35 min 给 T4。

样例 3 的凸性 assertion failed。

？

密码。不要爆零。把之前的版本拼上去数据点分治一下。

我就剩 25min 做 T4 了。

一开始的预期是 O(n^2+qn) 和 B 性质。想了 10 min 没想到任何平凡的做法，用仅存的理智写了 B 性质的 15 分。还剩 2min，写不完 st 表了。

[0,100]+100+48+15=263。

upd：T1 没判 sum>m，挂没了。

出来发现 fanglong 还没我高，难绷了。

好像认识的 BJOIer 里面没人过 T3T4。T2 的通过时间也并不算晚。早知道，不，其实即使不知道这些，我也不应该在认真思考 T4 的不平凡部分分之前，去写期望多获得 eps 分数的 T3 的凸优化。

一周前还在坚信「我现在已经不存在任何策略问题」的我，看到自己如此狼狈地走出考场的样子，心里会怎么想呢。

之后还有很长的路要走。