题解：P13363 [GCJ 2011 Qualification] Candy Splitting

观察 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，这时他的糖果总价值最大。

代码

CPP

#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";
    }
}

题解：P13363 [GCJ 2011 Qualification] Candy Splitting

文章操作

芝士

规则应用

求最大价值

代码

相关推荐

评论

题解：P13363 [GCJ 2011 Qualification] Candy Splitting