DOJ logoDOJ
题目
最近添加的题目收藏的题目Workbooks
分类DLC比赛小组团队讨论区
排名
解题数量排行榜连续解题排名DOJ Power 排行榜
评测状态
征题登录注册
DOJ logoDOJ

支持 OI 子任务计分、Elo 等级分和 Discord 账号绑定的社区在线评测系统。

题目
题目列表分类
社区
比赛排名讨论区公告举办外部比赛指南
账号
登录注册评测状态
政策
服务条款DLC 使用规则隐私政策API 文档语言运行环境比赛排名奖励评级与表现
© 2026 DOJ
保留所有权利
题解

一 二 三 2

返回题目

题解

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

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

设 ppp 是 222 的幂。由于 A≥CA\ge CA≥C,有 q≤pq\le pq≤p。令 λ=max⁡(0,C−g⌊,则最少操作次数为 。

Construction

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

Bound

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

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

Solution written by GPT5.6

)g=\gcd(N,S)
g=gcd(N,S)
p=Ngp=\dfrac Ngp=gN​
q=Sgq=\dfrac Sgq=gS​
q/pq/pq/p
222
ppp
222
q2⌋)\lambda=\max\left(0,C-g\left\lfloor\dfrac q2\right\rfloor\right)
λ=max(0,C−g⌊2q​⌋)
N−g+λN-g+\lambdaN−g+λ
,
1
,
2
2p−q,0,q2p-q,0,q2p−q,0,q
g−2λg-2\lambdag−2λ
ppp

若某个大小为 ppp 的组中有 ccc 个 222,则该组中 0,1,20,1,20,1,2 的数量必须分别为 p−q+cp-q+cp−q+c、q−2cq-2cq−2c、ccc。因此 0≤c≤⌊q/2⌋0\le c\le\lfloor q/2\rfloor0≤c≤⌊q/2⌋,并且所有大小为 ppp 的组中 ccc 的总和应为 C−λqC-\lambda qC−λq。由 λ\lambdaλ 的定义可知这样的分配总是存在。

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

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

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

  • 若 r<D/2r<D/2r<D/2,一对较小值恢复出一个 000 并留下一个较小值。一对较大值可以恢复出一个 111 并留下较大值,或恢复出一个 222 并留下较小值。
  • 若 r>D/2r>D/2r>D/2,一对较大值恢复出一个 222 并留下一个较大值。一对较小值可以恢复出一个 111 并留下较小值,或恢复出一个 000 并留下较大值。

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

p
ps1,ps2,…,pskps_1,ps_2,\ldots,ps_kps1​,ps2​,…,psk​
s1+s2+⋯+sk=gs_1+s_2+\cdots+s_k=gs1​+s2​+⋯+sk​=g

设第 iii 个连通分量中初始有 cic_ici​ 个 222。该分量的总和为 qsiqs_iqsi​,所以 ci≤⌊qsi2⌋c_i\le\left\lfloor\dfrac{qs_i}{2}\right\rfloorci​≤⌊2qsi​。由于 qqq 为奇数,

C≤∑i=1k⌊qsi2⌋=∑i=1k(si⌊q2⌋+⌊si2⌋)≤g⌊q2⌋+∑i=1k(si−1)=g⌊q2⌋+g−k.\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*}C​≤i=1∑k​⌊

因此 k≤g−λk\le g-\lambdak≤g−λ。形成一个大小为 sss 的连通分量至少需要 s−1s-1s−1 次操作,所以总操作次数至少为

N−k≥N−g+λN-k\ge N-g+\lambdaN−k≥N−g+λ

。

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