BZOJ3105 [cqoi2013]新Nim游戏

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

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

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

1	#include <cstdio>
2	#include <cstring>
3	#include <algorithm>
4	
5	using namespace std;
6	
7	typedef long long dint;
8	#ifdef WIN32
9	#define lld "%I64d"
10	#else
11	#define lld "%lld"
12	#endif
13	#define _l (long long int)
14	
15	const int maxn = 109;
16	
17	int n, a[maxn], b[maxn], c[maxn], t;
18	dint s;
19	
20	bool hasZero() {
21		for (int i = 0; i < t; ++ i)
22			b[i] = c[i];
23		for (int i = 31, j = 0; i >= 0 && j < t; -- i) {
24			for (int k = j; k < n; ++ k)
25				if ((b[k] >> i) & 1) {
26					swap(b[k], b[j]);
27					break;
28				}
29			if ((b[j] >> i) & 1) {
30				for (int k = j + 1; k < n; ++ k)
31					if ((b[k] >> i) & 1) {
32						b[k] ^= b[j];
33						if (!b[k])
34							return 1;
35					}
36				++ j;
37			}
38		}
39		return 0;
40	}
41	
42	int main() {
43	#ifndef ONLINE_JUDGE
44		freopen("in.txt", "r", stdin);
45	#endif
46		
47		s = 0;
48		scanf("%d", &n);
49		for (int i = 0; i < n; ++ i)
50			scanf("%d", a + i);
51		sort(a, a + n);
52		t = 0;
53		for (int i = n - 1; i >= 0; -- i) {
54			c[t ++] = a[i];
55			if (hasZero()) {
56				-- t;
57				s += a[i];
58			}
59		}
60		printf(lld "\n", s);
61	}
62