P3812 【模板】线性基

原来我听到线性基的时候,我觉得可能是什么非常高深的算法(눈‸눈)。但是今天用了一个早上自学后，发现其实并没有想象中的那么难。所以写篇板子题的题解纪念一下。 ### 一、定义 首先什么是线性基呢？对于一组数 A1...An，他们的线性基为 P1...Pm ，其中** Pi 是出现 1 的最高位在第 i 位的数** 。很容易想到，线性基的值域与原数组的值域相同。那么我们便可以通过线性基( ☉_☉)≡☞o────★°来求最大异或和。 ### 二、构造方法 对于每一个数，我们找出他的最高位的 1 在第 i 位， 如果此时 Pi 为零，就将这个数加入线性基，否则异或 Pi 继续找。然后我们就可以在 0 到 k 位上处理好每一位的线性基。这样得到的线性基保证每一位都能有对应的最大值。 例：4个数 2 9 10 17 2 ----> 10 9 ----> 1001 10 ----> 1010 17 ----> 10001 最终得到的 P4-P0: 17 9 0 2 1 ### 三、寻找答案 在我们得到的线性基中，从高位到低位用贪心贪掉每一个元素（即如果异或了这个元素变大就异或他）。那么为什么可以**将一个没有单调性的异或和**转化为贪心呢？ ( •́ _ •̀)？ 证明：首先从高位向低位找的过程中，每一个高位的值都不会被后面的元素所覆盖影响。然后我们可以结合下面三种情况理解（给出的是二进制）： 1、 现在的答案为1001010， Pi 为100001， 那么异或后答案为1001011，肯定更优； 2、现在的答案为1011111， Pi 为111111， 那么异或后的答案为1100000，虽然后面变小了 但此高位变大了所以也是更优； 3、现在的答案为1100000， Pi 为111111. 那么异或后的答案为1011111，虽然后面变大了 但此高位变小了所以肯定不优； 所以我们可以发现此处的贪心即贪**每一位的值使他最大**。 ### 然后我们就可以愉快的做出了这道模板题了！！！ 然鹅，线性基并没有结束(´≖◞౪◟≖) （如果已经被线性基冲昏了的直接跳过吧(；´ﾟωﾟ｀人)） ### 四、查询某个数 就是查找某个数是否可以由这 n 个数中任一个数异或得到。首先还是刚才那个定理：**线性基的值域与原数组的值域相同**。 还有我们要发现一个性质：**如果 x1 ^ x1 = x3, 那么 x3 ^ x2 = x1,且 x3 ^ x1 = x2**（可以自己证明一下）。 我们也是从低到高扫这个数的每一位，如果这第 i 位为 1，就异或上 Pi，然后知道处理到最后一位。如果变成 0 了，那么就是可以的。 ### 【正解】 ```cpp #include <bits/stdc++.h> #define N 51 #define ll long long using namespace std; int n; ll ans; ll a[N], p[101]; inline ll read() { char ch = getchar(); ll x = 0, f = 1; while(ch > '9' || ch < '0') { if(ch == '-') f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return x * f; } void Get_LB(ll x) { for(int i = 62; i >= 0; i--) { if(!(x >> (ll)i)) continue; if(!p[i]) { p[i] = x; break; } x ^= p[i]; } } int main() { n = read(); for(int i = 1; i <= n; i++) Get_LB(a[i] = read()); for(int i = 62; i >= 0; i--) if((ans ^ p[i]) > ans) ans ^= p[i]; cout << ans; return 0; } ```