G65 线性基+贪心法 P4570 [BJWC2011] 元素
视频链接：G65 线性基+贪心法 P4570 [BJWC2011] 元素_哔哩哔哩_bilibili
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; }