线性基（模板） LUOGU 3812

解题思路

线性基，是构造出一组数：ax,ax-1….a1,ax的二进制最高位为x。这些数字能异或和可以表示原来所有数的异或和。其实相当于一个高斯消元的过程。所以我们按位枚举，如果这一位曾经没数，就直接加入，如果有数，我们就让这两个数异或起来，进而继续表示其他的数。要求最大值则按位贪心即可。

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#define LL long long

using namespace std;

const int MAXN = 70;

int n;

LL ans;

LL b[MAXN];

int main(){

    scanf("%d",&n);

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

        LL u;scanf("%lld",&u);

        for(register int j=63;~j;j--)

            if(u&(1ll<<j)){

                if(!b[j]) {b[j]=u;break;}

                else u^=b[j];

            }

    }

    for(register int i=63;i>=1;i--)

        if((ans^b[i])>ans) ans^=b[i];

    printf("%lld",ans);

    return 0;

}

巴特西

线性基（模板） LUOGU 3812

解题思路

代码

最新文章

热门文章