<div class="post_brief"><p>
今天wc讲的题。主要其实是用拟阵来证明贪心的正确性。就构造一下就好了。不选的集合构成一个拟阵的基，如果基不能异或出0就是线性无关的。然后按照拟阵的贪心方法挨个加。</p>

 

策略是从大到小排个序能不选就不选，用异或消元来判断一下就好了。许久没有写了，还好没有搞忘。

 

代码还是比较短的，开心ing。

 

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;


typedef long long dint;
#ifdef WIN32
#define lld “%I64d”
#else
#define lld “%lld”
#endif
#define _l (long long int)


const int maxn = 109;


int n, a[maxn], b[maxn], c[maxn], t;
dint s;


bool hasZero() {
for (int i = 0; i < t; ++ i)
b[i] = c[i];
for (int i = 31, j = 0; i >= 0 && j < t; – i) {
for (int k = j; k < n; ++ k)
if ((b[k] >> i) & 1) {
swap(b[k], b[j]);
break;
}
if ((b[j] >> i) & 1) {
for (int k = j + 1; k < n; ++ k)
if ((b[k] >> i) & 1) {
b[k] ^= b[j];
if (!b[k])
return 1;
}
++ j;
}
}
return 0;
}


int main() {
#ifndef ONLINE_JUDGE
freopen(“in.txt”, “r”, stdin);
#endif


s = 0;
scanf("%d", &amp;n);
for (int i = 0; i &lt; n; ++ i)
	scanf("%d", a + i);
sort(a, a + n);
t = 0;
for (int i = n - 1; i &gt;= 0; -- i) {
	c[t ++] = a[i];
	if (hasZero()) {
		-- t;
		s += a[i];
	}
}
printf(lld "\n", s);



}