P9575 题解（2023 激励计划评分 8）

Register_int · 2023-08-20 18:22:48 · 题解

先特判 2|n 的情况。可以直接 x=1 然后进行均分。

如果 x 是一个奇数，那么取 \gcd 后会将所有数都变成奇数。而由于 n 是奇数，这样做会导致无解。所以 x 必须为 2 的倍数。

此时，如果序列中仍有 \gcd(a_i,2)>1，则将所有数 /2，同时将 x/2，以此类推。并且，我们希望 x 不要包含多余奇数因子，因为乘上奇数因子后无法改变序列奇偶性。因此，选择 x=2^{k+1}，其中 k 是使 \min\gcd(a_i,2^k)\ge 2^k 的最大非负整数。

将 a_i 的所有元素与 2^{k+1} 取 \gcd 方便讨论。此时序列中只有 1 或 2。容易发现，如果有奇数个奇数，那么必定无解，原因显然。当存在偶数个奇数时，我们只要将两个 1 相加，构造出一个新的 2，就能使 1，2 的个数均为偶数，实现均分。

总时间复杂度 O(n)。

AC 代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 1e5 + 10;

int n, k, a[MAXN], x[2], y[2], cnt;

int main() {
    scanf("%d", &n), k = 20;
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]), k = min(k, __lg(a[i] & -a[i]));
    for (int i = 1; i <= n; i++) a[i] >>= k;
    if (~n & 1) {
        puts("1");
        for (int i = 1; i <= n; i++) putchar(i & 1 ? '1' : '0');
    } else {
        for (int i = 1; i <= n; i++) cnt += a[i] & 1;
        if (cnt & 1) return puts("-1"), 0;
        x[0] = y[0] = n - cnt >> 1, x[0]++;
        x[1] = y[1] = cnt >> 1; x[1]--, y[1]++;
        printf("%d\n", 2 << k);
        for (int i = 1; i <= n; i++) putchar(x[a[i] & 1] ? (x[a[i] & 1]--, '0') : '1');
    }
}