bzoj 2460 [BeiJing2011]元素 (线性基)

链接:https://www.lydsy.com/JudgeOnline/problem.php?id=2460

题意:

给你一堆矿石,矿石有a,b两种性质,取任意个矿石,满足取得的这些矿石a性质异或和不为0,且b性质和最大,求b性质和的最大值。

思路:

线性基模板题,

根据线性基的性质: 线性基的任意一个子集异或和不为0。我们可以根据这些矿石的b性质从大到小排序,依此将这些矿石的a性质插到线性基里,如果能够插入的话就选这个,不能插入的话就不选。

实现代码:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int M = 1e6+;
struct Linear_Basis{
ll b[],nb[],tot;
void init(){
tot = ;
memset(b,,sizeof(b));
memset(nb,,sizeof(nb));
} bool Insert(ll x){
for(int i = ;i >= ;i --){
if(x&(1LL<<i)){
if(!b[i]){
b[i] = x;
break;
}
x ^= b[i];
}
}
return x > ;
} ll Max(ll x){
ll ret = x;
for(int i = ;i >= ;i --)
ret = max(ret,ret^b[i]);
return ret;
} ll Min(ll x){
ll ret = x;
for(int i = ;i <= ;i ++)
if(b[i]) ret ^= b[i];
return ret;
} void rebuild(){
for(int i = ;i >= ;i --)
for(int j = i-;j >= ;j --)
if(b[i]&(1LL<<j)) b[i]^=b[j];
for(int i = ;i <= ;i ++)
if(b[i]) nb[tot++] = b[i];
} ll K_Min(ll k){
ll res = ;
if(k >= (1LL<<tot))
return -;
for(int i = ;i >= ;i --)
if(k&(1LL<<i))
res ^= nb[i];
return res;
}
}LB; struct node{
ll a,b;
}p[M]; bool cmp(node x,node y){
return x.b > y.b;
} int main(){
int n;
while(scanf("%d",&n)!=EOF){
LB.init();
ll ans = ;
for(int i = ;i <= n;i ++)
scanf("%lld%lld",&p[i].a,&p[i].b);
sort(p+,p++n,cmp);
for(int i = ;i <= n;i ++){
if(LB.Insert(p[i].a))
ans += p[i].b;
}
printf("%lld\n",ans);
}
}
上一篇:【C#进阶系列】24 运行时序列化


下一篇:idea 设置格式化代码 快捷键