线性基题目(元素)

链接：https://www.luogu.com.cn/problem/P4570

线性基最重要的性质
1、原序列任意数字，都可由线性基异或得到。
2、线性基不可能异或得到0
3、无论怎么用原序列对线性基进行插入，得到的线性基是一定的。

题目分析：由于线性基不可能为0，而线性基已经满足不会异或到0且最大的条件(不然可以继续往线性基里插入元素)
那么这时即可贪心，按权值排序，如果能插入则更新答案

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
const int N = 1e5 + 10;
struct node{
    ll a,b;
    bool operator <(const node &w)const{
        return b > w.b;
    }
}tr[N];
int p[64];
bool insert(ll x){
    for(int i=63;i>=0;i--){
        if(!(x >> i)) continue;
        if(!p[i]){
            p[i] = x;
            return 1;
        }
        x ^= p[i];
    }
    return 0;
}
int main(){
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> tr[i].a >> tr[i].b;
    }
    sort(tr+1,tr+1+n);
    ll ans = 0;
    for(int i=1;i<=n;i++){
        if(insert(tr[i].a)) ans += tr[i].b;
    }
    cout << ans << endl; 
    return 0;
}