题目链接：
Problem - 1870B - Codeforces
最佳思路：
#include <iostream> #include <vector> using namespace std; int main() { int t; cin >> t; while (t--) { int n, m; cin >> n >> m; vector<int> a(n); unsigned int O = 0, base = 0; for (auto& x : a) { cin >> x; base ^= x; } for (int j = 0; j < m; j++) { int b; cin >> b; O |= b; } int after = 0; for (auto x : a) after ^= (x | O); int mn, mx; if (n & 1) { mn = base; mx = after; } else { mn = after; mx = base; } cout << mn << ' ' << mx << '\n'; } return 0; }这道题对于我这样对位运算不熟悉可太难了
我花了接近2h去逐步学习思路。。
思路：
这两种位运算的方法就不说了，比较基础
OR （|）运算有两个性质：
- 幂等：
y | y = y（同一个数 OR 两遍不变） - 结合：
(a|b)|c = a|(b|c)
所以无论你选多少个 b、按什么顺序，最终每个a[i]都等于a[i] | V，其中V = 你选中的那些 b 的按位或。
- 一个都不选 → V = 0（等于没操作）
- 选一堆 → V 是它们的 OR
于是问题变成：选一个 V，让(a1|V) ^ (a2|V) ^ ... ^ (an|V)最小 / 最大。
然后对答案x的每一个进制位进行思考：
先建立两个前提
前提 A：异或 = 二进制下"逐位无进位加法，对 2 取模"
异或不是把整个数混在一起算的，它是每一位各算各的。比如：
plaintext
5 ^ 3 = 101 ^ 011 = 110 = 6每一位独立：第 0 位 1^1=0，第 1 位 0^1=1，第 2 位 1^0=1。没有进位，位与位之间零交流。 这是"按位独立"的物理基础。
前提 B：k 个 1 异或 = k 的奇偶
1 ^ 1 = 0，1 ^ 1 ^ 1 = 1，1 ^ 1 ^ 1 ^ 1 = 0……
规律：偶数个 1 异或得 0，奇数个 1 异或得 1。因为每两个 1 凑一对抵消（1^1=0），最后剩下一个 1 还是全抵消，就看个数是奇是偶。
现在看 x 的某一位
设整个数组第 p 位（随便哪一位）有k个数是 1，剩下 n-k 个是 0。
plaintext
x 的第 p 位 = a1 的p位 ^ a2 的p位 ^ ... ^ an 的p位 = (k 个 1) ^ (n-k 个 0) = 1 ^ 1 ^ ... ^ 1 （共 k 个） = k 是奇数 ? 1 : 00 异或任何数都不改变它，所以那 n-k 个 0 可以直接扔掉
0^1 = 1 0^0 = 0
就剩 k 个 1 互异或，结果 = k 的奇偶。这就是 k mod 2。
操作之后，这一位变什么
操作是a[i] = a[i] | b[j]，只影响被选中的 b 里是 1 的那些位。
1 | 0 = 1 ;1 | 1 = 1;0 | 0 = 0; 0 | 1 = 1;
对第 p 位，只有两种情况：
情况 A：V 的第 p 位 = 0
plaintext
a[i] 的 p 位 | 0 = a[i] 的 p 位 （0 和任何数 OR 都不变）所以 n 个数这一位原封不动，还是 k 个 1，异或还是 k mod 2。等于白操作。
情况 B：V 的第 p 位 = 1
plaintext
a[i] 的 p 位 | 1 = 1 （1 和任何数 OR 都是 1）注意这个"对每个 i"——所有 n 个数这一位都被强行拉成 1，不管原来是 0 还是 1。
1 | 0 = 1 ;1 | 1 = 1;
于是这一位变成 n 个 1 互异或 =n mod 2。
由于V 的第 p 位 = 1，导致所有的a[i]该位都变成了1，所以要对n判断奇偶；
之后判断：单独V中的“1”比较"置"和"不置"谁大
把这两种结果摆一起，比大小。而"变大变小"，取决于 n 是奇是偶，因为n mod 2在两种情况下的值固定了。
情况一：n 是奇数
n 是奇数 →n mod 2 = 1，所以置位后这一位一定是 1。
那"不置"时这一位是k mod 2，可能是 0 也可能是 1：
- k 是偶：不置 = 0，置 = 1 →
0 → 1，变大了✅ - k 是奇：不置 = 1，置 = 1 →
1 → 1，没变➖
两种情况加起来：置位，这一位只会"变大"或"不变"，绝不会变小。
既然每一位置 1 都"稳赚不赔"，那想得到最大的 x，就把每一位都置 1——也就是 V 取尽可能大，把所有 b 都 OR 上（V = O）。
想要V种的1最多，方法就是全要：缺少的1会补充，重复的1也不影响
反过来，想得到最小的 x，就一位都别置（V = 0，保持原样）。
所以：
- min = 不操作 = base（原始的 x）
- max = 全置 = 每个 a 都 OR 上 O，再异或
情况二：n 是偶数
n 是偶数 →n mod 2 = 0，所以置位后这一位一定是 0。
- k 是奇：不置 = 1，置 = 0 →
1 → 0，变小了⬇️ - k 是偶：不置 = 0，置 = 0 →
0 → 0，没变➖
加起来：置位，这一位只会"变小"或"不变"，绝不会变大。
所以情况和奇数完全反过来：
- 想最大 → 一位别置（V=0）→max = base
- 想最小 → 全置（V=O）→min = 每个 a | O 再异或
对于V的置位 就如同一个开关：放0 那我只要判断k的奇偶数；放1 就需要判断n的奇偶
最后会发现极值就在(a1|V) ^ (a2|V) ^ ... ^ (an|V)与(a1) ^ (a2) ^ ... ^ (an)之中
其中V是b全选状态
我认为这题最妙的地方在于：处处都在讨论第k位，但最终没有任何对单独每一位的操作
for (auto& x : a) { cin >> x; base ^= x; }这句先把最开始的结果算出来，第k位该是1是1，该是0是0
但转折在于
如果n是奇数 V的k位的1可以将它的0转化为1.1则保持不变，使其尽量大
V并非想k是0是0，是1是1。但我们b全选可以使这种效果尽量最大化
反之一样
太通透了
