[学习笔记]我们追过的神奇异或（Trie树系列）

引言

刚学了\(Trie\)树，写篇博客巩固一下。

题目

首先安利一发\(Trie\)树模板

1、Phone List

2、The XOR largest pair

3、The xor-longest Path

4、Codechef REBXOR

第一题不难，但是我用的是暴力。

构造一棵\(Trie\)树，然后把字符串长度从大到小排序，然后按顺序插入。若在插入的时候\(Trie\)树结点一直不为空，那么该串为其的子串。

\(Code\ Below:\)

#include <bits/stdc++.h>
using namespace std;
int n,trie[100010][10],ans,tot;
char s[100010][15];
struct node{
    int len,id;
}l[100010];
void insert(int k){
    int len=strlen(s[k]),p=0,b=0;
    for(int i=0;i<len;i++){
        if(trie[p][s[k][i]-'0']==-1) {
            trie[p][s[k][i]-'0']=++tot;b=1;
        }
        p=trie[p][s[k][i]-'0'];
    }
    if(b==0) ans=1;
}
bool cmp(node a,node b){
    return a.len>b.len;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--){
        memset(trie,-1,sizeof(trie));
        scanf("%d",&n);
        ans=0;tot=0;
        for(int i=1;i<=n;i++){
            scanf("%s",s[i]);
            l[i].len=strlen(s[i]);l[i].id=i;
        }
        sort(l+1,l+n+1,cmp);
        for(int i=1;i<=n;i++){
            if(ans==0) insert(l[i].id);
        }
        if(ans==1) printf("NO\n");
        else printf("YES\n");
    }
    return 0;
}

第二题构造一棵\(Trie\)树，然后根据异或的运算规则，尽量当前的值与结点的值不一样。
此题是二三题的基础。

\(Code\ Below:\)

#include <cstdio>
int n,trie[100010*31][2],ans=0,val,tot=0;
int max(int a,int b){return a>b?a:b;}
int search(int x){
    int p=0,num=0,c;
    for(int i=31;i>=0;i--){
        c=(x>>i)&1;
        if(trie[p][c^1])
            p=trie[p][c^1],num=num<<1|1;
        else p=trie[p][c],num=num<<1;
    }
    return num;
}
void insert(int x){
    int p=0,c;
    for(int i=31;i>=0;i--){
        c=(x>>i)&1;
        if(!trie[p][c]) trie[p][c]=++tot;
        p=trie[p][c];
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&val);
        ans=max(ans,search(val));
        insert(val);
    }
    printf("%d\n",ans);
    return 0;
}

定义前缀异或和\(sum[1..i]=a[1]\)^\(...\)^\(a[i]\),\(v[i..j]=a[i]\)^\(a[i+1]\)^\(...\)^\(a[j]\),则\(v[i..j]=sum[1..i] * sum[1..j]\)

由于\(a^a=0,0^a=a,\)所以异或两次值不变。

那么预处理出树上前缀异或和（即到根的前缀异或和），跑一遍\(The\ XOR\ largest\ pair\)

\(Code\ Below:\)

#include <cstdio>
int n,trie[100010*31][2],ans=0,a[100010],val,tot=0,t=0,head[100010];
int max(int a,int b){return a>b?a:b;}
struct node{
    int to,val,next;
}e[100010*2];
void add(int x,int y,int w){
    e[++t].to=y;
    e[t].val=w;
    e[t].next=head[x];
    head[x]=t;
}
void dfs(int x,int fa,int now){
    a[x]=now;
    for(int i=head[x];i;i=e[i].next){
        int y=e[i].to;
        if(y==fa) continue;
        dfs(y,x,now^e[i].val);
    }
}
int search(int x){
    int p=0,num=0,c;
    for(int i=31;i>=0;i--){
        c=(x>>i)&1;
        if(trie[p][c^1])
            p=trie[p][c^1],num=num<<1|1;
        else p=trie[p][c],num=num<<1;
    }
    return num;
}
void insert(int x){
    int p=0,c;
    for(int i=31;i>=0;i--){
        c=(x>>i)&1;
        if(!trie[p][c]) trie[p][c]=++tot;
        p=trie[p][c];
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<n;i++){
        int x,y,w;
        scanf("%d%d%d",&x,&y,&w);
        add(x,y,w);add(y,x,w);
    }
    dfs(1,1,0);
    for(int i=1;i<=n;i++){
        ans=max(ans,search(a[i]));
        insert(a[i]);
    }
    printf("%d\n",ans);
    return 0;
}

第四题预处理出前缀异或和和后缀异或和，然后用\(O(n)\)的时间求最大值

\(Code\ Below:\)

#include <cstdio>
int n,trie[400010*31][2],ans=0,val,tot=0,a[100010],l[400010],r[400010];
int max(int a,int b){return a>b?a:b;}
int search(int x){
    int p=0,num=0,c;
    for(int i=31;i>=0;i--){
        c=(x>>i)&1;
        if(trie[p][c^1])
            p=trie[p][c^1],num=num<<1|1;
        else p=trie[p][c],num=num<<1;
    }
    return num;
}
void insert(int x){
    int p=0,c;
    for(int i=31;i>=0;i--){
        c=(x>>i)&1;
        if(!trie[p][c]) trie[p][c]=++tot;
        p=trie[p][c];
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    int now=0;insert(now);
    for(int i=1;i<=n;i++){
        now^=a[i];
        l[i]=max(l[i-1],search(now));
        insert(now);
    }
    now=0;insert(now);
    for(int i=n;i>=1;i--){
        now^=a[i];
        r[i]=max(r[i+1],search(now));
        insert(now);
    }
    for(int i=1;i<n;i++){
        ans=max(ans,l[i]+r[i+1]);
    }
    printf("%d\n",ans);
    return 0;
}

[学习笔记]我们追过的神奇异或（Trie树系列）

原文：https://www.cnblogs.com/owencodeisking/p/9735350.html