[BJWC2011]元素

link

也算是线性基的模板题。感觉凡是带异或的题都和线性基或者01trie脱不了干系(也有可能是我见过的题太少了)。

线性基有一个性质,即假如一个数可以被线性基所异或出来而惨遭剔除,只需剔除线性基构成中的一个数就可以把它放进去了。

于是就可以考虑贪心,把贡献从大到小排序,尝试加入贡献大者进线性基中。

#include<cstdio>
#include<algorithm>
#define zczc
#define int long long
using namespace std;
const int N=62;
const int M=1010;
inline void read(int &wh){
    wh=0;int f=1;char w=getchar();
    while(w<'0'||w>'9'){if(w=='-')f=-1;w=getchar();}
    while(w<='9'&&w>='0'){wh=wh*10+w-'0';w=getchar();}
    wh*=f;return;
}

int m,ans,s[N];
struct node{
	int a,b;
}a[M];
inline bool cmp(node s1,node s2){
	return s1.b>s2.b;
}

signed main(){
	
	#ifdef zczc
	freopen("in.txt","r",stdin);
	#endif
	
	read(m);
	for(int i=1;i<=m;i++){
		read(a[i].a);read(a[i].b);
	}
	sort(a+1,a+m+1,cmp);
	for(int i=1;i<=m;i++){
		int x=a[i].a;
		for(int j=N-1;j>=0&&x;j--){
			if((x&(1ll<<j))==0)continue;
			if(s[j])x^=s[j];
			else{
				ans+=a[i].b;s[j]=a[i].a;break;
			}
		}
	}
	printf("%lld\n",ans);
	
	return 0;
}
上一篇:数据结构


下一篇:MySQL保证ACID原理