字典树

昨天的比赛被一道字典树水题卡住了,太小看它了

STL实现字典树
少用指针保平安

#include "cstdio"
#include "iostream"
#include "algorithm"
#include "string"
#include "cstring"
#include "queue"
#include "cmath"
#include "vector"
#include "map"
#include "stdlib.h"
#include "set"
#define mj
#define db double
#define ll long long
using  namespace std;
const int N=1e6+5;
const int mod=1e9+7;
const ll inf=1e16+10;
char s[1002][100];
char t[100];
char e;
string f;
map<string,int> m;
int cnt=0;
int main()
{
    while(1){
        while((e=getchar())!='\n'){
            cnt=0;
            f+=e;
            m[f]++;
        }
        cnt++;
        f="";
        if(cnt==2) break;
    }
    while(scanf("%s",t)==1){
        f=t;
        printf("%d\n",m[f]);
    }
}

01字典树
http://blog.csdn.net/guhaiteng/article/details/52191831
Note:经常有区间异或和的题目:比如求[l,r]的异或和
由X xor X = 0 ; 0 xor Y = Y;所有【l,r】 = 【1,r】 XOR 【1,l - 1】
这样在一颗加入了r 前的所有前缀异或和的01字典树上查找【1,r】就能得到以r为右边界的最大异或和
HDU5536

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn  = 1e4+11;
struct Trie{
    int ch[maxn<<5][2],sz[maxn<<5],val[maxn<<5],tot,root;
    void init(){
        ch[0][0]=ch[0][1]=0;
        tot=1;root=0;
    }
    void insert(int x){
        int now=root;
        for(int k = 30; k >= 0; k--){
            int c=((x>>k)&1);
            if(!ch[now][c]){
                ch[tot][0]=ch[tot][1]=0;
                val[tot]=0;sz[tot]=0;
                ch[now][c]=tot++;
            }
            now=ch[now][c];
            sz[now]++;
        }
        val[now]=x;
    }
    void update(int x,int d){
        int now=root;
        for(int k = 30; k >= 0; k--){
            int c=((x>>k)&1);
            now=ch[now][c];
            sz[now]+=d;//NOTE!!
        }
        //val[now]+=d;
    } 
    int query(int x){
        int now=root;
        for(int k = 30; k >= 0; k--){
            int c=((x>>k)&1);
            if(ch[now][c^1]&&sz[ch[now][c^1]]) now=ch[now][c^1];
            else now=ch[now][c]; 
        }
        return x^val[now];
    }
}trie;
int n,a[maxn];
int main(){
    int T; scanf("%d",&T);
    while(T--){
        trie.init();
        scanf("%d",&n);
        for(int i = 0; i < n; i++){
            scanf("%d",&a[i]);
        }
        for(int i = 0; i < n; i++){
            trie.insert(a[i]);
        }
        int ans=0;
        for(int i = 0; i < n; i++){
            trie.update(a[i],-1);
            for(int j = i+1; j < n; j++){
                trie.update(a[j],-1);
                ans=max(ans,trie.query(a[i]+a[j]));
                trie.update(a[j],1);
            }
            trie.update(a[i],1);
        }
        printf("%d\n",ans);
    }
    return 0;
}

BZOJ4260
按道理可以AC的,然而RTE

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 1e3+5;
int n,ans,a[maxn],xxor[maxn],xxxor[maxn][maxn];
int main(){
    while(scanf("%d",&n)!=EOF){
//        trie.init();
        for(int i = 0; i < n; i++){
            scanf("%d",&a[i]);
//            trie.insert(a[i]);
        }
        xxor[0]=a[0];
        for(int i = 1; i < n; i++){
            xxor[i]=a[i];
            xxor[i]^=xxor[i-1];
        }
        for(int i = 0; i < n; i++){
            xxxor[i][i]=a[i];
            for(int j = i+1; j < n; j++){
                xxxor[i][j]=xxor[j]^xxor[i-1];
            }
        }
        int ans=0;
        for(int l1 = 0; l1 < n; l1++){
            for(int r1=l1; r1 < n; r1++){
                for(int l2=r1+1; l2 < n; l2++){
                    for(int r2=l2; r2 < n; r2++){
                        ans=max(ans,xxxor[l1][r1]+xxxor[l2][r2]);
                    }
                }
            }
        }
        printf("%d\n",n==1?a[0]:ans);
    }
    return 0;
}

UVA11732

#include<bits/stdc++.h>
const int maxn = 4e6+11;//MaxnL
const int kd = 80;//kuandu
char s[10000];
struct Trie{
    int son[maxn][kd],end[maxn],L,root,dend[maxn];
    long long ans;
    int newnode(){
        dend[L]=end[L]=0;
        memset(son[L],-1,sizeof(son[L]));
        return L++;
    }
    void init(){
        L=ans=0;
        root=newnode();
    }
    void insert(char str[]){
        ans+=end[root];
        end[root]++;
        int now=root,index;
        for(int i = 0; str[i]; i++){
            index=str[i]-'0';
            if(son[now][index]==-1){
                son[now][index]=newnode();
            }
            now=son[now][index];
            ans+=2*end[now];
            end[now]++;
        }
        ans+=dend[now];
        dend[now]++;
    }
}trie;
int main(){
    int n,kase=0;
    while(scanf("%d",&n)!=EOF){
        if(n==0) break;
        trie.init();
        for(int i = 0;i < n; i++){
            scanf("%s",s);
            trie.insert(s);
        }
        printf("Case %d: %lld\n",++kase,trie.ans);
    }
    return 0;
}

POJ1056
送分题

#include<cstdio>
#include<cstring>
const int maxn = 1e3+11;
const int kd = 2;
struct Trie{
    int son[maxn][2],end[maxn],tot,root;
    int node(){
        end[tot]=0; son[tot][0]=son[tot][1]=-1;
        return tot++;
    }
    void init(){
        tot=0;
        memset(son,-1,sizeof son);
        memset(end,0,sizeof end);
        root=node();
    }
    void insert(char str[]){
        end[root]++;
        int now=root,idx;
        for(int i = 0; str[i]!='\0'; i++){
            idx=str[i]-'0';
            if(son[now][idx]==-1){
                son[now][idx]=node();
            }
            end[son[now][idx]]++;
            now=son[now][idx];
            
        }
    } 
    bool check(char str[]){
        int now=root,idx;
        bool flag=1;
        for(int i = 0; str[i]!='\0'; i++){
            idx=str[i]-'0';
            if(end[son[now][idx]]<2){
                return 0;
            }
            now=son[now][idx];
        }
        return 1;
    }
}trie;
char str[1000][100];
int main(){
    int n=0,kase=0;
    while(scanf("%s",str[n])!=EOF){
        if(str[n][0]=='9'){
            trie.init();
            for(int i = 0; i < n; i++) trie.insert(str[i]);
            bool flag=0;
            for(int i = 0; i < n; i++){
                if(trie.check(str[i])){
                    flag=1;break;
                }
            }
            if(!flag) printf("Set %d is immediately decodable\n",++kase);
            else printf("Set %d is not immediately decodable\n",++kase);
            n=0;continue;
        }
        n++;
    }
    return 0;
}

左儿子-右兄弟字典树
想法就是从父亲找到第一个儿子,然后儿子遍历所有兄弟
优点:避免了sonmaxn的建树方式,空间开支不受树的深度影响
缺点:复杂度系数要上升L倍
同是前面那道题//数据范围没给出,题目太水没办法优化

#include<bits/stdc++.h>
using namespace std;
const int maxn =1e4+11;
struct Trie{
    int son[maxn],tot,root;
    int bro[maxn],sz[maxn];
    char ch[maxn];
    void init(){
        root=0;tot=1;
        son[0]=bro[0]=sz[0]=0;
        ch[0]=0;
    }
    int node(int fa,char c){
        son[tot]=0;bro[tot]=son[fa];//tot的右兄弟是未更新时fa的最后一个左儿子
        ch[tot]=c; sz[tot]=0;
        son[fa]=tot;//update
        return tot++;
    }
    void insert(char str[]){
        int now=root,lc;sz[now]++;
        for(int i = 0; str[i]; i++){
            bool flag=0;
            for(lc=son[now];lc;lc=bro[lc]){
                if(ch[lc]==str[i]){
                    flag=1;break;
                }
            }
            if(!flag){// son[now]自己和所有兄弟跑遍了 / now根本没有儿子
                lc=node(now,str[i]);
            }
            now=lc;sz[now]++;
        }
    }
    bool check(char str[]){
        int now=root,lc;
        for(int i = 0; str[i]; i++){
            for(lc = son[now]; lc; lc=bro[lc]){
                if(ch[lc]==str[i]){
                    break;
                }
            }
            if(sz[now=lc]<2) return 0; 
        }
        return 1;
    }
}trie;
char str[101][101];
int main(){
    int n=0,kase=0;
    while(scanf("%s",str[n])!=EOF){
        if(str[n][0]=='9'){
            trie.init();
            for(int i = 0; i < n; i++) trie.insert(str[i]);
            bool flag=0;
            for(int i = 0; i < n; i++){
                if(trie.check(str[i])){
                    flag=1;break;
                }
            }
            if(!flag) printf("Set %d is immediately decodable\n",++kase);
            else printf("Set %d is not immediately decodable\n",++kase);
            n=0;continue;
        }
        n++;
    }
    return 0;
}

进阶:bzoj1174

Last Updated:2017.10.3

标签: 算法, 学习

添加新评论