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