Qualification Round 2011 C: Candy Splitting

問題概要

長さN(

解法

2つの集合のxorが等しいので、元の数列のxorは0になる。これが可能である条件。またこのとき、どのような分割でもxorは等しくなる。したがって、和の最大値は全体の和から最小値を引いたものとなる。

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX_N = 1009;
int N;
int as[MAX_N];

int solve(){
	int mi = 1<<29, tot = 0, x = 0;
	for(int i=0; i<N; i++){
		mi = min(mi, as[i]);
		tot += as[i];
		x ^= as[i];
	}
	return x?-1:(tot-mi);
}

int main(){
	int T;
	scanf("%d",&T);
	for(int c=1; c<=T; c++){
		scanf("%d",&N);
		for(int i=0; i<N; i++){
			scanf("%d",as+i);
		}
		printf("Case #%d: ",c);
		int ans = solve();
		if(ans<0){
			puts("NO");
		}
		else{
			printf("%d\n",ans);
		}
	}
	return 0;
}