BZOJ 4269: 再见Xor [高斯消元 线性基]

时间：2021-06-10 08:35:52

4269: 再见Xor

Description

给定N个数，你可以在这些数中任意选一些数出来，每个数可以选任意多次，试求出你能选出的数的异或和的最大值和严格次大值。
我太愚蠢了连数组开小了以及$2^{31}$爆$int$都不造
 
线性基裸题啊....
#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <bitset>

using namespace std;

typedef long long ll;

const int N=1e5+,INF=1e9;

inline int read(){

    char c=getchar();int x=;

    while(c<''||c>''){c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x;

}

int n,p;

int a[N],bin[N];

void ini(){

    bin[]=;for(int i=;i<=;i++) bin[i]=bin[i-]<<;

}

int now;

void Gauss(int n){

    now=;

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

        int j=now;

        while(j<=n&&!(a[j]&bin[i])) j++;

        if(j==n+) continue;

        if(j!=now) swap(a[j],a[now]);

        for(int k=;k<=n;k++)

            if(k!=now&&(a[k]&bin[i])) a[k]^=a[now];

        now++;

    }

    now--;

}

int main(){

    freopen("in","r",stdin);

    n=read();

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

        int x=read();

        while(x==&&i<n) x=read(),i++;

        if(x!=) a[++p]=x;

    }

    ini();

    Gauss(p);

    int mx=;

    for(int i=;i<=now;i++) mx^=a[i];

    printf("%d %d\n",mx,mx^a[now]);

}

相关文章