【算法】01 字典树解决 xor 最值问题 ——quhengyi11

讲真这么简单的算法我竟然不会我真的菜坏了）：

说白了这个算法就是给你一个元素集 $\mathbf{A}={a_i}$，询问一个元素 x，找出一个元素 $a_p\in\mathbf{A}$，使得 $x \oplus a_p$ 为最大值或最小值。

构造也超级简单，就把每个元素集里的元素二进制展开，从高位到低位塞进 Trie 树，查询的时候也把要查询的数二进制展开并从高位向低位在 Trie 树上跑，贪心跑就能找到最大或者最小值。

好的这个算法我讲完了（：

这里给出代码：

inline void ins (int x)
{
    int u = 0;
    fd (i, 31, 0)
    {
        int now = (x >> i & 1);
        if (ch[u][now])
            u = ch[u][now];
        else
        {
            ch[u][now] = ++tot;
            u = tot;
        }
    }
    val[u] = x;
}
inline int query (int x)//这个是求 max 的
{
    int u = 0, ret = 0;
    fd (i, 31, 0)
    {
        int now = (x >> i & 1);
        if (ch[u][now ^ 1])
            u = ch[u][now ^ 1];
        else
            u = ch[u][now];
    }
    return val[u] ^ x;
}

另外，有时候会加一个 $num[]$数组表示 Trie 树上这个点已经被走过了多少次，有时候为了满足一些约束关系是要维护它的啦。

这里放例题

1. 模板题 hdu4825

2.hdu5536

这道题稍微说一下，这里要求 $(s_i+s_j)\oplus s_k$的最大值，无非就是将前面的放进元素集查后面的或者反过来，可是如果是将前面的和放进元素集的话，因为无序性你会不知道你选了哪两个 $i,j$从而你就不能保证 $k\ne s_i,s_j$，因此我们反过来，将单个元素放入元素集，并且在每次查询 $s_i+s_j$的时候把 $s_i$和 $s_j$从两个元素集里剔除（可以用 num 数组维护剔除）

代码：

#include<bits/stdc++.h>
#define fo(i, a, b) for (Re int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (Re int i = (a); i >= (b); --i)
#define edge(i, u) for (Re int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define N 32005
#define Re register
#define pb push_back
#define F first
#define S second
#define ll long long
#define inf 1000000007
#define mp std::make_pair
#define lowbit(x) (x & -x)
#define ls (k << 1)
#define rs (k << 1 | 1)
#define mod 10007
int T, n, m, x, ch[N][2], tot, val[N], a[N], num[N];
inline void ins (int x)
{
    int u = 0;
    fd (i, 31, 0)
    {
        int now = (x >> i & 1);
        if (ch[u][now])
            u = ch[u][now];
        else
        {
            ch[u][now] = ++tot;
            u = tot;
        }
        ++num[u];
    }
    val[u] = x;
}
inline void update (int x, int val)
{
    int u = 0;
    fd (i, 31, 0)
    {
        int now = (x >> i & 1);
        u = ch[u][now];
        num[u] += val;
    }
}
inline int query (int x)
{
    int u = 0, ret = 0;
    fd (i, 31, 0)
    {
        int now = (x >> i & 1);
        if (ch[u][now ^ 1] && num[ch[u][now ^ 1]])
            u = ch[u][now ^ 1];
        else
            u = ch[u][now];
    }
    return val[u];
}
int main ()
{
    scanf("%d", &T);
    fo (q, 1, T)
    {
        memset(ch, 0, sizeof ch);
        memset(val, 0, sizeof val);
        memset(num, 0, sizeof num);
        tot = 0;
        scanf("%d", &n);
        fo (i, 1, n)
        {
            scanf("%d", &a[i]);
        }
        fo (i, 1, n)
            ins(a[i]);
        int ans = 0;
        fo (i, 1, n)
            fo (j, i + 1, n)
            {
                update(a[i], -1);
                update(a[j], -1);
                ans = std::max(ans, query(a[i] + a[j]) ^ (a[i] + a[j]));
                update(a[i], 1);
                update(a[j], 1);
            }
        printf("%d\n", ans);
    }
    return 0;
}

3.bzoj4260

也是裸题，随便 dp 一下就行了（我刚开始把中间的加号看成了异或蒙了半天，听说如果这样需要可持久化 Trie 树？）

4.luogu4551

树上路径考虑树上异或前缀和，然后就是模板题了。

然后我在机房关门前又双叒水了一篇 blog