【学习笔记】线性基

原理

坑。

例题

P哥的桶

首先有一道很水的例题

题意

一共有 n 个数组,可以向某一个数组里增加一个数,或者询问区间内所有数组里数组可能的最大异或和。

思路

线性基套上一个线段树,可以学习一下基本插入和查询操作。

#include 
#define maxn 50001
#define maxl 32
#define ll long long
#define ls (p<<1)
#define rs (p<<1|1)
#define mid ((l+r)>>1)
using namespace std;
struct LB{
    ll a[maxl+1];
    void reset(){
        memset(a,0,sizeof(a));
    }
    void insert(ll t){
        for (int j=maxl;j>=0;j--){
            if (!t) return;
            if (!(t&(1ll<k||rR) return;
    if (l>=L&&r<=R){merge(temp,tree[p]);return;}
    query(l,mid,L,R,ls),query(mid+1,r,L,R,rs);
}
int main(){
    ios::sync_with_stdio(false);
    int n,m,op,k;ll v;
    cin>>m>>n;
    while(m--){
        cin>>op>>k>>v;
        if (op==1) update(1,n,k,v,1);
        else temp.reset(),query(1,n,k,v,1),cout<

最大XOR和路径

题意

在可能有重边自环的有向图里寻找一条从 1 到 $N$ 的路径,可以重复经过某些点或边,最大化经过的点权 XOR和。

思路

首先我们考虑任意一条从 1 到 $N$ 的简单路径。

由于可以重复经过一些点,也就是我们可以向外走一个环再回来。

发现从链上一点到环之间的路径经过两次对答案没有贡献,所以我们可以预处理出所有环的答案丢到线性基里贪心选取。

这种做法对一开始选取的简单路径没有要求,因为假设存在更优的路径,它和当前的这条路径形成的环也被加进了线性基里,如果选取了这个环,就相当于走了另外一条更优的路径。

代码
#include 
#define ll long long
#define maxn 50001
#define maxl 63
using namespace std;
struct LB{
    ll a[maxl+1];
    void insert(ll t){
        for (int j=maxl;j>=0;j--){
            if (!t) return;
            if (!(t&(1ll<=0;i--)
            if((x^a[i])>x) x^=a[i];
        return x;
    }
}K;
struct Edge{
    int to,next;
    ll val;
    Edge(int a=0,int b=0,ll c=0){
        to=a,next=b,val=c;
    }
}l[200100];
int head[maxn],vis[maxn],cnt,n,m;
ll dis[maxn];
void Add(int x,int y,ll z){
    l[++cnt]=Edge(y,head[x],z);
    head[x]=cnt;
}
void Dfs(int x,int f){
    vis[x]=1;
    for (int i=head[x];i;i=l[i].next){
        int v=l[i].to;
        if (v==f) continue;
        if (!vis[v]) dis[v]=dis[x]^l[i].val,Dfs(v,x);
        else K.insert(dis[x]^dis[v]^l[i].val);
    }
}
int main(){
    ios::sync_with_stdio(false);
    int n,m;cin>>n>>m;
    for (int i=1;i<=m;i++){
        int x,y;
        ll z;
        cin>>x>>y>>z;
        Add(x,y,z);
        Add(y,x,z);
    }
    Dfs(1,0);
    cout<

致谢

我的板子是从 Menci 那里学来的,感谢学长 qwq。

Show Comments