题意简述

每次操作选择一个 $x$，将所有数 $a_i$ 变为 $|a_i - x|$。最多 $40$ 次操作，能否使数组全变为 $0$？如果可以，输出操作序列。

可行性判断

操作本质是对所有数同时减去 $x$ 并取绝对值。观察奇偶性：

• 若 $x$ 为偶数，则 $a_i$ 与 $|a_i - x|$ 同奇偶；
• 若 $x$ 为奇数，则奇偶性相反。

由此可得：若初始数组中同时存在奇数和偶数，则无论如何操作，奇数和偶数的存在性不会同时消失，而最终 $0$ 是偶数，因此不可能全变为 $0$。
反之，若初始数组全部同奇偶（全奇或全偶），则一定能在 $40$ 步内完成。

构造方法（全同奇偶）

1. 如果初始全为奇数，首先执行一次 $x = 1$。所有奇数减 $1$ 变成偶数（可能有 $0$ 出现）。此时数组全为偶数。
2. 现在数组全为偶数（或本来就是全偶）。重复以下操作，直到数组全 $0$：
   • 设当前数组最小值为 $m$，最大值为 $M$；
   • 若 $M = 0$，结束；
   • 否则，选择 $x = \left\lfloor \dfrac{m + M}{2} \right\rfloor$；
   • 将每个 $a_i$ 更新为 $|a_i - x|$。
3. 输出所有记录的 $x$。

正确性简述

• 当数组全同奇偶时，$m$ 和 $M$ 同奇偶，因此 $x$ 为整数。
• 每次操作后，新的最大值不会超过 $\lceil (M - m)/2 \rceil$，值域严格缩减。因此最多执行 $O(\log \max a_i) \approx 30$ 次操作即可将所有元素变为 $0$。
• 第一步可能额外增加一次操作，总次数 $\le 31$，远小于 $40$。

复杂度

每组数据需要在每次操作中遍历整个数组，操作次数 $\le 31$，总复杂度 $O(n \log \max a_i)$。所有数据 $n$ 之和 $\le 2 \times 10^5$，完全可行。

参考代码

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];

    // 判断奇偶性
    bool has_even = false, has_odd = false;
    for (int x : a) {
        if (x % 2 == 0) has_even = true;
        else has_odd = true;
    }
    if (has_even && has_odd) {
        cout << "-1\n";
        return;
    }

    vector<int> ops;
    // 如果全为奇数，先执行一次 x = 1
    if (has_odd) {
        ops.push_back(1);
        for (int &x : a) x = abs(x - 1);
    }

    // 不断取 (min+max)/2 直到全0
    while (true) {
        int mx = *max_element(a.begin(), a.end());
        if (mx == 0) break;
        int mn = *min_element(a.begin(), a.end());
        int x = (0LL + mn + mx) / 2; // 避免溢出
        ops.push_back(x);
        for (int &v : a) v = abs(v - x);
    }

    cout << ops.size() << "\n";
    if (!ops.empty()) {
        for (int i = 0; i < (int)ops.size(); ++i) {
            cout << ops[i] << " \n"[i == ops.size() - 1];
        }
    } else {
        cout << "\n"; // 空行
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}