先把所有的数异或起来 得到sum 然后sum有一些位是1一些位是0 是0的位表示所有数里面有这位的数是偶数个
则无论怎么划分数 这一位对最终的答案都是不会有贡献的 因为偶数=偶数+偶数/奇数+奇数
所以我们把所有数直接&sum不管那些没有贡献的位 再一个个插入作线性基
拿出一个最高位的1给A 那么我们现在要做的就是尽量保证A剩下的高位能不是1就别是1 这样得到的答案是最优的
#include<bits/stdc++.h> using namespace std; typedef long long ll; ll a[65]; ll num[100005]; ll x; int main() { int TNT; scanf("%d", &TNT); while (TNT--) { memset(a, 0, sizeof(a)); int n; ll sum = 0; scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%lld", &x); num[i] = x; sum ^= x; } for (int i = 1; i <= n; i++) { num[i] &= sum; } for (int i = 1; i <= n; i++) { for (int j = 62; j >= 0; j--) { if (num[i] & (1ll << j)) { if (!a[j]) { a[j] = num[i]; break; } else { num[i] ^= a[j]; } } } } int aim = -1; ll aimx = 0; for (int i = 62; i >= 0; i--) { if (sum & (1ll << i)) { aim = i; aimx = a[i]; break; } } for (int i = aim - 1; i >= 0; i--) { if (aimx & (1ll << i)) { aimx ^= a[i]; } } ll ans = aimx - (aimx ^ sum); printf("%lld\n", ans); } }
Petrozavodsk Winter Training Camp 2018 Jagiellonian U Contest Problem A. XOR