查看源代码：
CF2160.md

---
title: CF2160
createTime: 2025/10/16
categories:
    - IT
tags:
    - OI
---

## A

:::note 题意
给定多重集 $S$，将其划分为 $m$ 个多重集 $S_i$ 使得 $\operatorname{mex} S_i$ 对所有 $i$ 相等。求此时 $\operatorname{mex} S_i$ 的最小值。
:::

显然合法的分割的 $\operatorname{mex}$ 一定是 $\operatorname{mex} S$。

## B

:::note 题意
有未知序列 $\{a_i\}$，设 $f(l,r)$ 为 $\{a_l, \dots, a_r\}$ 的不同元素个数，  
给出 $b_r = \displaystyle\sum_{l=1}^{r} f(l,r)$，求 $\{a_i\}$。
:::

注意到

$$
f(l,r) - f(l,r-1) = [a_l \notin \{a_l, \dots, a_{r-1}\}] \in \{0,1\}
$$

以及

$$
f(l-1,r) - f(l-1,r-1) \le f(l,r) - f(l,r-1)
$$

设 $g(l,r) = f(l,r) - f(l,r-1)$，

$1$ 和 $0$ 的分界点 $L$ 上（即上式不取等时），

$$
a_r=a_{L-1}, a_r \notin \{a_L, \dots, a_{r-1}\} \qquad (L \ge 1)
$$

只需求出 $L$，即可求出 $a_r$。

我们知道，01-串中 $1$ 的个数为数列的和，即

$$
r-L+1 = \sum_{l=1}^{r} g(l,r)
$$

由于

$$
b_{r} - b_{r-1} = f(r,r) + \sum_{l=1}^{r-1} f(l,r) - f(l,r-1) = 1 + \sum_{l=1}^{r-1} g(l,r)
$$

整理可得

$$
\large a_r = a_{r - b_r + b_{r-1}} \qquad \normalsize (r - b_r + b_{r-1} \ne 0)
$$

$r - (b_r - b_{r-1}) = 0$ 代表 $a_r \notin \{a_1, \dots, a_{r-1}\}$，可以任选一个其他元素。

## C

:::note 题意
设 $\operatorname{rev}(x)$ 表示二进制反序，问是否存在 $x$ 使得 $x \oplus \operatorname{rev}(x) = n$？
:::

先不考虑前导零。显然 $n$ 必为回文数，且若有奇数位，则最中间的一位为 $0$。

前导零可以通过 $1 \oplus 1$ 得到，因此只需保证回文。把后面的所有 $0$ 删去，则由回文性质可以去掉前导零。

## D

:::note 题意
有长度为 $2n$ 的未知序列 $\{a_i\}$，$\forall x=1,\dots,n, \exists i \ne j, a_i = a_j = x$。

每次询问一个下标集合 $S$，返回 $\displaystyle\max_{\{i,j\} \in S, a_i=a_j} a_i$，若不存在 $\{i,j\} \in S, a_i=a_j$ 则返回 $0$。

用不超过 $3n$ 次询问求出 $\{a_i\}$。
:::

设 $Q(S)$ 为询问 $S$ 的答案，注意到若 $S$ 满足 $Q(S)=0$，且 $Q(S \cup \{i\}) \ne 0$，则 $a_i = Q(S \cup \{a\})$。

于是有如下策略：

- 初始 $S, T \gets \emptyset$。
- 对于 $i=1,\dots,2n$：
  - 若 $Q(S \cup \{i\}) = q \ne 0$，则 $a_i \gets q$，并把 $a_i$ 加入 $T$；
  - 否则，把 $a_i$ 加入 $S$。
- 对于 $i \in S$：
  - $a_i \gets Q(T \cup \{i\})$。

易证总询问次数为 $3n$。