题解

一二三 2

回到问题

题解

将所有数都减去 $1$ ，于是初始值变为 $0,1,2$ 。若 $A<C$ ，对所有数作变换 $x\mapsto 2-x$ 即可，因此下文假设 $A\ge C$ 。

令 $N=A+B+C$ 、 $S=B+2C$ 、 $g = \gcd (N, S$ 、、。最终所有数必定等于整体平均值。无论进行多少次操作，每个数写成最简分数后其分母始终是的幂，因此若不是的幂则不可能完成。

设 $p$ 是 $2$ 的幂。由于 $A\ge C$ ，有 $q\le p$ 。令 $λ = \max (0, C - g ⌊$ ，则最少操作次数为。

Construction

当 $p>1$ 时， $q$ 为奇数。先构造 $\lambda$ 个大小为 $2p$ 的组，每组中 $0,1,2$ 的数量分别为。再将剩余元素分成个大小为的组。

Bound

若两个下标曾在同一次操作中被选中，就在它们之间连边得到图 $G$ ，设其连通分量数为 $k$ 。若某个连通分量的大小为 $s$ ，则该分量最终的总和 $sq/p$ 必须为整数，因此 $s$ 是 $p$ 的倍数。将各连通分量的大小写成，则。

总时间复杂度为 $O(N)$ 。

Solution written by GPT5.6

g = g cd (N, S)

p=\dfrac Ng

q=\dfrac Sg

q/p

2

p

2

λ = max (0, C - g ⌊ \frac{q}{2} ⌋)

N-g+\lambda

,

1

,

2

2p-q,0,q

g-2\lambda

p

若某个大小为 $p$ 的组中有 $c$ 个 $2$ ，则该组中 $0,1,2$ 的数量必须分别为 $p-q+c$ 、 $q-2c$ 、 $c$ 。因此 $0\le c\le\lfloor q/2\rfloor$ ，并且所有大小为 $p$ 的组中 $c$ 的总和应为 $C-\lambda q$ 。由 $\lambda$ 的定义可知这样的分配总是存在。

每个组都可以恰好用“组大小减 $1$ ”次操作变为相等。大小为 $p$ 的组由 $0,1,2$ 构成且总和为奇数。对于大小为 $2p$ 的组，将所有值除以 $2$ 后会得到总和为奇数的 $0,1$ 组。

考虑一个大小为 $D=2^k$ 、元素属于 $\{0,1,2\}$ 、总和为奇数 $q$ 的组。逆向构造操作。开始时，想象有 $D$ 个最终平均值 $q/D$ 。从两个相等的当前值 $x$ 中，固定其中一个位置为原始整数 $a\in\{0,1,2\}$ ，并将另一个位置逆向变为 $2x-a$ ，即可逆向恢复一次平均操作。

当活跃元素个数为 $D$ 时，令 $r=q\bmod D$ 。所有活跃元素的小数部分均为 $r/D$ ，因此只会出现 $r/D$ 和 $1+r/D$ 两种值。设较大值的个数为 $H$ ，并把相同类型的值两两配对。

若 $r<D/2$ ，一对较小值恢复出一个 $0$ 并留下一个较小值。一对较大值可以恢复出一个 $1$ 并留下较大值，或恢复出一个 $2$ 并留下较小值。
若 $r>D/2$ ，一对较大值恢复出一个 $2$ 并留下一个较大值。一对较小值可以恢复出一个 $1$ 并留下较小值，或恢复出一个 $0$ 并留下较大值。

下一层的活跃元素个数为 $D/2$ 。对于每个状态 $(D,H)$ ，之后能够恢复的未恢复 $2$ 的数量构成一个整数区间。当 $D=2$ 时，只有 $(H,c)=(0,0)$ 和 $(2,1)$ 两种状态。利用上述转移可以从较小的 $D$ 开始计算这些区间。使用前缀和后缀最小值、最大值，可以在 $O(D)$ 时间内处理一层，而所有层大小之和也是 $O(D)$ 。实际恢复时，只需选择一个使下一状态仍落在可行区间内的转移。最后将记录的逆向操作倒序，即可得到恰好 $D-1$ 次正向操作。

p

ps_1,ps_2,\ldots,ps_k

s_1+s_2+\cdots+s_k=g

设第 $i$ 个连通分量中初始有 $c_i$ 个 $2$ 。该分量的总和为 $qs_i$ ，所以 $c_i\le\left\lfloor\dfrac{qs_i}{2}\right\rfloor$ 。由于 $q$ 为奇数，

\begin{align*} C &\le \sum_{i=1}^k \left\lfloor \frac{qs_i}{2}\right\rfloor \\ &= \sum_{i=1}^k \left(s_i\left\lfloor\frac q2\right\rfloor+\left\lfloor\frac{s_i}{2}\right\rfloor\right) \\ &\le g\left\lfloor\frac q2\right\rfloor+\sum_{i=1}^k(s_i-1) \\ &= g\left\lfloor\frac q2\right\rfloor+g-k. \end{align*}

因此 $k\le g-\lambda$ 。形成一个大小为 $s$ 的连通分量至少需要 $s-1$ 次操作，所以总操作次数至少为

N-k\ge N-g+\lambda

。

⌋

2

qsi

⌋

=i=1∑k(si⌊2q⌋+⌊2si⌋)

≤g⌊2q⌋+i=1∑k(si−1)

=g⌊2q⌋+g−k.

一 二 三 2

题解

一二三 2