第一行为一个整数n，表示元素个数
第二行一行包含n个整数，分别代表序列中的元素
第三行为一个整数Q，表示询问次数
接下来Q行，每行两个数x,y，含义如题所示
输出Q行，若x可以变换为y，输出“YES”，否则输出“NO”
5 1 2 3 4 5 3 6 7 2 1 3 8
YES YES NO
对于(6,7)来说，6可以先和3异或，再和2异或
对于(2,1)来说，2可以和3异或
对于(3,8)来说，3不论如何都不能变换为8
对于100%的数据，n,Q<=105
保证所有运算均在int范围内
// x ^ z = y z = x ^ y // 线性基模板题 #include<bits/stdc++.h> using namespace std; const int MAXN = 32; int num[MAXN]; int insert(int x) { for (int i = 31; i >= 0; i--) { if ((x >> i) & 1) { if (!num[i]) { num[i] = x; return 1; } x ^= num[i]; } } return 0; } bool query(int x) { for (int i = 31; i >= 0; i--) { if (((x >> i) & 1) && num[i]) x ^= num[i]; } return !x; } int main() { int n, x, y, q; cin >> n; for (int i = 1; i <= n; i++) { cin >> x; insert(x); } cin >> q; while (q--) { cin >> x >> y; cout << (query(x ^ y) ? "YES" : "NO") << endl; } return 0; }
原文：https://www.cnblogs.com/HighLights/p/13364360.html