总结

一个字符串是树中的一条链，从根节点到叶子结点

字典树中，字符放在边上，节点仅代表编号

具体的，通常用$tr[N][c]$，表示编号为i的节点向下边为字符c连接的节点编号

Trie一般形式（插入）

1
2
3
4
5
6
int tr[N][26];
int tot=1;
for(auto c : s){
    if(tr[t][c-'a']==0) tr[t][c-'a']=++tot;
    t=tr[t][c-'a'];
}

01Trie一般形式（插入）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
int tr[N*30][2];
int tot=1;
void insert(int x){
    int p = 1;
    for(int i=31;i>=0;i--){
        int u = (x>>i)&1;
        if(!tr[p][u]) tr[p][u] = ++tot;
        p = tr[p][u];
    }
}

Trie

Trie字符串统计

地址

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
void SINGLE_TEST()
{
    int n;cin>>n;
    while(n--){
        char op;cin>>op;
        string s;cin>>s;
        if(op=='I'){
            int t=1;
            for(auto c : s){
                if(tr[t][c-'a']==0) tr[t][c-'a']=++tot;
                t=tr[t][c-'a'];
            }
            cnt[t]++;
        }else{
            int t=1;
            bool ok=0;
            for(auto c : s){
                if(tr[t][c-'a']==0){
                    ok=1;
                    cout<<0<<'\n';
                    break;
                }
                t=tr[t][c-'a'];
            }
            if(!ok)
                cout<<cnt[t]<<'\n';
        }
    }
}

E - Yet Another Sigma Problem

地址

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
void SINGLE_TEST()
{
    int n;cin>>n;
    ll ans=0;
    for(int i=1;i<=n;i++){
        string s;cin>>s;
        int t=1;
        for(auto c : s){
            if(tr[t][c-'a']==0) tr[t][c-'a']=++tot;
            t=tr[t][c-'a'];
            ans+=cnt[t]++;
        }
    }
    cout<<ans<<'\n';
}

01Trie

最大异或对

地址

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
void insert(int x){
    int p = 1;
    for(int i=31;i>=0;i--){
        int u = (x>>i)&1;
        if(!tr[p][u]) tr[p][u] = ++tot;
        p = tr[p][u];
    }
}
int query(int x){
    int p = 1;
    int res = 0;
    for(int i=31;i>=0;i--){
        int u = (x>>i)&1;
        if(tr[p][!u]){
            res += 1<<i;
            p = tr[p][!u];
        }else{
            p = tr[p][u];
        }
    }
    return res;
}

void SINGLE_TEST()
{
    int n;cin>>n;
    vector<int> a(n+1);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        insert(a[i]);
    }
    ll ans=0;
    for(int i=1;i<=n;i++){
        ans = max(ans, query(a[i]));
    }
    cout<<ans<<'\n';
}

D. Dr. Evil Underscores

地址

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
int tr[N*30][2];
int dep[N*30];
int tot=1;
void insert(int x){
    int p=1;
    for(int j=30;j>=0;j--){
        int t=(x>>j&1);
        if(!tr[p][t]) tr[p][t]=++tot;
        dep[p]=j;
        p=tr[p][t];
    }
}
void SINGLE_TEST()
{
    int n;cin>>n;
    vector<int> a(n+1);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        insert(a[i]);
    }
    function<int(int)> dfs=[&](int x){
        int ans=0;
        if(!tr[x][0] && !tr[x][1]) return 0LL;    
        if(tr[x][0] && tr[x][1]){
            return min(dfs(tr[x][0]),dfs(tr[x][1]))+(1LL<<dep[x]);
        }
        if(tr[x][0]){
            return dfs(tr[x][0]);
        }
        if(tr[x][1]){
            return dfs(tr[x][1]);
        }
    };
    cout<<dfs(1)<<'\n';
}

C. Xor Tree

地址

一般对于求删除数，我们可以反向考虑求保留数

参考

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
void SINGLE_TEST()
{
    int n;cin>>n;
    vector<int> a(n+1);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        insert(a[i]);
    }
    function<int(int)> dfs=[&](int x){
        if(!tr[x][0] && !tr[x][1]) return 1LL;
        if(!tr[x][0]) return dfs(tr[x][1]);
        if(!tr[x][1]) return dfs(tr[x][0]);
        return max(dfs(tr[x][0]),dfs(tr[x][1]))+1;
    };
    cout<<n-dfs(1)<<'\n';
}