题解 | # Trie # _牛客博客

模板题目一：https://www.luogu.com.cn/problem/P8306

$N$ 是字符串的最大可能长度， $cnt[]$ 数组记录字符串的个数， $idx$ 是下标

const int N = 3000000 + 100;
int son[N][62], cnt[N], idx = 0;

插入操作：
两处 $cnt[p]$ 的位置有不同的效果，第一处 $cnt[p]$ 记录的是所有字符串前缀的出现次数，而最后一处的 $cnt[p]$ 记录的是所有完整字符串的出现次数

void insert(string s){
    int p = 0;
    for(int i = 0; i < (int)s.size(); i ++){
        int u = work(s[i]);
        if(!trie[p][u]) trie[p][u] = ++ idx;
        p = trie[p][u];
        cnt[p] ++;
    }
}

查询操作：查询字符串的出现次数

int query(string s){
    int p = 0;
    for(int i = 0; i < (int)s.size(); i ++){
        int u = work(s[i]);
        if(!trie[p][u]) return 0;
        p = trie[p][u];
    }
    return cnt[p];
}

额，因为是多组测试，所以得清除上一组保留的数据：

for(int i = 0; i <= idx; i ++){
        for(int j = 0; j < 62; j ++) trie[i][j] = 0;
        cnt[i] = 0;
    }
    idx = 0;

总代码：

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;


const int N = 3000000 + 100;
int trie[N][62], cnt[N], idx = 0;


int work(char x){
    if('A' <= x && x <= 'Z') return x - 'A';
    else if('a' <= x && x <= 'z') return x - 'a' + 26;
    else return x - '0' + 52;
}

void insert(string s){
    int p = 0;
    for(int i = 0; i < (int)s.size(); i ++){
        int u = work(s[i]);
        if(!trie[p][u]) trie[p][u] = ++ idx;
        p = trie[p][u];
        cnt[p] ++;
    }
}

int query(string s){
    int p = 0;
    for(int i = 0; i < (int)s.size(); i ++){
        int u = work(s[i]);
        if(!trie[p][u]) return 0;
        p = trie[p][u];
    }
    return cnt[p];
}

void solve(){

    for(int i = 0; i <= idx; i ++){
        for(int j = 0; j < 62; j ++) trie[i][j] = 0;
        cnt[i] = 0;
    }
    idx = 0;
    
    int n, q; cin >> n >> q;
    for(int i = 1; i <= n; i ++){
        string s; cin >> s;
        insert(s);
    }
    while(q --){
        string s; cin >> s;
        cout << query(s) << endl;
    }
    return ;
}

signed main(){
    HelloWorld;

    int tt = 1; 
    cin >> tt;
    while(tt --) solve();
    return 0;
}

题目二：https://www.luogu.com.cn/problem/P10470

一点点逆向思维

总代码：

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;


const int N = 1000000 + 100;

int trie[N][26], cnt[N], idx = 0;


void insert(string s){
    int p = 0;
    for(int i = 0; i < (int)s.size(); i ++){
        int u = s[i] - 'a';
        if(!trie[p][u]) trie[p][u] = ++ idx;
        p = trie[p][u];
    }
    cnt[p] ++;
}

int query(string s){
    int ans = 0, p = 0;
    for(int i = 0; i < (int)s.size(); i ++){
        int u = s[i] - 'a';
        if(!trie[p][u]) return ans;
        p = trie[p][u];
        ans += cnt[p];
    }
    return ans;
}
void solve(){

    int n, m; cin >> n >> m;
    for(int i = 1; i <= n; i ++){
        string s; cin >> s;
        insert(s);
    }    
    for(int i = 1; i <= m; i ++){
        string s; cin >> s;
        cout << query(s) << endl;
    }
    return ;
}

signed main(){
    HelloWorld;

    int tt = 1; 
    while(tt --) solve();
    return 0;
}

题目三：https://www.luogu.com.cn/problem/P10471

很经典的一道题目，如果不知道用字典树的话，就会陷入 $O(n^{2})$ 暴力循环枚举中

把每一个整数看作长度为 $31$ 的二进制 $01$ 串，然后将 $01$ 串插入到字典树中。遍历 $1$ 到 $n$ ，枚举每一个 $a_{i}$ ，然后在二进制上找对应进制相反的进制，如果相反的进制对应的值为空，那么只好相同为 $0$ 了

注意从大到小开始插入，这样可以求得最大值

最多会有 $10^{5} \times 32$ 个节点，所以 $N$ 取值为 $5000000 + 100$

总代码：

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;


const int N = 5000000 + 100;

int trie[N][2], idx = 0;

void insert(int x){
    int p = 0;
    for(int i = 32; i >= 0; i --){
        int u = (x >> i) & 1;
        if(!trie[p][u]) trie[p][u] = ++ idx;
        p = trie[p][u];
    }
}

int query(int x){
    int ans = 0, p = 0;
    for(int i = 32; i >= 0; i --){
        int u = (x >> i) & 1;
        if(trie[p][!u]){
            ans += (1LL << i);
            p = trie[p][!u];
        }
        else p = trie[p][u];
    }
    return ans;
}

void solve(){
    
    int n; cin >> n;
    vector<int> a(n + 10);
    for(int i = 1; i <= n; i ++){
        cin >> a[i];
        insert(a[i]);
    }
    int ans = 0;
    for(int i = 1; i <= n; i ++) ans = max(ans, query(a[i]));
    cout << ans << endl;
    return ;
}

signed main(){
    HelloWorld;

    int tt = 1; 
    while(tt --) solve();
    return 0;
}

题目四：https://www.luogu.com.cn/problem/P4551

设 $d[x]$ 表示节点 $x$ 与根节点的异或路径值，那么求树中所有异或路径的最大值，就是求两个节点 $i,j$ ，满足 $d[i] \oplus d[j]$ 值最大

$d[i] \oplus d[j]$ 就是 $i,j$ 的异或路径值，额，很显然了，与 $LCA$ 一样的道理

那么可以用 $DFS$ 搜索预处理出所有节点的 $d$ 值，然后找两个节点 $i,j$ ，满足 $d[i] \oplus d[j]$ 值最大，就是题目三

总代码：

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;


const int N = 100000 + 100;

int n, d[N];
vector<pair<int, int> > adj[N];
int trie[N * 33][2], idx;

void dfs(int u, int fa, int sum){
    d[u] = sum;
    for(auto [v, w] : adj[u]){
        if(v == fa) continue;
        dfs(v, u, sum ^ w);
    }
}

void insert(int x){
    int p = 0;
    for(int i = 32; i >= 0; i --){
        int u = (x >> i) & 1;
        if(!trie[p][u]) trie[p][u] = ++ idx;
        p = trie[p][u];
    }
}

int query(int x){
    int ans = 0, p = 0;
    for(int i = 32; i >= 0; i --){
        int u = (x >> i) & 1;
        if(trie[p][!u]){
            ans += (1LL << i);
            p = trie[p][!u];
        }
        else p = trie[p][u];
    }
    return ans;
}

void solve(){

    cin >> n;
    for(int i = 1; i <= n - 1; i ++){
        int u, v, w; cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    dfs(1, -1, 0);
    for(int i = 1; i <= n; i ++) insert(d[i]);
    int ans = 0;
    for(int i = 1; i <= n; i ++) ans = max(ans, query(d[i]));
    cout << ans << endl;
    return ;
}

signed main(){
    HelloWorld;

    int tt = 1; 
    while(tt --) solve();
    return 0;
}

题目五：https://codeforces.com/problemset/problem/1285/D

$[Trie+树形DP]$

首先将 $n$ 个数的二进制 $01$ 串存入 $Trie$ 中，然后想如何求最小值， $dfs(0,32)$ ，第一位表示权值，第二位表示枚举的二进制位置

如果第 $i$ 位全是 $0$ ，即 $!trie[p][0]$ ，那么返回 $dfs(trie[p][1],x-1)$
如果第 $i$ 位全是 $1$ ，即 $!trie[p][1]$ ，那么返回 $dfs(trie[p][0],x-1)$
如果第 $i$ 位既有 $0$ 也有 $1$ ，那就返回 $min(dfs(trie[p][0],x-1), dfs(trie[p][1],x-1))+2^{i}$

总代码：

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;


const int N = 100000 + 100;


int trie[32 * N][2], idx = 0;
int n, a[N], ans;

void insert(int x){
    int p = 0;
    for(int i = 32; i >= 0; i --){
        int u = (x >> i) & 1;
        if(!trie[p][u]) trie[p][u] = ++ idx;
        p = trie[p][u];
    }
}

int dfs(int p, int x){
    if(x < 0) return 0;
    if(!trie[p][0]) return dfs(trie[p][1], x - 1);
    if(!trie[p][1]) return dfs(trie[p][0], x - 1);
    return min(dfs(trie[p][0], x - 1), dfs(trie[p][1], x - 1)) + (1LL << x);
}

void solve(){

    cin >> n;
    for(int i = 1; i <= n; i ++){
        cin >> a[i];
        insert(a[i]);
    }    
    cout << dfs(0, 32);
    return ;
}

signed main(){
    HelloWorld;

    int tt = 1; 
    while(tt --) solve();
    return 0;
}