本人蒟蒻如有错误还请指出打牛客时盯了一题两个小时毫无头绪一头雾水一看题解线性基人麻了于是就有了这篇文章...线性基的概念首先线性基是什么有什么用线性基是一个数的集合取线性基中若干个数异或起来可以得到原序列中的任意一个数。线性基的构造其构造方法为从最高位往低位枚举用表示为线性基中最高位为的数当一个数二进制下第位为1时如果不存在就对赋值否则将这个数异或上。如果这个数中途被异或成0了那么说明这个数可以被线性基中的一些数异或得到则不需要将这个数插到线性基中。具体则表示为这样代码则表示为void insert(int x) { for (int i 60; i 0; i--) if ((x i) 1) { if (!d[i]) { d[i] x; return; } x ^ d[i]; } zero 1; }注此处zero用于记录是否有元素无法插入到线性基中在下文求异或最小值处提到。线性基的性质性质一原序列中的任意一个数都可以通过线性基中的若干个数异或表示。因为如果无法表示那么他必然可以加到线性基中。性质二线性基中任意数异或起来不可能为0。假设^^0则^可以由^表示由性质一可知无法被插到线性基中。性质三在满足性质一条件下线性基中的数的个数最少。如果我们多插入了一个数x而x又可以由原线性基中的一些数异或得到那么这个数显然是多余的。线性基的作用求异或最大值求异或最大值本质上是一个贪心的过程。从最高位往低位枚举如果该位线性基存在并且异或后结果变大则异或上该位的线性基。int qmax() { int res 0; for (int i 60; i 0; i--) if ((res ^ d[i]) res) res ^ d[i]; return res; }求异或最小值由性质二可知线性基无法表示0因此我们要分类讨论。如果一个数无法被插入到线性基中则说明他可以被线性基中的元素表示即存在一些数的异或值为0这一点只需要用一个变量zero在插入的时候记录一下是否变成0即无法插入到线性基中即可。如果不存在0异或的异或值那么最小的线性基就是答案因为最小的线性基最高位最小值最小。int qmin() { if (zero) return 0; for (int i 0; i 60; i) if (d[i]) return d[i]; return 0; }求第k小的异或值由于线性基无法存0因此当存在0时k要先减1。我们要先对线性基做一个处理对于每一位从到枚举每一位如果存在并且的第位为1那么让的异或上。处理完后线性基中的数应该长这样最后再把新的线性基的数加到新数组p中接下来找第k小的值时只需要将k二进制拆分如果k的第位为1就异或上。注意不是异或上原线性基中元素。int query(int k) { k - zero; if (!k) return 0; for (int i 60; i 0; i--) for (int j i - 1; j 0; j--) if (d[i] (1LL j)) d[i] ^ d[j]; for (int i 0; i 60; i) if (d[i]) p[cnt] d[i]; if (k (1LL cnt)) return -1; int res 0; for (int i 0; i cnt; i) if ((k i) 1) res ^ p[i]; return res; }判断一个数是否能被线性基中的一些数异或得到只需要尝试将这个数插入到线性基中如果这个数最后变成0了即这个数不能插入到线性基中说明这个数可以被线性基中的一些数异或得到否则不能。int check(int x) { for (int i 60; i 0; i--) { if ((x i) 1) x ^ d[i]; if (x 0) return 1; } return 0; }查询一个数可以由原序列中的哪些数异或得到线性基一个非常强大的作用是可以直接找出一个数由原序列中的哪些数异或得到。这一步查询本质上是一个哈希的过程。在线性基中插入元素时我们可以同时存储这一位的哈希值当一个数由这一位异或而来时我们只需要异或上这一位的哈希值。最后再对这个哈希值做一个解码。这样我们就可以找到由哪些数异或而来了。bool insert(int val, int idx) { ull cul 0; for (int i 30; i 0; i--) if ((val i) 1) { if (!d[i]) { d[i] val; mask[i] cul | (1ull rep.size()); rep.push_back(idx); return true; } val ^ d[i]; cul ^ mask[i]; } zero 1; return false; } pairbool, ull check(int val) { ull res 0; for (int i 30; i 0; i--) { if ((val i) 1) { if (!d[i]) return {false, 0}; val ^ d[i]; res ^ mask[i]; } } return {true, res}; } vectorint choose(ull msk) { vectorint res; for (int i 0; i rep.size(); i) if ((msk i) 1) res.push_back(rep[i]); return res; }模板int zero 0, cnt 0; int d[61], p[61]; ull mask[61]; vectorint rep; bool insert(int val, int idx) { ull cul 0; for (int i 30; i 0; i--) if ((val i) 1) { if (!d[i]) { d[i] val; mask[i] cul | (1ull rep.size()); rep.push_back(idx); return true; } val ^ d[i]; cul ^ mask[i]; } zero 1; return false; } int qmax() { int res 0; for (int i 30; i 0; i--) if ((res ^ d[i]) res) res ^ d[i]; return res; } int qmin() { if (zero) return 0; for (int i 0; i 30; i) if (d[i]) return d[i]; return 0; } void rebuild() { for (int i 30; i 0; i--) for (int j i - 1; j 0; j--) if (d[i] (1LL j)) d[i] ^ d[j]; for (int i 0; i 30; i) if (d[i]) p[cnt] d[i]; } int query(int k) { k - zero; if (!k) return 0; rebuild(); if (k (1LL cnt)) return -1; int res 0; for (int i 0; i cnt; i) if ((k i) 1) res ^ p[i]; return res; } pairbool, ull check(int val) { ull res 0; for (int i 30; i 0; i--) { if ((val i) 1) { if (!d[i]) return {false, 0}; val ^ d[i]; res ^ mask[i]; } } return {true, res}; } vectorint choose(ull msk) { vectorint res; for (int i 0; i rep.size(); i) if ((msk i) 1) res.push_back(rep[i]); return res; } void clear() { for (int i 0; i 30; i) d[i] p[i] mask[i] 0; cnt 0; zero 0; rep.clear(); }题目原题链接回到这道我两个小时没有任何头绪的题我去这不一眼秒题目大意有两个长度为n的数组和构造一个数组等于或者使得^^...^等于0思路先让等于如果异或结果已经为0那么答案就为数组如果要让替换成那就异或上^。也就是说令原先数组的异或结果为如果为0答案就为数组否则就要异或上若干个^使得最后的结果为0。那么只需要找出一些^的位置使得异或结果为即可。代码void solve() { clear(); cin n; int t 0; for (int i 1; i n; i) { cin a[i]; t ^ a[i]; st[i] 0; } for (int i 1; i n; i) { cin b[i]; if ((a[i] ^ b[i]) 0) continue; insert(a[i] ^ b[i], i); } if (t 0) { for (int i 1; i n; i) cout a[i] ; cout endl; return; } auto [flag, msk] check(t); if (!flag) { cout -1 endl; return; } vectorint ans choose(msk); for (int x : ans) st[x] 1; for (int i 1; i n; i) if (st[i]) cout b[i] ; else cout a[i] ; cout endl; }参考文献线性基详解题解