题目描述

给定 $n$ 个整数（可能重复），现在需要从中挑选任意个整数，使得选出整数的异或和最大。

请问，这个异或和的最大可能值是多少。

数据范围

$$ 1 \le n \le 10^5 $$
$$ 0 \le S_i \le 2^{63} - 1 $$

样例

input:
3
5 2 8
output:
15

解法

此题，我们可以使用线性基解决

• 线性基的定义

对于一个数列 A 来说，P 是他的线性基当且仅当
1. A任意数字都能通过P中的一些数字异或出来
2. P只能异或出A中的数或A中的数能异或出来的东西
3. P中任意数都不能被P中其他数异或出来
4. P中数最高位不重复

由3容易得出
$$ P_i \oplus P_j \neq P_k \oplus P_l $$

所以，A中数可以异或出来的最大值就是P中数可以异或出来的最大值

// 1.已知线性基求最大值
int findmax(int *p, int len)
{
    sort(p + 1, p + len + 1, greater<int>());
    int v = 0;
    for(int i = 1; i <= len; i++)
        v = max(v, v ^ p[i]);
    return v;
}

这种看似贪心的做法为什么是对的呢？
让我们看一张图：

首先1一定要选，为什么呢？
我们知道一个常识，那就是大位压死小位(官大一级压死你)
1000000000 > 111111111
如果不选1那么以后再也没有一个数可以使得最高位为1了，那么结果一定更劣
然后，分别考虑，优先看最高位
当前数 $\oplus$ 最高位 = 0 不选， 否则选
写出来，就是简单的取max了~~

那么，如何求线性基呢？
为了满足4要求，我们要比较所有最高位，如果当前要插入的数最高位已经有了，就异或上这个有的数，重复直到没有再插入（0就不用了），容易证明符合123条件。

void add(int v)
{
    for(int i = 1; i <= cnt; i++)
        v = min(v, v ^ p[i]);

    if(v)
    {
        p[++cnt] = v;
        sort(p + 1, p + cnt + 1, greater<int>());
    }
}

注意long long,现在就可以给出代码了：

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
long long n, p[N], a[N], cnt;
void add(long long v)
{
    for(int i = 1; i <= cnt; i++)
        v = min(v, v ^ p[i]);

    if(v)
    {
        p[++cnt] = v;
        sort(p + 1, p + cnt + 1, greater<long long>());
    }
}
int main(void)
{
    cin >> n;
    for(int i = 1; i <= n; i++) scanf("%lld", a + i), add(a[i]);

    long long v = 0;
    for(int i = 1; i <= cnt; i++)
        v = max(v, v ^ p[i]);

    cout << v;
}