题解：CF2246D diss_quack and Array Game

C202301 · 2026-07-25 18:13:57 · 题解

好题。

考虑观察一下假设 Alice 初始操作已定时 Bob 怎么做最优。发现一定分成两个步骤：

• 假设全部数都是偶数。没得操作，直接全部除以 2。
• 有一个是奇数。将奇数对应位置放到第二个。那么除了该数字之外其他数字比如说 \texttt{101} 一定要一位一位删除，并且 1 对应的那一位还要多一次，比如 \texttt{101} 的最优操作过程就是 \texttt{101},\texttt{100},\texttt{10},\texttt{1},\texttt{0}。简单归纳可知操作次数是二进制位数加上 1 的个数减 1。

然后考虑 Alice 一开始怎么做。其实 Alice 可以直接枚举所有情况，并找寻最优解：考虑先枚举第一个步骤中的次数是多少，然后操作所有数使得满足这个条件。然后感性理解可以发现说将每一个数 a_i 表示成二进制，抛开结尾若干个 0（这个在第一阶段处理）我们 +1 的次数一定不是很多，因为事实上我们每一个数的贡献是 O(\log n) 的，我们 +1 事实上本质是减小 1 的个数，那么我们肯定不会加太多次。注意这里的分析一定基于不考虑结尾若干个 0，也就是我们枚举加多少时一定是加上 2^k 而不是 1。

直接暴力枚举复杂度 O(n \log^2 n)。参考实现：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int N = 200000;
ll n, a[N + 5], lg[N + 5];
ll calc2(int x) {return __builtin_popcount(x) + lg[x] + 1; }
ll lowbit(int x) { return x & (-x); }
void solve() {
  ll ans = 1000000000;
  cin >> n; for(int i = 1; i <= n; ++i) cin >> a[i];
  for(ll j = 0; j <= 20; ++j) { //枚举第一步骤操作次数
    ll tot = 0;
    for(ll i = 1; i <= n; ++i) {
      ll v, z = 1000000000;
      if(lowbit(a[i]) < (1 << j)) { //满足条件
        tot += (1ll << j) - a[i] % (1ll << j);
        v = a[i] + (1ll << j) - a[i] % (1ll << j);
      } else v = a[i];
      v /= (1 << j);
      for(ll k = 0; k <= 50; ++k) { //枚举加的次数
        z = min(z, calc2(v + k) + k * (1 << j));
      } //看实现可知加的不是 1
      tot += z;
    }
    ans = min(ans, tot + j);
  }
  cout << ans - n << endl; //由于事实上我计算时用的是 log(n)+1 也就是没有减 1 的版本，那么最终我们要减去 n
}
int main() {
  lg[1] = 0; for(int i = 2; i <= 200000; ++i) lg[i] = lg[i / 2] + 1;
  ios::sync_with_stdio(0), cin.tie(0);
  int t; cin >> t;
  while(t--) solve();
  return 0;
}