Moe's CF Life

喵哈喽~！各位看官，今天由我，小猫娘，来给大家讲解一下 Codeforces 上的这道 Array Coloring 问题哦，喵~ 这道题其实就像给一堆小鱼干分类一样，只要找到诀窍，就非常简单啦！

题目大意

我们拿到一个有 n 个整数的数组 a。我们的任务是，把数组里所有的数字都涂上两种颜色（比如说红色和蓝色），需要满足下面几个条件喵：

每个数字都必须被涂上颜色。
两种颜色都必须至少用一次（也就是说，不能所有数字都涂成红色，或者都涂成蓝色）。
最最重要的一点！所有涂成红色的数字加起来的总和，跟所有涂成蓝色的数字加起来的总和，它们的奇偶性必须相同。

举个栗子：如果红色数字的总和是 10（偶数），那么蓝色数字的总和也必须是偶数，比如 18。如果红色数字总和是 7（奇数），那蓝色数字总和也必须是奇数，比如 13。

如果能找到这样一种涂色方法，我们就输出 "YES"，否则就输出 "NO"，很简单吧，喵~

解题思路

一看到奇偶性，小猫娘的脑袋里就叮地一下亮了灯！这种问题呀，通常都和数学上的一些小性质有关，而不是真的要去暴力尝试所有涂色方法哦，那也太慢啦。

我们来分析一下这个核心条件：红色总和与蓝色总和的奇偶性相同。

设红色数字的总和是 Sum(Red)
设蓝色数字的总和是 Sum(Blue)
设整个数组所有数字的总和是 TotalSum

那么很显然，TotalSum = Sum(Red) + Sum(Blue)，对吧？

现在我们来考虑奇偶性：

情况一：如果 Sum(Red) 是偶数，并且 Sum(Blue) 也是偶数（满足条件！）。那么 TotalSum = 偶数 + 偶数 = 偶数。
情况二：如果 Sum(Red) 是奇数，并且 Sum(Blue) 也是奇数（也满足条件！）。那么 TotalSum = 奇数 + 奇数 = 偶数。

喵呜！发现了吗？不管在哪种我们想要的情况下，两个分区的和加起来，也就是整个数组的总和 TotalSum，必须是一个偶数！

那如果 TotalSum 是个奇数呢？那它只能由一个奇数和一个偶数相加得到。这样的话 Sum(Red) 和 Sum(Blue) 的奇偶性就肯定不一样了，直接就不满足条件了。所以，如果 TotalSum 是奇数，我们就可以直接说 "NO" 啦！

好，现在我们知道了一个必要条件：TotalSum 必须是偶数。那这个条件足够吗？也就是说，只要 TotalSum 是偶数，就一定能找到一种满足条件的涂色方法吗？

我们来试试看~ 题目保证了数组长度 n >= 2，所以我们总能分出两个非空的颜色组。最简单的分法就是：我们把第一个数字 a_1 涂成红色，剩下的所有数字 a_2, a_3, ... a_n 全都涂成蓝色。

Sum(Red) = a_1
Sum(Blue) = TotalSum - a_1

因为我们已经假设了 TotalSum 是偶数：

如果 a_1 本身是偶数：Sum(Red) 就是偶数。Sum(Blue) = TotalSum(偶) - a_1(偶) = 偶数。两者奇偶性相同！
如果 a_1 本身是奇数：Sum(Red) 就是奇数。Sum(Blue) = TotalSum(偶) - a_1(奇) = 奇数。两者奇偶性也相同！

看吧~ 只要 TotalSum 是偶数，我们总能找到至少一种涂色方法（就是把第一个元素单独分出来）来满足条件！

所以，这道题的逻辑就超级简化了，喵~ 我们只需要判断整个数组所有数字的总和是不是偶数就行了！

怎么判断一个总和是不是偶数呢？我们其实不需要真的把它们全加起来。我们知道：

偶数 + 偶数 = 偶数
奇数 + 奇数 = 偶数
偶数 + 奇数 = 奇数

这说明，一堆数加起来的和的奇偶性，只跟这堆数里有多少个奇数有关。如果有偶数个奇数，那它们的和就是偶数。如果有奇数个奇数，那它们的和就是奇数。

所以，最终的结论就是：统计一下数组里有多少个奇数。如果奇数的个数是偶数，那么总和就是偶数，输出 "YES"。如果奇数的个数是奇数，那么总和就是奇数，输出 "NO"。

题解代码

下面是解题的 C++ 代码，小猫娘加上了可爱的注释，让你看得更明白哦~

cpp

#include <iostream>

// 这个函数用来解决单个测试用例，喵~
void solve() {
    int n;
    std::cin >> n;

    // 我们要判断数组总和的奇偶性。
    // 一个聪明的办法是计算所有数字的奇偶性（0代表偶，1代表奇）的总和的奇偶性。
    // 这可以通过异或(XOR)操作来实现，喵~
    // 初始时，我们认为奇数的数量是0，所以总和是偶数。
    int odd_count_is_odd = 0; // 0 表示奇数个数是偶数, 1 表示奇数个数是奇数

    for (int i = 0; i < n; ++i) {
        int a;
        std::cin >> a;
        
        // a % 2 可以得到这个数的奇偶性 (偶数是0, 奇数是1)
        // 我们用异或来追踪奇数个数的奇偶性。
        // odd_count_is_odd = 0 (偶数个奇数), a % 2 = 1 (又来一个奇数) -> odd_count_is_odd 变成 1
        // odd_count_is_odd = 1 (奇数个奇数), a % 2 = 1 (又来一个奇数) -> odd_count_is_odd 变成 0
        // 这不就正好是异或运算嘛！
        odd_count_is_odd ^= (a % 2);
    }

    // 如果 odd_count_is_odd 最后是 0，说明有偶数个奇数，总和是偶数。
    if (odd_count_is_odd == 0) {
        std::cout << "YES\n";
    } else { // 否则，有奇数个奇数，总和是奇数。
        std::cout << "NO\n";
    }
}

int main() {
    // 加速一下输入输出，让程序跑得像小猫一样快！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

知识点小课堂

1. 奇偶性 (Parity)

奇偶性是整数的一个基本属性，一个数要么是奇数，要么是偶数。

偶数：能被 2 整除的整数（如 0, 2, 8, -4）。
奇数：不能被 2 整除的整数（如 1, 3, 9, -5）。

奇偶性在加法和乘法运算中有非常稳定的规律，这次我们主要用到了加法规律：

偶 + 偶 = 偶
奇 + 奇 = 偶
偶 + 奇 = 奇

理解这些是解决这道题的第一步，也是最重要的一步哦，喵~

2. 位运算：异或 (Bitwise XOR)

异或是一个二进制运算符，符号是 ^。它的规则是：两个操作数相对应的位相同，则结果为 0；如果不同，则结果为 1。

A	B	A ^ B
0	0	0
0	1	1
1	0	1
1	1	0

异或有一个非常有趣的性质：x ^ x = 0，x ^ 0 = x。这让它很适合用来解决“出现次数”相关的问题。在我们的代码里，odd_count_is_odd ^= (a % 2) 就是一个绝妙的应用。

a % 2 的结果不是 0 就是 1。
我们用一个变量 odd_count_is_odd 来记录当前遇到的奇数（也就是 a % 2 == 1 的情况）的个数是奇是偶。
每当遇到一个奇数（a % 2 == 1），我们就对 odd_count_is_odd 进行 ^ 1 操作，这会使它在 0 和 1 之间翻转。
遇到偶数（a % 2 == 0）时，^ 0 操作不改变 odd_count_is_odd 的值。
所以，在遍历完整个数组后，odd_count_is_odd 的值就准确地反映了奇数总个数的奇偶性！是不是很酷，喵~

好啦，这次的题解就到这里啦！希望小猫娘的讲解对你有帮助哦。下次再见，喵~！

题目大意 ​

解题思路 ​

题解代码 ​

知识点小课堂 ​

1. 奇偶性 (Parity) ​

2. 位运算：异或 (Bitwise XOR) ​