本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-16 17:41:51

记录

ABC 正常，D 猜结论过了？E 用的笛卡尔树不太会，再说。

题解

A. Split the Multiset

注意到每次操作最多把数增加 $(k-1)$ 个，那么由 $1$ 个变为 $n$ 个需要的最少次数为 $\lfloor\frac{n-1}{k-1}\rfloor$。

B. Make Majority

发现可以把一段 $0$ 变为只剩一个，然后判断 $01$ 个数大小即可，只有 $1$ 的个数严格大于 $0$ 时可以最终变成 $1$。

C. Increasing Sequence with Fixed OR

先把给的数转成二进制，只需要考虑为 $1$ 的 $k$ 个位。根据题意，相邻的两个数不能有一位两者都为 $0$。同时贪心地想最大数一定为 $n$。倒着填时每次都要符合条件且尽可能大，那么每次都只去掉一个 $1$ 即可，这样的 $k+1$ 个数一定最优。

D. The Omnipotent Monster Killer

发现如果有次数上界 $k$，那么直接树形 DP 设 $f_{u,i}$ 表示 $u$ 子树内 $u$ 第 $i$ 轮删的最小花费，$f_{u,i}=ia_u+\sum \min_{j\ne i}f_{v,j}$ 直接转即可。问题在 $k$ 最大能取到多少。

最初感觉取到 $3$ 即可，但是挂了。考虑如果原树 $n$ 个点需要 $k$ 次删完，那么给每个点都连上一个极大值点，也就是加上 $n$ 个点就能让其多一次操作。所以操作数上界为 $\log n$。正式证明我不太会，只会感性理解。