Trie樹模闆及練習

Trie樹(字典樹)性質：

1：每條邊/個非根節點上儲存一個字母

2：從根節點到某一節點，把路徑上的字母連起來即為這個節點表示的字元串

3：每個節點的所有子節點連邊/子節點各不相同

4：整棵樹的根節點為空，便于插入和查詢

模闆：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int n,q,ord,len,root,tot;
int tree[][];//tree[i][j]表示編号(1)為i的節點的第j個兒子(2)的編号 
int sum[];//某一編号(1)的節點出現的次數 
char c[];
bool v[];//表示目前節點是否為單詞結束标志 
void insert()//插入 
{
    len=strlen(c);
    root=;//若将根節點編号設定1,需将tot初始值也設為1 
    for(int i=;i<len;i++)
    {
        int x=c[i]-'a'+;//編号2:第x個兒子(Ascll);相同字母編号相同 
        if(!tree[root][x])
        tree[root][x]=++tot;//編号1:編号為tot的節點;相同字母編号可能不同 
        sum[tree[root][x]]++;//通路次數
        root=tree[root][x];//順着tire樹向下走 
    }
    v[root]=;
}
bool ask_prefix()//判斷字首是否出現 
{
    len=strlen(c);
    root=;//從根節點開始找
    for(int i=;i<len;i++)
    {
        int x=c[i]-'a'+;
        if(!tree[root][x])
        return ;
        root=tree[root][x];
    }
    return ;
}
bool ask()//判斷單詞是否出現 
{
    len=strlen(c);
    root=;
    for(int i=;i<len;i++)
    {
        int x=c[i]-'a'+;
        if(!tree[root][x])
        return ;
        root=tree[root][x];
    }
    return v[root];
}
int ask_sup()//查詢字首出現次數 
{
    len=strlen(c);
    root=;
    for(int i=;i<len;i++)
    {
        int x=c[i]-'a'+;
        if(!tree[root][x])
        return ;
        root=tree[root][x]; 
    }//root經過此循環後變成字首最後一個字母所在位置的後一個位置
    return sum[root];
}
int main()
{
    scanf("%d",&n);
    for(int i=;i<=n;i++)
    {
        scanf("%s",c);
        insert();
    }
    scanf("%d",&q);
    for(int i=;i<=q;i++)
    {
        scanf("%d%s",&ord,&c);
        if(ord==)
        {
            if(ask())
            printf("YES\n");
            else printf("NO\n");
        }
        if(ord==)
        {
            if(ask_prefix())
            printf("YES\n");
            else printf("NO\n");
        }
        if(ord==)
        printf("%d\n",ask_sup());//Sum of Prefix
    }
    return ;
}
           

練習：

http://codevs.cn/problem/3031/最富有的人

貪心法與DFS法求解

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int n,root,tot;
int ans;
int num[],tree[][],v[];//易MLE 
void insert(int k)
{
    root=;
    for(int i=;i>=;i--)//二進制位從左向右自上而下建樹 
    {
        int x=(k>>i)&;
        if(!tree[root][x])
        tree[root][x]=++tot;

        root=tree[root][x];
    }
    v[root]=k;//記錄數字值 
}
void query(int k)//貪心法：使最高位上貢獻的答案盡量大 
{
    root=;
    int total=;
    for(int i=;i>=;i--)
    {
        int x=(k>>i)&;
        if(!tree[root][x^])
        root=tree[root][x];
        else
        {
            root=tree[root][x^];
            total|=(<<i);//分部使用|運算 
        }
    }
    ans=max(ans,total);
}
void dfs(int x,int y)//DFS：從高位向低位搜，盡量讓兩個指針一個走1一個走0，不滿足時才走相同的，每個點最多被周遊1次 
{
    ans=max(ans,v[x]^v[y]);
    if((tree[x][]&&tree[y][])||(tree[x][]&&tree[y][]))
    {
        if(tree[x][]&&tree[y][])
        dfs(tree[x][],tree[y][]);
        if(tree[x][]&&tree[y][])
        dfs(tree[x][],tree[y][]);
        return;
    }
    if(tree[x][]&&tree[y][])
    dfs(tree[x][],tree[y][]);
    if(tree[x][]&&tree[y][])
    dfs(tree[x][],tree[y][]);
}
int main()
{
    scanf("%d",&n);
    for(int i=;i<=n;i++)
    {
        scanf("%d",&num[i]);
        insert(num[i]);
    }
    //dfs(0,0);
    for(int i=;i<=n;i++)
    query(num[i]);
    printf("%d\n",ans);
    return ;
}