NOIP2025 总结

· · 生活·游记

NOIP 2025 总结

场上

9:40 做完 T1, T2，想一些 T3 假性质，恍惚间已然 11:20，所写一并删去。

心有不甘，却不再会到 48 以上，决定写完就此结束 T3，至此 12:00 有余。

T4 没有想法，心态开始波动，坚持着继续拼暴力，拼到 40 分，最后五分钟回归平静。

挂分

可能是会挂的。

不能奢望不挂的。

这部分留到出分后。

考前心态（写于考前）

出乎意料的松弛，没有立 flag，似乎即将到来的是漫长的训练中平常的一天。

没有打模板，没有看做题记录，考前一天听了很多之前的歌，找人 duel 了四场，最后一场于晚十点结束。

这可能是之前立 flag 经历的提醒，但对比训练过程和此前成绩，没有理由比别人考得好，也就不尽是兴奋。

当然还有对同学们的祝福，希望他们能取得理想的成绩，留在热爱的 OI 道路上。

考后心态（闲话）

没破防，但晚上没找到人 duel。

题目质量很高，除去对结果的担忧还是享受着比赛的。

策略较为稳定，时间不够，发挥不出水平，只能说水平还没到位。

希望到了省选能有成为真正的高水平选手，发挥出彼时应有的水平。

相信还是有机会翻盘的。

训练

独立思考的时间应当进一步增加。

做题不能在舒适区徘徊啊，什么题都要做。

再难也要去研究，别觉得不会考，不会就问。

记住 u'r on a mission，别有时间就开摆。

Tree

设 u 点权 a_u，价值 b_u，你要最大化的即 \sum_u b_u。

考虑 a_u 的分配，设 x=\text{mex}_{v\in \text{sub}_u-\{u\}}a_v，按 a_u 分为取 x 和 >x 两种情况。两类点 b_u 都已经确定，而后者的存在是为了增加 u 某个祖先的 b_v，不妨放到对应祖先处确定具体值。

设 f_{u,i,j} 为子树 u 内已确定的 a_v 求 \text{mex} 为 i，j 个点未确定，此时最大价值，转移即枚举 b_u-\max_{v\in \text{son}_u}b_v。

不妨钦定某个 v 处取到 \max，这形成一个链剖，在这个结构上考虑 b_u 在 \max_vb_v 基础上每次 +1 的贡献，即对 u 到 \text{tp}_u 这条链上所有点 b 值 +1，其对总答案的贡献即链内深度（1-index），设之 d_u。

换言，初始 d_1=1，每个 u 恰选择一个重儿子 v 使 d_v=d_u+1，其余 d_v=1，最大化 \sum_u(\max_{v\in \text{anc}_u}d_v)。

设 f_{u,i} 表示: 钦定 u 为其所在重链的 tp，u 祖先链上的 d_{\max} 为 i，此时 u 子树的最大价值和。

为了处理更新 d_{\max} 的情况，再令 g_{u,i} 表示 u 为其所在重链中间一个点，祖先链 d_{\max} 在 u 处取到 i，子树价值。

每个深度开线段树做到 $O(nm\log n)$，长剖技巧做到 $O(nm)$，此处不再赘述。 另一个视角是想要更直观地刻画贡献给祖先的点的贡献，下将 $a_u=x$ 的点称作黑点，$a_u>x$ 称为白点。 发现黑点 $u$ 一定可以有黑点儿子，否则取子树黑点 $\text{mex}$ 最大的儿子 $v$，交换 $a_u,a_v$ 不劣，这样 $v$ 成为黑点。 将这个 $v$ 看作 $u$ 的重儿子，黑点内部形成链剖，此时白点 $u$ 所贡献即是其祖先中深度最小的黑点 $v$，否则将 $v$ 改成白点和 $u$ 贡献给同一个点不劣。 设 $f_{u,i}$ 为 $u$ 最深祖先黑点链内深度为 $i$ 时的子树 $u$ 的最大价值，这是为了处理首个黑点祖先在子树外的那些点，转移同样可以优化。 参考了 CommonAnts 的题解，感谢他耐心给我讲。 #### Query 固定询问 $(\text L,\text R)$，考虑分治 `solve(x, y)` 表示处理所有 $[x,y]$ 的长度在 $[\text L,\text R]$ 内的子区间的贡献。 处理跨过 $\text{mid}$ 的子区间，以对左半的贡献为例，枚举 $l$，单调队列维护 $r$，贡献给左半一个后缀的 $i$。 考虑一些复杂度分析，单个区间 $\mathcal O(\min(\text{len},\text R))$ 且 $\text{len}<\text L$ 无需做，即处理的区间在 $O(\frac{n}{\text L})$，做到 $O(n\frac{\text R}{\text L})$。 考虑将 $[\text{L},\text R]$ 划分为若干 $\frac{\text R'}{\text L'}=\mathcal O(1)$ 分别求解，这样区间的个数是 $\mathcal \Omega(\log n)$ 的，直接预处理所有 $[2^i,2^{i+1})$ 答案，将 $[\text L,\text R]$ 划分一个整段区间和 $\mathcal O(1)$ 散段，散段有 $\frac{\text{R}'}{\text L'}<2$，每个位置对整段做 ST 表即可。 复杂度 $O(n\log n\log \log n+nq)$。 --- 感谢 cxy 给我讲 T3。