题解：CF1725H Hot Black Hot White

FiraCode · 2024-08-16 19:37:34 · 题解

考虑将 a 和 b 拼起来其实就是 a \times 10^k + b，k 是多少不重要，因为在模 3 的意义下，10^k 恒等于 1。

所以原式就变成了 (a_i + a_j)^2 + a_i \times a_j。

然后由于在模 3 意义下，a_i 只有 3 钟取值。

于是把他们一一列举出来：

我们发现对于 Z=0，那么只要保证所有的 0 都在一组内即可。

设 cnt_i 表示 i 的出现次数。

那么只要 cnt_0 \le \frac n2 即可。

否则对于 Z=2，只要让 1,2 在同一组即可。

也就是 cnt_1 + cnt_2 \le \frac n2。

又由于 cnt_0 + cnt_1 + cnt_2 = n，所以上面那两个式子至少有一个成立，所以不会无解。

#include <bits/stdc++.h>

using namespace std;

int n;
int a[100010];
bool st[100010];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    int cnt = 0;
    for (int i = 1; i <= n; ++i) {
        if (a[i] % 3 == 0)
            st[i] = true, ++cnt;
    }

    if (cnt > n / 2) {
        memset(st, false, sizeof(st));
        cnt = 0;

        for (int i = 1; i <= n; ++i)
            if (a[i] % 3 == 1 || a[i] % 3 == 2) {
                ++cnt;
                st[i] = true;
            }

        for (int i = 1; i <= n; ++i) if (!st[i] && cnt < n / 2) {
            ++cnt;
            st[i] = true;
        }

        puts("2");
        for (int i = 1; i <= n; ++i) printf("%d", st[i]);
        return 0;
    }

    for (int i = 1; i <= n; ++i)
        if (!st[i] && cnt < n / 2) {
            ++cnt;
            st[i] = true;
        }

    puts("0");
    for (int i = 1; i <= n; ++i) printf("%d", st[i]);

    return 0;
}