P4570 [BJWC2011]元素

[题目](https://www.luogu.com.cn/problem/P4570) 别的题解里的高端证明咱也看不懂，咱就只能把这题看作一个线性基好题来做。 ### 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]$ 是插不进去的。 $$ d[a]\oplus d[b]\oplus d[c]=x\Rightarrow d[a]\oplus d[b]\oplus x=d[c] $$ 上面是的式子是异或的性质，因此可以知道线性基元素数量唯一。 回归本题 题目里不要魔法抵消不就是线性基的性质二吗！U•ェ•*U 所以我们可以巧妙的把题转化为：将元素序号插入线性基，让魔力值最大 那为什么我要这么强调性质三呢？~~闲的~~ 本题解题关键就是它——既然**元素数量不变**，那就贪心插入魔力值最大的呗╮(╯▽╰)╭ ### Code ```c++ #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