日记 - 伊埃斯的博客站

还是改不掉看到数数题和概期题就害怕的习惯。

火↗

不是所有的概期都要 dp

设能在 $k$ 时刻内点燃第 $i$ 棵树的区间是 $[l_i,r_i]$ ，那么显然，第 $i$ 棵树被点燃的概率是 $1 - \prod_{j = l_i}^{r_i}(1 - a_j)$ 。把这些都加上就是了，可以很容易的做到 $O(n^2)$ 。

观察到 $l_i$ 和 $r_i$ 都是单调递增的，于是直接双指针做到 $O(n)$ 。

注意处理 $a_i = 1$ 的情况，因为 $0$ 没有逆元。

捐赠↗

大样例一定要测

有显然的结论： $a$ 中取的个数加上 $b$ 中未取的个数等于 $b$ 的总数。我们考虑把求解“取最大的 $k$ 个 $b$ ”改成求解“取最小的 $cntb - k$ 个 $b$ ”。

使用一颗权值线段树维护 $a$ 和 $b$ ，我们在插入 $a$ 的时候正常插入，在插入 $b$ 的时候插入将要插入的树的相反数，答案就是 $sumb$ 减去权值线段树里最大的 $cntb$ 个数的和，时间复杂度 $O(m \log V)$ 。

但是大家都是 $O(m \log^2 V)$ 过的。。。出题人紧急加了一组 hack。。。

染色↗

我们有朴素的 dp 方程。因为如果一颗子树内还没有染完色，那么剩下的叶子节点的 $c_u$ 一定相同。所以我们可以设 $dp_{u,x}$ 表示 $u$ 的子树内还没有染完色，还需要一个染色为 $x$ 的祖先的方案数。而 $dp_{u,0}$ 表示这个子树已经染完色了，不用再染了。

转移方程如下：

\begin{aligned} dp_{u,x} & = \prod_{v \in son_u}(dp_{v,0} + dp_{v,0}) - \prod_{v \in son_u}dp_{v,0} \\ dp_{u,0} & = (m + 1)\prod_{v \in son_u}dp_{v,0} + \sum_{i = 1}^{m}dp_{u,i} \end{aligned}

也是很好理解啊。边界就是对于每个叶子： $dp_{u,0} = dp_{u,c_u} = 1$ 。这个转移方程可以很容易的做到 $O(n^2)$ ，考虑如何优化。

钱神讲了一个神秘的优化方法：重剖优化 dp。我们每次先处理 $u$ 的重儿子，让 $dp_u$ 直接继承 $dp_{son_u}$ 的值。然后每次暴力合并剩下的轻儿子。

但是合并的时候有许多的细节。我们看到， $dp_{v,0}$ 要对 $\forall x \in [1,m] \ dp_{u,x}$ 做出贡献，但是如果每次暴力让 $dp_{u,x}$ 去乘上每个 $dp_{v,0}$ 的话，时间复杂度原地退化。所以我们对于每个 $u$ 记录一个 $tag_u$ ，表示这个 $u$ 里的每个 $dp_{u,x}$ 都要乘上一个 $tag_u$ 。当然这个 $tag_u$ 也是直接从重儿子继承的啊。维护 $tag_u$ 只需要在每次转移 $v$ 的时候，让 $tag_u$ 乘上 $dp_{v,0} \times tag_v$ 就是了。

时间复杂度 $O(n \log n)$ ，因为重链只剖的出来 $O(\log n)$ 层。

后日谈

什么时候能看到计数题和概期题不害怕呢？

Thanks for reading!

日记

周三 10月 15 2025

725 字 · 3 分钟

life 日记