# CF1406

3/5

• 多测要清空
• 对于序列贡献形如 $a_i-a_{i-1}$ 这类的序列区间操作，可以考虑维护差分数组
• 交互题对操作次数有限制的，可以先想想暴力怎么做，再推推性质使用分块等技巧削去无用的 / 可以合并的操作

# A

题意：

一个数列，要把它划分为两个集合 $A$ ， $B$ ，最大化 $\mathrm mex (A) +\mathrm mex(B)$

$$n,a_i\le 100$$

题解：

桶

# B

题意：

$n$ 个数中找 $5$ 个数使其乘积最大。

$$n\le 10^5$$

题解：

排序

答案只有可能为偶数个最小值乘其余的最大值

# C

题意：

一棵树，删一条边连一条边使得只有一个重心。

$$3\le n\le 3\times 10^5$$

题解:
最多两个重心，且相邻

把一个重心下面的叶子加到另一个重心上，就只有一个重心了。

# D

题意：

给出一个序列 $a$ ，构造两组序列 $b,c$ 使得 $b_i+c_i=a_i$ ，$b$ 单调不降， $c$ 单调不升，求最小的 $\max\{b_i,c_i\}$ ，区间加修改。

题解：

答案是 \max \

假设一开始 $a_i$ 是平的，那 $b_i=c_i$

观察到若 $a$ 凸起了，$c$ 若加了，则全局 $c$ 都要加 ，不如加 $b$

$b_n = b_1+(S=\sum \max\{0,a_i-a_{i-1}\})$

所以 $c_1+b_n = x+ a_1-x+S=a_1+S$

显然，两个相等时答案最小。

则最小答案 $a_1+S\over2$

对于区间修改，维护一个差分数组，看看左右端点的变化即可。

# E

题意：

交互题

一个 $1\to n$ 的集合，有一个关键数字

三种操作：

• 询问集合中 $x$ 的倍数有多少个； $1\le x$
• 询问集合中 $x$ 的倍数有多少个，并删去，关键数字不会被删； $2\le x$
• 回答

最多操作 $10000$ 次

题解：

考虑对于每个素因子，利用 $B + A$ 可判断 $x$ 是否存在这样一个因子，如果存在，就暴枚 $x^k$ 用 $A$ 看，然后乘进答案。

显然，$100000$ 以下的素数有 $9000$ 多个，这样是不行的

那么，对于 $\sqrt n$ 以下的素因子，可能出现大于 $1$ 次的幂，我们暴力处理，对于大于 $\sqrt n$ 的因子，最多出现一个幂，于是我们分块处理，使用 A 1 来看减去的数字，若减去的数字不等于块长，就在块内暴力处理，反正最多出现一个，所以操作复杂度是对的。