题解：P13363 [GCJ 2011 Qualification]

题目翻译

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

Patrick 还很小，不会正确的加法。他只会一种近似的二进制加法：当两个

1

相加时，他会忘记进位。例如，计算

12

，二进制

1100

和

5

，二进制

0101

的和时，他会这样计算：

CPP

  1100
+ 0101
------
  1001

结果得到

9

（二进制

1001

），因为他没有正确处理进位。其他例子：

CPP

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

CPP

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

题解：P13363 [GCJ 2011 Qualification]

文章操作