「LibreOJ」#6060「2017 山东一轮集训 Day1 / SDWC2018 Day1」Set – 题解

主要思路

神仙题。

发现 \(x_1 \oplus x_2 = xorsum\)，所以我们尽量把 \(xorsum\) 的位分给 \(x_2\)。如果 \(xorsum\) 的某位为 \(1\)，那就直接给 \(x_2\) 就好；如果为 \(0\) ，那么有 \(0, 0\) 和 \(1, 1\) 两种情况。所以，我们构造线性基时，通过优先考虑为更高的 \(0\) 的位可以使得答案更大（我们考虑用线性基求最大异或和的过程，优先插入权更大的位置）。

代码

// LOJ6060.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e5 + 200;

typedef long long ll;

int n, tot;
ll ai[MAX_N], tb[MAX_N], bi[MAX_N];

void insert(ll x)
{
    for (int i = 1; i <= tot; i++)
        if (x & (1LL << tb[i]))
        {
            if (bi[i] == 0)
            {
                bi[i] = x;
                break;
            }
            x ^= bi[i];
        }
}

int main()
{
    scanf("%d", &n);
    ll xorsum = 0;
    for (int i = 1; i <= n; i++)
        scanf("%lld", &ai[i]), xorsum ^= ai[i];
    for (int i = 62; i >= 0; i--)
        if (!(xorsum & (1LL << i)))
            tb[++tot] = i;
    for (int i = 62; i >= 0; i--)
        if (xorsum & (1LL << i))
            tb[++tot] = i;
    for (int i = 1; i <= n; i++)
        insert(ai[i]);
    ll x2 = 0;
    for (int i = 1; i <= tot; i++)
        if (!(x2 & (1LL << tb[i])))
            x2 ^= bi[i];
    printf("%lld\n", xorsum ^ x2);
    return 0;
}