BZOJ 2460 [BeiJing2011]元素

题目大意

给你一个序列，让你选出一些元素，使得它们的任意集合的亦或和均不为0。

线性基傻题。

线性基就是建立一些方程组，使得抽出任意集合亦或和均不为0.

高斯消元即可。

#include <cstdio>
#include <algorithm>
using namespace std;
#define N 1010
typedef long long ll;
struct stone{ll num;int mag;}a[N];
int n;
int gauss()
{
	ll i;int j,k,cnt=0,ret=0;
	for(ll i=1ll<<60;i;i>>=1)
	{
		for(j=++cnt,k=0;j<=n;++j)
			if((a[j].num&i)&&a[j].mag>a[k].mag)
				k=j;
		if(!k) {cnt--;continue;}
		swap(a[cnt],a[k]),ret+=a[cnt].mag;
		for(j=1;j<=n;++j)
			if(j!=cnt&&a[j].num&i)
				a[j].num^=a[cnt].num;
	}
	return ret;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i) scanf("%lld%d",&a[i].num,&a[i].mag);
	printf("%d\n",gauss());
	return 0;
}