Trie学习笔记

Trie(字典树)

基本数据结构

实际是:对于每个字符串组的每一个不同前缀建立节点

基本代码

void Insert(char *s,int p){

    int now=0;

    int l=strlen(s);

    rep(i,0,l-1){

        int k=s[i]-'a';

        if(!nxt[now][k]) nxt[now][k]=++ncnt;

        now=nxt[now][k];

    }

}

不得不说,结构非常简单

但它有很多妙用

--->Xor Sum

典型数字trie

如何求出最大异或?

从最高位开始,能不同则不同,在建立的trie树上跑就行

const int N=100000,K=50;

int n,m;

int nxt[N*32][2];

int cnt;

void Insert(int x){

    int now=1;

    drep(i,31,0) {

        int y=(x&(1<<i))>0;

        if(!nxt[now][y]) nxt[now][y]=++cnt;

        now=nxt[now][y];

    }

}

int Que(int x){

    int now=1,ans=0;

    drep(i,31,0) {

        int y=(x&(1<<i))>0;

        if(nxt[now][!y]) ans|=(!y)<<i,now=nxt[now][!y];

        else ans|=y<<i,now=nxt[now][y];

    }

    return ans;

}

int main(){

    rep(kase,1,rd()){

        cnt=1; memset(nxt,0,sizeof nxt);

        n=rd(),m=rd();

        rep(i,1,n) Insert(rd());

        printf("Case #%d:\n",kase);

        rep(i,1,m) {

            int ans=Que(rd());

            printf("%d\n",ans);

        }

    }

}

巴特西

Trie学习笔记

Trie(字典树)

--->Xor Sum

最新文章

热门文章