题解：P12156 [蓝桥杯 2025 省 Java B] 电池分组

· · 题解

一、题目概述

本题出自蓝桥杯 2025 省赛 Java B 组，要求对实验室新研发的 N 个新型能量电池进行分组实验。每个电池有对应的能量值，需将这 N 个电池分成两组，使得两组电池能量值的异或和相等，并且每组至少包含一个能量电池。题目会给出多个测试用例，需要对每个测试用例判断是否能完成这样的分组，若可以则输出 YES，否则输出 NO。

二、输入输出要求

输入格式

第一行包含一个整数 T，表示测试用例的数量。每个测试用例占两行： 第一行包含一个整数 N，表示能量电池的数量。 第二行包含 N 个整数 A_1, A_2, \dots, A_N，表示每个能量电池的能量值。

输出格式

对于每个测试用例，输出一行。如果可以将能量电池分成两组，使得这两组能量电池的能量值异或和相等，则输出 YES；否则，输出 NO。

三、解题思路

本题的关键在于利用异或运算的性质来判断是否能进行符合要求的分组。异或运算（用符号 ^ 表示）具有以下重要性质：

交换律：a ^ b = b ^ a，这意味着异或运算中操作数的顺序不影响结果。

结合律：(a ^ b) ^ c = a ^ (b ^ c)，可以随意调整异或运算的计算顺序。

自反性：任何数和自身异或结果为 0，即 a ^ a = 0。

与 0 异或：任何数和 0 异或结果为其本身，即 a ^ 0 = a。

假设可以将 N 个能量电池分成两组，且两组的异或和都为 x，那么所有电池能量值的异或和 S 就等于这两组异或和再进行异或运算，即 S = x ^ x。根据异或运算的自反性可知 x ^ x = 0，所以如果所有电池能量值的异或和不为 0，那么肯定无法分成满足条件的两组。而当所有电池能量值的异或和为 0 且 N \geq 2 时，必然可以分成满足条件的两组（因为至少有两个电池，且整体异或和为 0，可以通过合理分配电池到两组来实现两组异或和相等）。

四、代码实现

#include <iostream>
using namespace std;

int main() {
    int T;
    cin >> T;
    while (T--) {
        int N;
        cin >> N;
        int xor_sum = 0;
        for (int i = 0; i < N; ++i) {
            int a;
            cin >> a;
            xor_sum ^= a;
        }
        if (xor_sum == 0 && N >= 2) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }
    return 0;
}