P4570 [BJWC2011]元素

是个汉子 · 2020-10-20 15:07:25 · 题解

题目

别的题解里的高端证明咱也看不懂，咱就只能把这题看作一个线性基好题来做。

Solution

首先，我学过的线性基有三个性质

1. 原序列里的任意一个数都可以通过线性基中的一些数异或得到
2. 线性基里的任意一些数异或起来都不能得到 0
3. 线性基里面的数的个数唯一，在性质一的前提下，有最少的数

（唯一指的是每个序列的线性基的元素数量唯一但线性基不一定唯一）

现在稍微说一下性质三的正确性：

如果序列元素都能插入线性基，那么插入顺序不管是什么，线性基的元素数量就是序列元素数量

如果有些元素是不能插入的。

设其中一个数为 x ，那 x 一定满足 x=d[a]\oplus d[b]\oplus d[c] 这样的形式，此时的插入顺序应为 d[a],d[b],d[c],x 。如果将顺序变为 d[a],d[b],x,d[c] ， d[c] 是插不进去的。

上面是的式子是异或的性质，因此可以知道线性基元素数量唯一。

回归本题

题目里不要魔法抵消不就是线性基的性质二吗！U•ェ•*U

所以我们可以巧妙的把题转化为：将元素序号插入线性基，让魔力值最大

那为什么我要这么强调性质三呢？闲的

本题解题关键就是它——既然元素数量不变，那就贪心插入魔力值最大的呗╮(╯▽╰)╭

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long

using namespace std;
const int N=1010;
struct node{
    ll x;
    int y;
}a[N];
int n,ans;
ll d[70];

inline bool cmp(node x,node y){
    return x.y>y.y;
}

inline bool insert(ll x){
    for(int i=62;i>=0;i--){
        if(x&(1ll<<i)){
            if(!d[i]){
                d[i]=x;
                return true;
            }
            else x^=d[i];
        }
    }
    return false;
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%lld%d",&a[i].x,&a[i].y);
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++)
        if(insert(a[i].x)) ans+=a[i].y;
    printf("%d\n",ans);
    return 0;
}

今天，你学会线性基的性质了吗 :D