题目描述

Description

给定N个数，你可以在这些数中任意选一些数出来，每个数可以选任意多次，试求出你能选出的数的异或和的最大值和严格次大值。

Input

第一行一个正整数N。
接下来一行N个非负整数。

Output

一行，包含两个数，最大值和次大值。

Sample Input

3
3 5 6

Sample Output

6 5 

HINT

100% ： N <= 100000, 保证N个数不全是0，而且在int范围内

题目分析：

高斯消元求出线性基 然后贪心的选数就可以了 次大值的话就干掉最小的线性基

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,tot;
int a[102000];
int ans;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1<<30;i;i>>=1)
    {
        for(int j=++tot;j<=n;j++) 
            if(a[j]&i) 
            {
                swap(a[tot],a[j]);
                break;
            }
        if(!(a[tot]&i)) 
        {
            tot--;
            continue;
        }
        for(int j=1;j<=n;j++)
            if(j!=tot&&(a[j]&i)) a[j]^=a[tot];
    }
    for(int i=1;i<=tot;i++) if(ans^a[i]>ans) ans^=a[i];
    printf("%d %d",ans,ans^a[tot]);
    return 0;
}