20150209 WC2015 Day0.2
20150210 WC2015 Day0.4

BZOJ3105 [cqoi2013]新Nim游戏

laekov posted @ 2015年2月10日 21:57 in 未分类 with tags bzoj matroid , 572 阅读

今天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);
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter