NOIP2025

· · 生活·游记

做了两个小时 T3 没做出来，晚节不保。

按照难度排序。

T1：注意到两个选了 \ge 2 个的可以一个减二一个加二不劣，所以一定是每种选不超过一个然后找性价比最高的每次选两个，然后排序乱做。

T4：首先如果确定了区间必须经过中点，那么对于一个给定的点，区间是否覆盖它只和区间左右端点里的一个有关，枚举这个端点单调队列即可。按 R 分块，那么合法区间一定不会跨过一整块。在相邻块的就是确定必须经过一点的问题。在同一块内的，再次按 L 分块，那么跨过一整块的区间必合法，经过相邻块的区间仍然用相同办法处理，一块内的区间必不合法。

T2：不合法的结构是一个和为 m-1 的前缀，紧接着一个 2，然后要求后面的第一个 1（可能不存在）加上前面的价格最小的 1 的价格之和小于这个 2 的价格。枚举这个 2 是谁，然后大力做。

T3：等价于对原树进行链剖分，然后每个点的贡献为它到根节点最长的连续重链长度。于是有 O(nm^2) DP 就是记当前重链长度以及历史最大重链长度。这是我考场写的东西。然后震撼发现如果子树的深度加上当前重链长度还不超过历史最大重链长度的话，那这个子树的答案可以直接出了。所以记录的两维之差是子树深度的，上长剖即可 O(nm)。