G65 线性基+贪心法 P4570 [BJWC2011] 元素

视频链接：

P4570 [BJWC2011] 元素 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

// 线性基 O(60*n)
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

#define LL long long
const LL N=1005;
int n,m;
struct node{
  LL num,val;
}a[N],p[70];

bool cmp(node a,node b){
  return a.val>b.val;
}
void insert(node x){ //贪心法
  for(int i=60;i>=0;--i){
    if(x.num>>i&1){ //x第i位为1
      if(p[i].num){  //已存在p[i]
        x.num^=p[i].num;
      }
      else{ //不存在p[i]
        p[i]=x; break;
      }
    }
  }
}
int main(){
  cin>>n;
  for(int i=0;i<n;++i)
    cin>>a[i].num>>a[i].val;
  sort(a,a+n,cmp);
  for(int i=0;i<n;++i) insert(a[i]);
  LL sum=0;
  for(int i=0;i<=60;++i) sum+=p[i].val;
  cout<<sum<<endl;
}