题解：P13363 [GCJ 2011 Qualification]

· · 题解

题解：P13363 [GCJ 2011 Qualification]

题目链接

题目翻译

Sean 和 Patrick 兄弟从父母那里得到了一袋糖果。每颗糖果都有一个正整数值，他们想把糖果分成两堆。首先，Sean 将糖果分成两堆，并选择一堆给 Patrick。然后，Patrick 会计算每堆糖果的价值（即堆中所有糖果值的总和）。如果他发现两堆的价值不相等，就会开始哭闹。

Patrick 还很小，不会正确的加法。他只会一种近似的二进制加法：当两个 1 相加时，他会忘记进位。例如，计算 12，二进制1100 和 5，二进制 0101 的和时，他会这样计算：

  1100
+ 0101
------
  1001

结果得到 9（二进制 1001），因为他没有正确处理进位。其他例子：

5 + 4 = 1
7 + 9 = 14
50 + 10 = 56

Sean 擅长加法，希望在不惹哭弟弟的情况下，尽可能多地拿走糖果的价值。我们需要判断是否可以将糖果分成两堆，使得 Patrick 认为两堆的价值相等。如果可能，求出 Sean 能拿走的堆的最大价值。

输入格式

第一行是测试用例数 T。每个测试用例包含两行：第一行是糖果数 N，第二行是 N 个糖果的值 C_i。

输出格式

对于每个测试用例，输出 "Case #x: y"，其中 x 是测试用例编号。如果无法满足条件，y 为 "NO"；否则，y 为 Sean 能拿走的堆的最大价值。

思路

观察题目样例很容易发现，Patrick 的加法实际上是按位异或。因此，我们把问题转化为如何才能使得两堆的异或和相等。设总异或和为 sum，若 sum 为 0，则可以将糖果分成任意两堆，否则无法满足条件。

若总异或和为 0，则 Sean 可以拿走任意一堆，为了保证剩下的子集的异或和与原总异或和均为 0，可以考虑拿走总和最大的子集，其总和为总糖果和减去最小的糖果值。

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
int t,n,x,s,c[100005];
void solve(int tas)
{
    x=0,s=0;
    memset(c,0,sizeof(c));
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>c[i];
        x^=c[i];
        s+=c[i];
    }
    if(x!=0)
    {
        cout<<"Case #"<<tas<<": NO\n";
        return;
    }
    int mn=1e18;
    for(int i=1;i<=n;i++) mn=min(mn,c[i]);
    cout<<"Case #"<<tas<<": "<<s-mn<<'\n';
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>t;
    for(int i=1;i<=t;i++) solve(i);
    return 0;
}