算法简介：流光的星火

$\tt Trie$ 树，已经在曾经的文章中提及，但是说呢，并没有多提应用以及一些细节，所以说我们单独开一篇文章来讲 $\tt Trie$ 树。

友情链接：

【算法介绍】字符串算法 | 祝馀宫

那么字典树字典树，形如其名，就是字典形状的树。我们就是基于字典的顺序来排列，会在下文提到。

算法引导：长明的烛火

那么所谓字典顺序，就是我们在做字符串比大小的时候说的字典序。如果看过英文字典的话，就会发现一个这样的规律：

优先按照字典序排序，意思就是按照每一位的字符顺序排，越靠前的位置权值越大。比如说对于字符串 abcd 和 bcda 第一位 a 小于 b 所以说 abcd 小。
如果一个串是另一个串的前缀，则短的那一个小。比如说对于字符串 abc 和字符串 abcd 那么显然就是 abc 更小。

知道了这个字典序的顺序，那么我们字典树又是怎么个东西呢？首先我们要明确的一点是，这个字典树是一个新的数据结构，肯定不会是像数组一样列表式存储，我们要有内存上和形式上的优化。再结合字典树中的 “树” 这个关键词，我们大致会有这样的猜想。

树的节点，或者树的边表示一个字符，然后当前节点到根的路径或者点连到一起就是当前的字符串。

然后我们深入思考，这样的结构显而易见时会有重复状态的，比如说 tea 和 ten 他们的前缀 te 都是重复的，直到 a 和 n 是不同的才出现分支。似乎这是一个很高效的数据结构，而这玩意就是我们说了千百遍的的字典树。

那么指正一下刚刚的猜测，对于字典树的结构和内容给出精确的定义：用边来代表字母，而从根结点到树上某一结点的路径就代表了一个字符串，根是空。

那么我们就可以有下面这样的经典图，表示字典树的结构。

算法模板：燧传的烽火

其实有了刚刚的思路，代码并不难实现，主要注意的是空间、细节问题，总体来说 $\tt Trie$ 是一个比较有趣的算法。

// 这里写一个常规的字符串 Trie
int ch[N][30], tot = 1; // tot = 1 是根节点
int mark[N]; // N 等于所有读入字符串的长度总和，30是字符集大小，这里是 26 个字母

inline void Insert(string s) {
    int p = 1; // 从根节点开始
    for(char &c : s) { // 顺着树的结构搜
        if(!ch[p][c - 'a']) {
            ch[p][c - 'a'] = ++ tot;
        }
        p = ch[p][c - 'a'];
    }
    mark[p] = 1; // 把最后一个字符标记表示一个单词结束
}

inline bool Search(string s) {
    int p = 1;
    for(char &c : s) { // 顺着树的结构搜
        if(!ch[p][c - 'a']) { // 没路了，说明找不到
            return false;
        }
        p = ch[p][c - 'a'];
    }
    return mark[p]; // 如果刚好有一个单词结尾，说明配对上了，否则没有找到
}

这上面只是最最基础的应用，实际上还有很多神奇的用法等待开发~

算法演示：燎灼的烈火

那么一样我们来一个模板题先开开胃。

POJ - 3630 Phone List

阅读题面，这里给一个非最优解的做法，由于我们上文说过字典树的存储规则可以认为是字典序，于是说把所有字符串按照字典序排序，然后看标记的路上有没有看到单词结尾路上的标记点即可。

const int N = 1e5 + 10;

int n;
string s[N];

int ch[N][10], mark[N], tot = 1;
inline bool insert(string s) {
    int p = 1, flag = 0;
    for(char &c : s) {
        if(ch[p][c - '0'] == 0) {
            ch[p][c - '0'] = ++tot;
        }
        if(mark[p]) flag = 1;
        p = ch[p][c - '0'];
    }
    mark[p] = 1;
    return flag;
}

bool ans;

inline void Input() {
    cin >> n; ans = 0;
    for(int i = 1; i <= n; i++) {
        cin >> s[i];
    }
}

inline void Work() {
    sort(s + 1, s + n + 1);
    for(int i = 1; i <= n; i++) {
        ans |= insert(s[i]);
    }
    if(!ans) cout << "YES\n";
    else cout << "NO\n";
}

inline void Clear() {
    memset(ch, 0, sizeof(ch)); 
    memset(mark, 0, sizeof(mark));
    tot = 1;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T; cin >> T;
    while(T--) {
        Clear();
        Input();
        Work();
    }
    return 0;
}

算法拓展：不灭的薪火

那么这里来一道更加刺激的题目。

在给定的 $N$ 个整数 $A_1,A_2,···,A_n$ 中选出两个并进行 XOR（异或）运算，得到的结果的最大值是多少?

这题我没找到原题题源……（绝对不是我懒得用原题机找

话说回来，这道题我用了猴子算法骗了 90pts 运气超级好。

那么这题如果是正解怎么做呢，看上去和 $\tt Trie$ 并无关系。我们注意到异或属于位运算，然后我们就可以把每一个数看成一串二进制位零一。于是转化为了 $\tt Trie$ 。

但是为什么是 $\tt Trie$ 呢，我们观察到异或运算具有唯一性，如果我们要凑出 $1$ 那么另一个数必须和我相反，否则的话我们只能找到一个和我们相同的数字凑出 $0$ ，然后我们如果把每一个数字都用 32 位凑齐的的话，大家都一样的，所以说我只要跟着配对到底就可以。

const int N = 5e6 + 10;

int n;
ll a[N];

int ch[N][2], tot = 1;

inline void Insert(ll x) {
    int p = 1;
    for(int i = 31; i >= 0; i--) {
        int now = (x >> i) & 1;
        if(!ch[p][now]) {
            ch[p][now] = ++tot;
        }
        p = ch[p][now];
    }
}

inline void Input() {
    read(n);
    for(int i = 1; i <= n; i++) {
        read(a[i]);
        Insert(a[i]);
    }
}

inline ll Find(ll x) {
    ll ans = 0; int p = 1;
    for(int i = 31; i >= 0; i--) {
        int now = (x >> i) & 1;
        if(!ch[p][now ^ 1]) p = ch[p][now];
        else {
            p = ch[p][now ^ 1];
            ans = ans ^ (1LL << i);
        }
    }
    return ans;
}

inline void Work() {
    ll ans = 0;
    for(int i = 1; i <= n; i++) {
        ans = max(ans, Find(a[i]));
    }
    printf("%lld\n", ans); 
}

int main() {
    int T = 1;
    while(T--) {
        Input();
        Work();
    }
    return 0;
}