H. Hot Black Hot White - 题解

比赛与标签

比赛: COMPFEST 14 - Preliminary Online Mirror (Unrated, ICPC Rules, Teams Preferred) 标签: constructive algorithms, math 难度: *1800

喵~ 题目大意是什么呀？

主人Sama，你好呀！Chanek 博士给了我们一个好玩的任务喵~

我们有 N 颗魔法石（N 是一个偶数），每颗石头 i 都有一个能量值 A_i。我们的任务是把这些石头涂成两种颜色：一半涂成黑色，一半涂成白色。

涂完色后，我们要把它们放进一个魔法盒里。这个盒子有一个魔法系数 Z，Z 可以是 0, 1, 或 2。

两颗不同颜色的石头 i 和 j 会发生“反应”，变得非常危险，当且仅当它们满足这个条件： concat(A_i, A_j) × concat(A_j, A_i) + A_i × A_j ≡ Z (mod 3) 这里的 concat(x, y) 就是把数字 y 的十进制表示拼在数字 x 的后面，比如 concat(10, 24) 就是 1024。

我们的目标是，找到一个合适的 Z 和一种涂色方案，使得没有任何两颗不同颜色的石头会发生反应。如果找不到，就告诉博士这是不可能的（输出 -1）。

简单来说，就是要给石头合理染色，并选一个 Z，来避免所有“黑白配”的石头发生反应，的说！

解题思路喵~ 抓住关键！

这个题目看起来好复杂，尤其是那个 concat 函数和长长的公式，让人头大喵... 但别怕，猫娘带你一步步把它变简单！

第一步：简化那个可怕的公式！

我们解题的关键，就是处理这个 mod 3 的条件。让我们来研究一下 concat(x, y) mod 3 有什么规律。

concat(x, y) 的本质是 x * 10^d + y，其中 d 是 y 的位数。在模 3 的世界里，10 ≡ 1 (mod 3)。所以 10^d ≡ 1^d ≡ 1 (mod 3)。那么，concat(x, y) ≡ x * 1 + y ≡ x + y (mod 3)。

哇！concat 操作在模 3 之后，就变成了简单的加法！这个发现太棒了喵！

现在，我们把这个结论代入原来的反应条件： concat(A_i, A_j) × concat(A_j, A_i) + A_i × A_j ≡ Z (mod 3) 就变成了： (A_i + A_j) × (A_j + A_i) + A_i × A_j ≡ Z (mod 3)

让我们继续化简，为了方便，我们只看模 3 之后的值： (A_i + A_j)^2 + A_i × A_j ≡ Z (mod 3)A_i^2 + 2*A_i*A_j + A_j^2 + A_i*A_j ≡ Z (mod 3)A_i^2 + 3*A_i*A_j + A_j^2 ≡ Z (mod 3)

因为 3*A_i*A_j 肯定是 3 的倍数，所以 3*A_i*A_j ≡ 0 (mod 3)。最终，那个复杂的条件就变成了—— A_i^2 + A_j^2 ≡ Z (mod 3)

第二步：给石头分类！

现在问题变得超级简单了喵！两颗不同颜色的石头 i 和 j 是否反应，只取决于 (A_i^2 + A_j^2) mod 3 的值。

我们可以根据这个性质给石头分类。我们定义一个新属性 R_i = A_i^2 mod 3。

如果 A_i % 3 == 0，那么 R_i = 0^2 mod 3 = 0。
如果 A_i % 3 == 1，那么 R_i = 1^2 mod 3 = 1。
如果 A_i % 3 == 2，那么 R_i = 2^2 mod 3 = 4 mod 3 = 1。

所以，R_i 的值只可能是 0 或者 1！

R_i = 0 当且仅当 A_i 是 3 的倍数。
R_i = 1 当且仅当 A_i 不是 3 的倍数。

我们的目标是：选一个 Z，并把石头分成黑白两组，使得对于任何一颗黑石头 i 和白石头 j，都有 R_i + R_j <binary data, 3 bytes> Z (mod 3)。

第三步：构造无敌的染色方案！

我们来数一下 R=0 的石头有 count0 个，R=1 的石头有 count1 个。每种颜色都需要 N/2 个石头。

我们的策略是，通过合理分配，让“黑白配”产生的 R_i + R_j 的值的集合尽可能小，这样就容易找到一个安全的 Z 了。

情况一：R=0 的石头太多了 (count0 > N/2)

我们可以轻松地挑出 N/2 个 R=0 的石头，把它们都涂成黑色。
黑色组：所有石头的 R 值都是 0。
白色组：包含剩下的 count0 - N/2 个 R=0 的石头，以及全部 count1 个 R=1 的石头。
现在我们看看黑白配会产生哪些 R_i + R_j 的和：
- 黑(R=0) + 白(R=0) -> 和为 0
- 黑(R=0) + 白(R=1) -> 和为 1
产生的和只有 0 和 1。太好了！我们只要选择 Z=2，就绝对不会有石头反应了！
特殊情况：如果压根没有 R=1 的石头（count1=0），那所有石头都是 R=0，黑白两组都是 R=0，和永远是 0。这时选 Z=1 或 Z=2 都可以，代码里选了 Z=1，也是完全正确的呐。

情况二：R=0 的石头不够多 (count0 <= N/2)

这次我们不能让黑色组全是 R=0 了。反过来想，我们可以让白色组的成分变得单一！
黑色组：把所有 count0 个 R=0 的石头都涂成黑色，还差 N/2 - count0 个，就从 R=1 的石头里随便挑一些补上。
白色组：剩下的石头都是 R=1 的。
现在我们再看看黑白配的和：
- 黑(R=0) + 白(R=1) -> 和为 1
- 黑(R=1) + 白(R=1) -> 和为 2
产生的和是 1 和 2。我们只要选择 Z=0，就高枕无忧啦！
那个 count0 == N/2 的情况，其实是这个情况的特例。此时黑色组全是 R=0，白色组全是 R=1，和永远是 1，选 Z=0 当然可以啦！

你看，我们总能通过这种构造方法找到一个完美的方案，所以根本不需要输出 -1 的说！

代码实现喵~

cpp

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main() {
    // 喵~ 使用这个可以让输入输出更快哦
    ios::sync_with_stdio(false);
    cin.tie(0);

    int N;
    // 读入石头的数量 N
    cin >> N;
    vector<long long> A(N);
    // 读入每颗石头的能量值 A[i]
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }

    // R[i] 用来存储我们简化后的属性值 (A[i]^2 mod 3)
    vector<int> R(N);
    int count0 = 0; // 记录 R[i] == 0 的石头数量
    for (int i = 0; i < N; i++) {
        long long mod = A[i] % 3;
        // R[i] 只会是 0 或 1
        R[i] = (mod * mod) % 3; 
        if (R[i] == 0) {
            count0++;
        }
    }
    
    int count1 = N - count0; // R[i] == 1 的石头数量
    int half = N / 2;       // 每种颜色需要的石头数量
    
    // 先默认所有石头都涂成白色('1')，我们再把需要涂黑的改成黑色('0')
    string color(N, '1'); 

    // 情况一：R=0 的石头正好是 N/2 个
    // 此时，让所有 R=0 的石头是黑色，所有 R=1 的石头是白色
    // 黑(R=0) + 白(R=1) 的和总是 1，我们选 Z=0 就行
    if (count0 == half) {
        for (int i = 0; i < N; i++) {
            if (R[i] == 0) {
                color[i] = '0';
            }
        }
        cout << 0 << '\n';
        cout << color << '\n';
    } 
    // 情况二：R=0 的石头比 N/2 多
    // 我们就挑 N/2 个 R=0 的石头涂成黑色
    // 这样黑色组全是 R=0，白色组有 R=0 和 R=1 的
    // 黑白配的和可能是 0 或 1，我们选 Z=2 就行
    else if (count0 > half) {
        int quota = half; // 还需要涂黑的名额
        for (int i = 0; i < N; i++) {
            if (R[i] == 0 && quota > 0) {
                color[i] = '0';
                quota--;
            }
        }
        // 特殊情况：如果根本没有 R=1 的石头，那黑白都是 R=0，和总是0
        // 选 Z=1 或 Z=2 都行
        if (count1 == 0) {
            cout << 1 << '\n';
        } else {
            cout << 2 << '\n';
        }
        cout << color << '\n';
    } 
    // 情况三：R=0 的石头比 N/2 少
    // 我们把所有 R=0 的石头都涂黑，再从 R=1 的石头里挑一些补足 N/2 个
    // 这样白色组就全是 R=1 的了
    // 黑白配的和可能是 1 或 2，我们选 Z=0 就行
    else { // count0 < half
        // 先把所有 R=0 的涂黑
        for (int i = 0; i < N; i++) {
            if (R[i] == 0) {
                color[i] = '0';
            }
        }
        // 计算还需要多少个 R=1 的石头来凑够 N/2 个黑色
        int quota = half - count0;
        for (int i = 0; i < N; i++) {
            if (quota <= 0) break; // 名额用完就停
            if (R[i] == 1) {
                color[i] = '0';
                quota--;
            }
        }
        cout << 0 << '\n';
        cout << color << '\n';
    }

    return 0;
}

复杂度分析喵~

时间复杂度: O(N) 的说。我们只需要遍历几次数组，一次用来读入，一次用来计算 R 值和 count0，最后再遍历一次来确定颜色。每次遍历都是线性的，所以总的时间复杂度是 O(N)，非常快！
空间复杂度: O(N) 的说。我们需要 A 数组、R 数组和 color 字符串来存储石头的信息，它们的空间都和 N 成正比，所以空间复杂度是 O(N)。

知识点与总结

这道题真是太有趣了，喵~ 让我们来总结一下学到了什么吧！

核心思想：模运算化简！ concat 这种看起来很可怕的操作，在模运算下可能有非常简单的形式。10 ≡ 1 (mod 3) 是解开这道题的黄金钥匙！以后遇到复杂的数学表达式，记得先试试看能不能在模运算下简化它，说不定就有惊喜呢！
构造性算法: 这是一道典型的构造题。我们不是去搜索所有可能的答案，而是根据问题的性质，直接构造出一个满足条件的解。关键在于找到一种有效的分类方法（这里是按 R_i 的值分类），然后基于分类来构建分组（黑白两色），从而达成目标。
分类讨论: 根据 count0 和 N/2 的大小关系进行分类讨论，是让构造逻辑变得清晰的关键。每种情况下，我们的目标都是让其中一个颜色组的“成分”尽可能单一，从而限制“黑白配”产生的 R_i + R_j 的可能取值，这样就能轻松找到一个安全的 Z 值了。
编程小贴士: 像这种需要给 N 个物品染色或分组的问题，可以先初始化一个全是一种颜色的数组/字符串，然后根据逻辑去修改需要变成另一种颜色的部分。这样代码会很清晰，不容易出错呐。

希望这篇题解能帮到主人Sama哦！要继续加油，享受解题的乐趣喵~！

H. Hot Black Hot White - 题解 ​

比赛与标签 ​

喵~ 题目大意是什么呀？ ​

解题思路喵~ 抓住关键！ ​

第一步：简化那个可怕的公式！ ​

第二步：给石头分类！ ​

第三步：构造无敌的染色方案！ ​

代码实现喵~ ​

复杂度分析喵~ ​

知识点与总结 ​