2023年板刷省选题记录

Day 1 3/13

昨天晚上没睡好，今天状态很差。晚上19:15开始做题，预计做两道。

19:40开始看第一题题解。没有想到任何关键点上，我是傻逼。接下来睡了一会。20:15开始写。

就写了一道，开颓，埋了。

联合省选2022 填树

给定一棵 (n) 个点的无根树，对每个点 (i) 给定一个区间 ([l_i, r_i])，求对于所有树上路径，如果将这个路径上每一个点填上其对应区间中的一个数，且最终所有数极差小于等于 (K)，那么共有多少种方案，以及这些方案中填上的数的总和。

数据范围：(1 le n le 200, 1 le l_i le r_i le 10^9, 1 le K le 10^9)。

可以说是我做的第二道拉格朗日插值优化DP题，就从第一步开始想歪了/kk/kk。

首先，如果已经确定路径上数的最小值，那么可以非常容易地计算出任何一个路径的权值和。具体地，暴力DP时间复杂度为 (Theta(n^2))，换根DP优化即可做到 (Theta(n))。则直接枚举最小值，总复杂度是 (Theta(nW))，其中 (W) 是值域。

接下来我们需要考虑把 (W) 优化成 (n)。这样想的直觉是，除了区间端点以外的其他值都很相似，并且不太重要。考虑最小值为 (L) 时，点 (i) 可以取的区间是 ([l_i, r_i] cap [L, L + K])，当 (L) 增加 1 时，如果它或者对应右端点没有触碰到某个 (l_i, r_i)，则方案总数可以表示为一堆一次函数相乘然后再相加，而第二问的方案总数可以表示为一堆二次函数相乘相加。这个东西次数是 (mathrm O(n)) 的，要计算区间和，则只要拉格朗日插值求出前缀和即可。

于是做完了。考虑在端点触碰到某些关键点的时候暴力重新算出下面 (mathrm O(n)) 个东西，剩下的部分用插值算一下，时间复杂度是 (mathrm O(n ^ 3))，随便过。

被卡常了，提示我们不要乱堆递归，这玩意可以直接转移而不用换根的两次dfs。