CF2160

约 572 字大约 2 分钟

2025-10-16

A

题意

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

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

题意

有未知序列 $\{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}\}$ ，可以任选一个其他元素。

题意

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

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

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

题意

有长度为 $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$ $i = 1, \dots, 2 n$ ：
- 若 $Q(S \cup \{i\}) = q \ne 0$ ，则 $a_i \gets q$ ，并把 $a_i$ 加入 $T$ ；
- 否则，把 $a_i$ 加入 $S$ 。
对于 $i \in S$ $i \in S$ ：
- $a_i \gets Q(T \cup \{i\})$ 。

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

版权归属：Phantom-Bird