洛谷3812：【模板】线性基—

洛谷3812：【模板】线性基——题解

阅读量：6716 次

发布时间：2019-06-25

本文共 901 字，大约阅读时间需要 3 分钟。

给定n个整数（数字可能重复），求在这些数中选取任意个，使得他们的异或和最大。

我知道代码很简单，可是我一直在找一个理解性题解。

（我笨啊……）

这个人说的十分的好，下面引用他的话：（侵删）

首先考虑下面这个情况：

如果这n个数每个数的最高位的1的位置都不一样，我们就可以从高位向低位贪心选择取或者不取。

线性基就是把n个数选一些异或和出来化成这样一种情况：

对于当前这个数，选取它的最高位的1，看看线性基中有没有已经存入一个这样的数，如果没有存入，当然就把这个数存入，退出。

但是如果已经有了呢？可以发现线性基中存了的数一定是之前一些数的异或和，并且它的最高位的1也是同一位。那么我们把当前这个数异或上线性基存的这个数（显然结果还是一些数的异或和），自然这个最高位的1的位置就会变低，然后再丢回上一步重新考虑。

最后在这个线性基上做贪心就行了。

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;typedef long long ll;ll a[51];void insert(ll k){    for(int i=50;i>=0;i--){    if(k&(1LL<
         
          =0;i--){    if(ans<(ans^a[i]))ans^=a[i];    }    printf("%lld\n",ans);    return 0;}