P3812 【模板】线性基

佚名 6年前 (2019-04-19) 随笔 775人围观抢沙发百度已收录

题目背景

这是一道模板题。

题目描述

给定n个整数（数字可能重复），求在这些数中选取任意个，使得他们的异或和最大。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

输入输出格式

输入格式：

第一行一个数n，表示元素个数
接下来一行n个数
输出格式：
仅一行，表示答案。

输入输出样例

输入样例#1：

2
1 1
输出样例#1：

说明

\(1≤n≤50,0≤Si≤250\)

代码

线性基构造
\(\circ\)逆序枚举 \(t\)所有为 \(1\)的二进制位 \(j= L\to1\)
\(\qquad \circ\)如果 \(a_j\ne 0,t=t\,xor\,a_j\)
\(\qquad \circ\)如果 \(a_j\ = 0\)则
\(\qquad\qquad \circ\)枚举 \(k\in \left[ 0\to j\right),t\)的第 \(k\)位为 \(1\) \(，t =t\,xor\,a_k\)
\(\qquad\qquad \circ\)枚举 \(k\in \left(j\to L\right],t\)的第 \(k\)位为 \(1\) \(，a_k =a_k\,xor\,t\)
最大值为 \(xor sum\,a_i\)

#include<bits/stdc++.h>
using namespace std;
const int maxl=60;
long long ans=0;
struct LinearBasics
{
    long long a[maxl+1];
    LinearBasics()
    {
        memset(a,0,sizeof(a));
    }
    void insert(long long t)
    {
        for(int j=maxl;j>=0;j--)
        {
            if(!(t&(1ll<<j)))continue;
            if(a[j])t^=a[j];
            else
            {
                for(int k=0;k<j;k++)if(t&(1ll<<k))t^=a[k];
                for(int k=j+1;k<=maxl+1;k++)if(a[k]&(1ll<<j))a[k]^=t;
                a[j]=t;
                return;
            }
        }
    }
    long long querymax()
    {
        long long res=0;
        for(int i=0;i<=maxl;i++)res^=a[i];
        return res;
    }
}lb;
inline long long read()
{
    long long x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x*f;
}
int main()
{
    int n=read();
    for(int i=1;i<=n;i++)
    lb.insert(read());
    printf("%lld",lb.querymax());
    return 0;
}