模拟赛 16 题解

二分+dp+单调栈+树链剖分+贪心+并查集

A.软件

显然，答案具有单调性，所以我们可以采用二分。

对于给定的时间 $t$，判定可以dp。

设 $f[i][j]$ 表示前 $i$ 个人中，已经加工了 $j$ 个第一个软件的模块，加工的第二个软件模块的最大值。

不难发现我们可以把一个人的工作划分成两段：第一段加工软件一，第二段加工软件二。

转移时可以枚举第 $i$ 个人加工的第一个软件的模块数，那么剩下的时间它都在加工第二个软件。即：

$f[i][j]=\max_{k\in[0,j]}(f[i-1][j-k]+(t-k\times d_1)/d_2)$

注意 $k$ 枚举的上界不能超过 $\frac n {d_1}$。

判定 $f[n][m]$ 是否 $\geqslant m$ 即可。

B.最大后缀值个数

从根到每个节点的路径上维护一个单调栈，不难发现答案就是到每个节点的单调栈元素个数。

到每个点插入的时候要二分，不能暴力弹栈。

可以类似于CSP2019d1t2的做法，回溯的时候撤销操作。

注意不要清空加入元素的位置，即使是栈顶！！！

可以采用swap的方式。

C.树

先推一下式子：

$dep_u+dep_v-2\times dep_{lca}\geqslant tim_v-tim_u$

那么可以移项，变成一边只和 $u$ 或 $v$ 相关。

$dep_u+tim_u-2\times dep_{lca}\geqslant tim_v-dep_v$

发现 $lca$ 都是在 $u$ 到根的链上，并且该式左边在链底取到最小值。

所以我们直接把 $dep_{lca}$ 替换成链底即可。

把式子挂在链上面，维护最小值，操作直接链修改链查询就好了。

D.魔塔

神仙贪心。

邻项交换法可证：按 $\frac{times}{d}$ 取是最优的。

我刚开始的想法是直接用堆，从根向下贪心，取完把它的儿子扔到堆里面。

经 $\text{Wankupi}$ 的指导，这个贪心确实是假的，因为一个节点的贡献不止它的权值，还要考虑它的子树。

换言之，它本身可能很劣，但他的子树很优，所以还是要先打它。

这启发我们把每个节点都先加入堆里面，每次取出权值最大的节点是先不打，而是把它的贡献加到他祖先上面作为新的权值。

我们同时再记录一个攻打标记，只有当取出的值有可以攻打的标记，我们才能去打，并加入它的儿子。

由于一个节点要贡献所有祖先，所以我们采用并查集来维护这个操作。