题解：P13363 [GCJ 2011 Qualification] Candy Splitting

Doraeman · 2025-07-28 17:33:50 · 题解

观察 Patrick 的“加法”计算方法，就会发现，这就是——号称“不进位加法”的，传说中的异或（符号为 \oplus）。

芝士

与本题有关的异或规则如下。

• 异或有交换律和结合律。
• 对于十进制数 a,b，a\oplus b=0 与 a=b 等价。

规则应用

循环求所有糖果的异或总值 xor_{tot}。

设将所有糖果任意分成两堆，其异或值分别为 a,b。
根据异或的结合律，a\oplus b=xor_{tot}。

• 如果 xor_{tot}\not=0，说明 a\oplus b\not=0。根据规则，a\not=b。
  此时，在 Patrick 眼中两堆糖果价值不相等。无论如何分堆，他一定会哭，直接输出 NO。

• 如果 xor_{tot}=0，说明 a\oplus b=0。根据规则，a=b。
  此时，在 Patrick 眼中两堆糖果价值相等，不会哭。

  这种情况下考虑求 Sean 可以获得的糖果的最大价值。

求最大价值

在 Sean 眼中，一堆糖果的总价值是所有糖果的价值之和（而非异或值）。

这种情况下，可以求出所有糖果的价值之和。由于必须分给 Patrick 一个非空堆，所以可以直接给他一个价值最低的糖果（兄弟情义呢？塑料兄弟情？），剩余的 N-1 颗糖果都给 Sean，这时他的糖果总价值最大。

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int T; cin >> T;
    for(int _=1; _<=T; _++){
        int n; cin >> n;
        int xor_tot = 0, sum = 0, mini = 1e6+5;
        for(int i=1; i<=n; i++){
            int x; cin >> x;
            xor_tot ^= x;
            sum += x;
            mini = min(x, mini);
        }

        cout << "Case #" << _ << ": ";
        if(!xor_tot) cout << sum - mini << '\n';
        else cout << "NO\n";
    }
}