Codeforces Round 958 (Div. 2)

最自闭的一集。

tbh 赛前一整天心理状态都不太好，压力也很大。稍微甩个锅吧。

出题人：I failed to find a Div2-A level proof. If you have a simpler proof please share it in the comments.

比赛链接

Problems	AC
A. Split the Multiset	○
B. Make Majority	○
C. Increasing Sequence with Fixed OR	○
D. The Omnipotent Monster Killer	⊕
E. Range Minimum Sum	⊕
F. Heartbeat

A

你有一个 multiset $S$，初始时集合中只包含一个正整数 $n$，即 $S={n}$。另外，给定一个正整数 $k$。

在每次操作中，你可以选择 $S$ 中的任意一个正整数 $u$，从 $S$ 中移除一个 $u$，然后向 $S$ 中插入至多 $k$ 个正整数，使得插入的所有整数之和等于 $u$。

找到使得 $S$ 包含 $n$ 个 $1$ 的最小操作次数。

想象一下，把一开始那个 $n$ 看成是 $n$ 个 $1$ 构成的一条链，有 $n - 1$ 条边。

你每次操作相当于是断开 $k - 1$ 条边。

所以答案自然是

$$
\lceil \frac{n-1}{k-1}\rceil
$$

Code

B

Code

C 二进制

给定一个正整数 $n$。找到满足以下条件的最长正整数序列 $a=[a_1,a_2,\ldots,a_k]$，并打印这个序列：

• 对于所有 $1 \leq i \leq k$，满足 $a_i \leq n$。
• 序列 $a$ 是严格递增的，即对于所有 $2 \leq i \leq k$，有 $a_i > a_{i-1}$。
• 对于所有 $2 \leq i \leq k$，满足 $a_i ,|, a_{i-1} = n$，其中 $|$ 表示按位或运算。

做到 C 题的时候已经是究极降至了，构造题 spj 输出和样例不一样想了半天为什么。。。。

首先，我们把 n 用二进制表示，例如 23 是 10111。

对于 n 里面 0 的那些位，是不用管的，因为那些位肯定一直都是 0。

假设 n 在二进制下最高位是 k。那么 $a_1$ 的第 k 位肯定是 0，且后面的数的第 k 位肯定是 1。那么问题就变成了一个子问题。

Code

D 树形 DP

你，作为怪物杀手，想要消灭一组生活在一棵有 $n$ 个顶点的树上的怪物。第 $i$ 个顶点上有一个攻击力为 $a_i$ 的怪物。你打算进行 $10^{100}$ 轮战斗。

每一轮战斗的流程如下：

1. 所有存活的怪物都会攻击你。你的健康值会减少等于所有存活怪物攻击力之和的量。
2. 你可以选择一些（可能是全部或者一些）怪物来杀死。一旦被杀死，这些怪物将不会在未来的战斗中再次攻击。

有一个限制：在一轮战斗中，你不能同时杀死两个直接相连的怪物。

如果你以最优方式选择要攻击的怪物，那么在所有轮战斗结束后，你可以达到的健康值减少的最小值是多少？

有一个想法是这个轮数不会很多，大概是 log 量级的。

Why？参考下官方题解的证明，你可以这样想。设每个点的轮数是 $b_i$。

首先对于每个点来说，他的 $b_i$ 一定是直接相邻点的 mex 对吧。

那么假如 点 u 的 $b_u = x$ 是所有节点里面最大的，我们将 u 看作一棵树的根。他必须要有下家 1 ~ x - 1。令 $f(x)$ 表示能满足这个条件所需的最少节点数，那么有 $ f(1)=1,\ f(x)\ge 1+\sum_{1\le i<x}f(i)\to f(x)\ge 2^{x-1}$

也就是 $n \ge 2^{x - 1}$，即最大的数不超过 logn + 1。

剩下的问题其实相当于一个填数问题，每个点不能和相邻的点填一样的。

$$f_{u, i} = i\times a_{u} + \sum_{v\in \operatorname{son}(u)} \min_{j\not= i} f_{v, j}$$

可以前后缀最值做到 $O(nm)$，但是本题直接转移 $O(nm^2)$ 已经足够通过。

Code

E 单调栈

对于长度为 $n$ 的数组 $[a_1, a_2, \ldots, a_n]$，定义 $f(a)$ 为所有子段中最小元素的和。具体地，

$$
f(a) = \sum_{l=1}^n \sum_{r=l}^n \min_{l \leq i \leq r} a_i.
$$

给定一个排列 $[a_1, a_2, \ldots, a_n]$。对于每个 $i$，独立解决以下问题：

• 从数组 $a$ 中删除 $a_i$，得到剩余的数组 $b = [a_1, a_2, \ldots, a_{i-1}, a_{i+1}, \ldots, a_n]$。
• 计算 $f(b)$。

假如不带删除操作的话是个典题，用单调栈可以 O(n) 求出每个 i 之前和之后第一个 < a[i] 的位置 l[i], r[i]。那么答案就是 $\sum{a_i \times (i - l_i) \times (r_i - i)}$

那么你想，对于一个 i 来说，假如我们现在要删掉 a[j]：

假如 1 <= j < l[i] or r[i] < j <= n，那么 a[i] 的贡献还是没变。

假如 l[i] < j < i，那么 a[i] 的贡献变成了 $a_i \times (i - l_i - 1) \times (r_i - i)$，因为左边可取的少了一个。对于 i < j < r[i]，类似。

假如 j = l[i] or j = r[i] 呢，那么就需要用到次小值，这个次小值其实在单调栈过程中是可以一起求出来的。

Code