【贪心】【线性基】bzoj2460 [BeiJing2011]元素

题意：让你求一些数在XOR下的带权极大无关组。

带权极大无关组可以用贪心，将这些数按权值从大到小排序之后，依次检验其与之前的数是否全都线性无关。可以用线性基来搞。

可以用拟阵严格证明，不过也可以脑补一下……

#include<cstdio>

#include<algorithm>

using namespace std;

typedef long long ll;

ll d[64],p[64];

int cnt;//简化线性基的大小

bool Insert(ll val){//尝试插入线性基，返回是否插入成功

	for(int i=62;i>=0;--i){

		if(val&(1ll<<i)){

			if(!d[i]){

				d[i]=val;

				break;

			}

			val^=d[i];

		}

	}

	return val>0;

}

ll QueryMax(){

	ll res=0;

	for(int i=62;i>=0;--i){

		if((res^d[i])>res){

			res^=d[i];

		}

    }

	return res;

}

ll QueryMin(){

	for(int i=0;i<=62;++i){

		if(d[i]){

			return d[i];

		}

	}

	return 0;

}

void Rebuild(){//化为简化线性基

	for(int i=62;i>=0;--i){

		for(int j=i-1;j>=0;--j){

			if(d[i]&(1ll<<j)){

				d[i]^=d[j];

			}

		}

	}

	for(int i=0;i<=60;++i){

		if(d[i]){

			p[cnt++]=d[i];

		}

	}

}

ll Kth(ll K){

	ll res=0;

	if(K>=(1ll<<cnt)){

		return -1ll;

	}

	for(int i=60;i>=0;--i){

		if(K&(1ll<<i)){

			res^=p[i];

		}

	}

	return res;

}

int n;

struct Point{

	ll x,y;

	Point(const ll &x,const ll &y){

		this->x=x;

		this->y=y;

	}

	Point(){}

};

Point a[1005];

bool cmp(const Point &a,const Point &b){

	return a.y>b.y;

}

int main(){

//	freopen("bzoj2460.in","r",stdin);

	scanf("%d",&n);

	for(int i=1;i<=n;++i){

		scanf("%lld%lld",&a[i].x,&a[i].y);

	}

	sort(a+1,a+n+1,cmp);

	ll ans=0;

	for(int i=1;i<=n;++i){

		if(Insert(a[i].x)){

			ans+=a[i].y;

		}

	}

	printf("%lld\n",ans);

	return 0;

}

巴特西

【贪心】【线性基】bzoj2460 [BeiJing2011]元素

最新文章

热门文章