P3812 线性基详解

【模板】线性基 - 洛谷

将若干个数异或起来的的最大值是多少？

题解：

这里我们还是采用贪心的思想，从最高位开始异或，一直向下。这里我们可以使用线性基来保存二进制下的信息。

void insert(int x){for(int i=62;i>=0;i--){if((x>>i)&1){if(!p[i]) {p[i]=x;break;}x^=p[i];}}}

这样线性基就具有以下性质：

1:查询是否能被其他数异或出来；

int insert(int x){for(int i=62;i>=0;i--){if((x>>(ll)i)&1){if(!p[i]) {p[i]=x;break;}x^=p[i];}}return x;}

2:查询异或最大值或最小值；

 int askmx() {int ans=0;for(R int i=62;i>=0;i--)if((ans^p[i])>ans) ans^=p[i];return ans;}

int askmn() {if(zero) return 0;//判断原数组是否有0；for(R int i=0;i<=62;i++)if(p[i]) return p[i];}

3：查询第K大（小）；

void rebuild() {cnt=0;top=0;for(R int i=MB;i>=0;i--)for(R int j=i-1;j>=0;j--)if(p[i]&(1LL<<j)) p[i]^=p[j];for(R int i=0;i=(1LL<=0;i--)if(k&(1LL<<i)) ans^=d[i];return ans; }

线性基和01trie的区别：

线性基和01trie都能对树的异或进行处理，但是线性基作用更为广泛，能对很多个数操作；但是01trie只能每次查询当前数与其他数的异或最大值，算是各有胜场了。

给上01trie的题：P4551 最长异或路径（XOR 异或 dfs 字典树 trie 贪心）_Jack_00_的博客-CSDN博客

完结撒花~