【比赛记录】CFR958（Div.2）

· · 个人记录

记录

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。正式证明我不太会，只会感性理解。