Petrozavodsk Winter Training Camp 2018 Jagiellonian U Contest Problem A. XOR

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

先把所有的数异或起来得到sum 然后sum有一些位是1一些位是0 是0的位表示所有数里面有这位的数是偶数个

则无论怎么划分数这一位对最终的答案都是不会有贡献的因为偶数=偶数+偶数/奇数+奇数

所以我们把所有数直接&sum不管那些没有贡献的位再一个个插入作线性基

拿出一个最高位的1给A 那么我们现在要做的就是尽量保证A剩下的高位能不是1就别是1 这样得到的答案是最优的

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

ll a[];

ll num[];

ll x;

int main() {

        int TNT;

        scanf("%d", &TNT);

        while (TNT--) {

                memset(a, , sizeof(a));

                int n;

                ll sum = ;

                scanf("%d", &n);

                for (int i = ; i <= n; i++) {

                        scanf("%lld", &x);

                        num[i] = x;

                        sum ^= x;

                }

                for (int i = ; i <= n; i++) {

                        num[i] &= sum;

                }

                for (int i = ; i <= n; i++) {

                        for (int j = ; j >= ; j--) {

                                if (num[i] & (1ll << j)) {

                                        if (!a[j]) {

                                                a[j] = num[i];

                                                break;

                                        } else {

                                                num[i] ^= a[j];

                                        }

                                }

                        }

                }

                int aim = -;

                ll aimx = ;

                for (int i = ; i >= ; i--) {

                        if (sum & (1ll << i)) {

                                aim = i;

                                aimx = a[i];

                                break;

                        }

                }

                for (int i = aim - ; i >= ; i--) {

                        if (aimx & (1ll << i)) {

                                aimx ^= a[i];

                        }

                }

                ll ans = aimx - (aimx ^ sum);

                printf("%lld\n", ans);

        }

}