P3812 【模板】线性基 题解

· · 题解

线性基

线性基是一种基于异或操作的数据结构。
其总体思想是将已知的数中无用的数删除。

什么是无用的数

如果一个数 a 能被已给数据的另外几个数异或出来，我们就称之为无用的数，并不再对其进行任何操作。

此外，我们成其余的数（即不是无用的数）为线性基的基底，并把它们存起来。

实现

对于本题，我们观察异或的本质：不产生进位的二进制加法。也就是说，我们可以贪心从高到低枚举二进制位，判断每一位是否能为 1。

显然，直接模拟并不好操作。我们就引入线性基。

void add(int x){
    for(int i=50;i>=0;i--){//枚举每个二进制位
        if((x>>i)&1){//判断第i为是否为1
            if(s[i] == 0){//判断是否已经存在该位为1的数
                s[i] = x;
                return;
            }
            x ^= s[i];//将此位改为0，若x=0，则说明该数为无用的数
        }
    }
}

详细解释：

我们枚举每个二进制位，并查找有没有数能将这位变为 1（对于二进制，我们贪心从高位到低位枚举，枚举到的第一个目前位 0 的位即为该数贡献最大的位）。

对于我们遍历的每一个数 x，若它能将我们枚举的某个位变为 1，那么该数就不是无用的数（因为它能对答案产生贡献，即把答案的该位异或成 1）。

如果数 x 被遍历了所有二进制位但没有被存储，则我们很容易证得该数是一个无用的数（试试证明）。

回到此题

我们已经保证不会出现无用的数，那么我们只需要从高到低按二进制位枚举，如果该位有被存储，那么我们只需要判断异或次数是否会让答案变大。

int getmax(){
    int res=0;
    for(int i=50;i>=0;i--){
        res=max(res, res ^ s[i]);//如果该位没被存储，则数组初始化的0对异或操作不会有影响。
    }
    return res;
}

完整代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
int s[100],a[100];
void add(int x){
    for(int i=50;i>=0;i--){
        if((x>>i)&1){
            if(s[i] == 0){
                s[i] = x;
                return;
            }
            x ^= s[i];
        }
    }
}
int getmax(){
    int res=0;
    for(int i=50;i>=0;i--){
        res=max(res, res ^ s[i]);
    }
    return res;
}
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        add(a[i]);
    }
    cout<<getmax();
    return 0;
}