luogu4570 元素

problem

有\(n\)个二元组, \((x,y)\),要选出一些二元组，使得他们的\(x\)的任何一个子集的异或和不为\(0\)并且\(y\)的和最大。

solution

考虑是\(x\)的子集异或和不为0这个条件。如果他有一个子集异或和为\(0\),那么就说明其中有一个数字可以由其他的数字异或得到。所以就是要找出他的线性基。使得线性基中的元素的\(y\)之和最大。

考虑线性基的一个性质:

线性基的数量是一定的，即如果往原线性基中添加一个元素。那么也要删除恰好一个元素。

证明:

如果首先证明删除最多一个元素。这个根据线性基的定义就可以知道。线性基是可以得到原数组中所有异或和的一个最小子集，所以如果删除了多于一个元素。那么线性基肯定就不能得到原数组的所有异或和了。

然后证明至少删除一个元素。如果不删除的话。原线性基没有加入这个元素，肯定是这个元素可以被其他元素异或得到。现在将它加进去但是不删除元素。就不符合线性基定义了。

所以对于这个题，我们优先加入\(y\)值大的。所以按照\(y\)排个序然后求线性基即可。

code

/*
* @author: wxyww
* @date:   2019-07-23 10:11:07
* @last modified time: 2019-07-23 10:25:42
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
using namespace std;
typedef long long ll;
const int n = 1010;
#define pi pair<int,ll>
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
pi a[n];
bool cmp(pi x,pi y) {
    return x.first > y.first;
}
ll p[n],ans;
int main() {
    int n = read();
    for(int i = 1;i <= n;++i) {
        a[i].second = read();a[i].first = read();
    }
    sort(a + 1,a + n + 1,cmp);
    for(int i = 1;i <= n;++i) {
        ll x = a[i].second;
        for(int j = 63;j >= 0;--j) {
            if(!(x & (1ll << j))) continue;
            if(!p[j]) {
                p[j] = x;ans += a[i].first;break;
            }
            x ^= p[j];
        }
    }
    cout<<ans<<endl;
    return 0;
}