C++ !異様な操作!

5855 ワード

テーマはSoloとkokoが2人の兄弟で、母は彼らに大きな袋の砂糖をあげて、すべての砂糖に自分の重さがあります.今、彼らはこれらの砂糖を2つの山に分けたいと思っています.砂糖を分ける任務はもちろん長兄のソロに落ちたが、kokoは二人で手に入れなければならない砂糖の総重量を「等しい」と要求した(kokoの論理によると).そうしないと泣くだろう.残念なことに、kokoはまだ非常に小さく、2つの数をバイナリに回して加算するだけで、常に進位を忘れています.12(1100)に5(101)を加えた場合:
 1100
+0101
——-
 1001

そこでkokoが得た計算結果は9(1001)であった.
他にもいくつかの例があります.
5 + 4 = 1
7 + 9 = 14
50 + 10 = 56

(実際、これは異或演算:125=9,54=1...)今Soloはとても貪欲で、できるだけ自分が得た砂糖の総重量を最大にして、koを泣かせないようにしたいと思っています.
解答要求時間制限:1000 ms、メモリ制限:64 MB
入力入力の最初の行は整数N(2≦N≦15)であり、袋の中に砂糖がどれだけあるかを示す.2行目は、i番目の糖の重量を表すN個の整数Ci(1≦Ci≦106)を含む.
出力kokoが泣かないようにすることができれば、Soloで得られる糖の総重量を出力し、そうでなければ「NO」を出力します.
サンプル入力サンプル1
3
3 5 6

出力サンプル1
11

入力サンプル2
5
1 2 3 4 5

出力サンプル2
NO

入力サンプル3
8
7258 6579 2602 6716 3050 3564 5396 1773

出力サンプル3
35165

ヒントSample 1では、3個の糖の重量が3、5、6であり、5(101)+6(110)=3(11)であるため、Soloは5と6の糖を持ち去り、kokoは3の糖を得た.
Sample 2の砂糖5個は、いくら分けても、kokoの要求を満たすことができないのでNO.
Sample 3の中でSoloは前の7つの砂糖を持って行って、全部で重さは35165です.
最初の構想はすべての方法を遍歴し、最大値を算出することである.異種または発見を検討したところ、2つのグループの異種または値が等しい場合、このグループ全体の異種または値は必ず0であり、例1で分析する.
3 ^ 5
0011 ^ 0101=0110(6)
6 ^ 6 = 0

また、この値のセットが異種または均等であれば、どのように分けてもよいので、要求を満たすためには最小値を除去するだけで、残りの和はSoloに必要な最大値です.
#include 
#include 
#include 
#include 
using namespace std;
const int maxInt = 2147483647;
int main()
{
     
	int n;
	while (cin>>n)
	{
     
		vector<int> numVec;
		int numSum = 0;
		int addSum = 0;
		int minNum = maxInt;
		while (n--)
		{
     
			int num;
			cin >> num;
			numSum ^= num;
			addSum += num;
			numVec.push_back(num);
			if (num < minNum) {
     
				minNum = num;
			}
		}
		if (!numSum){
     
			cout << addSum-minNum << ::endl;
		} else {
     
			cout << "NO" << ::endl;
		}	
	}
	
	return 0;
}