字典树

放假在家无聊就学了字典树，字典树这东西学起来简单，但是再有的地方用起来还是挺难的（主要是想不到），但是套路就哪几种摸清楚了还是一样简单。我就简单的口胡一下什么是字典树。

字典树又称为前缀树，至于为什么这么叫它，你学会了字典树就明白了。什么作用？能干么？我觉得我也没必要说，等你学会了字典树自然就知道了它的作用，而且还是自己思考，可能会事半功倍。

直接说怎么建树吧，比如我现在有一个字符串 “aab”,该怎么建树呢。我就直接画图了
我现在又有一个字符串 “aac”

想必聪明的你看到这两幅图就知道怎么建了吧？两个字符串（“aab”,“aac”）根据图中可知，只用了两个a，也就是两个字符串共用了aa，所以很显然字典树的作用之一就是节省空间。
但是，如果我们就这么建下来了，怎么判断有哪些字符串呢？比如怎么判断树中的 “aa”是不是我建树中的字符串呢？
其实很简单只要标记一下就行了。如图：

比如我们再每个字符串的最后一个字符做一下标记(也就是’b’, ‘c’)这样我就能判断有哪些字符串是建树中的了。

就这样简单说一下吧！看几道题

最大异或对

题意我就不写自己看吧！说一下思路吧：
这题刚开始我也不会写 （前提是知道这题是字典树 智商不够用啊），后来看了题解 才知道。要想找一对最大异或值，该开始一般人第一反应是暴力，但是发现是时间复杂度太大，就想着怎么优化。嗯嗯嗯嗯，暴力是对的，但是不能一个一个枚举，可以用字典树枚举每个数 ，然后通过字典树求出以枚举的那个数能异或的最大值。但是为啥字典树求出来就是最大的呢？
这个才是重点前面都是废话哈哈哈哈哈哈，为什么字典树求出来就是最大的呢？
我们建树 是把每个数拆成二进制，然后每个数只有01，是不是可以看成一个字符串然后建树，因为只有01，所以建的树一定是二叉树，是从高位向低位建呢？还是从低位向高位建呢？因为求最大吗，所以自然从高位向低位建呀。我们就建一个高度位30的二叉树，每一层代表这个位是0，还是1。然后将你要枚举的数拆开，
如果你要枚举的数第30位是0，要想异或最大 ，那么要异或的有1就选1，没有的话就选0了，查这颗字典树的第1层（也就是第30位）有1就选1，没有就选0，要是我们枚举的那个数第30位是1，
同理，要想异或最大当然是找0呀，所以查字典树第一层是否有0；
然后就以此类推查29位，28位…
为啥查的数一定是我们n个数中的一个？
这是我之前想的问题，其实很简单 因为我们建树直接按30位从高位向低位建树，所以所有数的最后一位再字典树中一定是叶子节点（第30层的），所以从跟节点到最后一个节点，一定是n个数中的一个。
说了这么多，看下代码吧，懒得写注释了。

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

const int N = 1e5 + 7;
int a[N], tree[30* N][2], n;
int cnt = 1;

void build(int x){
    int now = 1;
    for (int i = 30; i >= 0;i--){
        int id = (x >> i) & 1;
        if(!tree[now][id])
            tree[now][id] = ++cnt, now = cnt;
        else
            now = tree[now][id];
    }
}

int query(int x){
    int ans = 0, now = 1,cn=0;
    for (int i = 30; i >= 0;i--){
        int id = (x >> i) & 1;
        if(tree[now][!id])
            ans += 1 << i, now = tree[now][!id];
        else
            now = tree[now][id];
    }
    return ans;
}

int main(){
    scanf("%d", &n);
    for (int i = 1; i <= n;i++){
        scanf("%d", &a[i]);
        build(a[i]);
    }
    int maxn = INT_MAX;
    for (int i = 1; i <= n;i++){
        maxn = min(maxn, query(a[i]));
    }
    printf("%d\n", maxn);
}

再看一题 ：

D. Dr. Evil Underscores
题意：找一个任意的x，使得异或n个数的最大值要最小。

题解：这题也是知道了字典树 还是不会写，最后看了xls的代码 想了半天才想通为啥。
我就简单说下吧，跟上一题差不多，建一颗高度为30的二叉树，高度为1的节点代表二进制的第30位，以此类推。
要想找任意的x，使与n个数的异或的最大值最小。如果这个字典树有0、1，这个时候无论你选什么最大的异或之后还是1， 所以当字典树有0、1 的时候dfs ，0这个边，再dfs，1这个边，因为你不知道取0，1对后面的影响，所以都选，当只有，字典树只有0这条边的时候很显然走0，为什么不走1呢？这不是就最大值吗？走1不是更大吗？没错走1是更大，但是题目是要求让最大值最小，所以走0，同理只有1这条边的时候走1，前面有0，1的时候都在 这样会产生很多答案，最后再所有答案中取一个最小的就ok了，仔细想一下就能明白了。
代码：

    #include<bits/stdc++.h>
    using namespace std;
    const int N = 1e5 + 7;
    int tree[30 * N][2], a[N], n;
    int cnt = 1;
     
    void insert(int x){
        int now = 1;
        for (int i = 30; i >= 0;i--){
            int id = (x >> i) & 1;
            if(tree[now][id] == 0){
                tree[now][id] = ++cnt;
                now = cnt;
            }else{
                now = tree[now][id];
            }
        }
    }
     
    int dfs(int node,int pos,int maxn){
        if(pos<0){
            return maxn;
        }
            
        int minn = INT_MAX;
        if(tree[node][0] && tree[node][1]){
            minn = min(minn, dfs(tree[node][0], pos - 1, maxn + (1 << pos)));
            minn = min(minn, dfs(tree[node][1], pos - 1, maxn + (1 << pos)));
        }else if(tree[node][0]){
            minn = min(dfs(tree[node][0], pos - 1, maxn), minn);
        }else{
            minn = min(dfs(tree[node][1], pos - 1, maxn), minn);
        }
        return minn;
    }
     
    int main(){
        scanf("%d", &n);
        for (int i = 1; i <= n;i++){
            scanf("%d", &a[i]);
            insert(a[i]);
        }
        printf("%d\n", dfs(1, 30, 0));
    }