SGU-275. To xor or not to xor（线性基模板题）

博主链接

题目链接

题意：

给你n个数，求最大异或值

题解：

先求出线性基，用线性基求这组数出的最大值：从高往低扫，若异或上使答案变大，则异或。

代码：

#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int maxn=20010;
struct  Linear_Basis{
    ll b[63],nb[63],tot; //b为线性基 nb用来求第K小异或值 tot为nb元素个数
    void Init(){    //初始化
        tot=0;
        memset(b,0,sizeof(b));
        memset(nb,0,sizeof(nb));
    }
    bool Ins(ll  x){ //插入
        for(int i=62;i>=0;i--){
            if(x&(1ll<<i)){
                if(!b[i]){
                    b[i]=x;
                    break;
                }
                x^=b[i];
            }
        }
        return x>0;
    }
    ll Max(ll x){   //求最大值 初始值x没要求就是0
        ll res=x;
        for(int i=62;i>=0;i--){
            res=max(res,res^b[i]);
        }
        return res;
    }
    ll Min(ll x){   //求最小值 初始值x没要求就是0
        ll res=x;
        for(int i=0;i<=62;i++){
            if(b[i])res^=b[i];
        }
        return res;
    }
    ll Rebuild(ll x){   //第K大
        for(int i=0;i<=62;i--){
            for(int j=i-1;j>=0;j--){
                if(b[i]&(1ll<<j))b[i]^=b[j];
            }
        }
        for(int i=0;i<=62;i++){
            if(b[i])nb[tot++]=b[i];
        }
    }
    ll Kth_Max(ll k){
        ll res=0;
        for(int i=62;i>=0;i--){
            if(k&(1ll<<i))res^=nb[i];
        }
        return res;
    }
}LB;
int main(){
 // freopen("input.txt","r",stdin);
    int n;
    ll a;
    scanf("%d",&n);
    LB.Init();
    for(int i=0;i<n;i++){
        scanf("%lld",&a);
        LB.Ins(a);
    }
    printf("%lld\n",LB.Max(0));
    return 0;
}