BZOJ3105 [cqoi2013]新Nim游戏

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

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

代码还是比较短的，开心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", &n);
	for (int i = 0; i < n; ++ i)
		scanf("%d", a + i);
	sort(a, a + n);
	t = 0;
	for (int i = n - 1; i >= 0; -- i) {
		c[t ++] = a[i];
		if (hasZero()) {
			-- t;
			s += a[i];
		}
	}
	printf(lld "\n", s);
}