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

说白了这个算法就是给你一个元素集$\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

分类: 文章

quhengyi11

喵(ฅ>ω<*ฅ)

3 条评论

B_Z_B_Y · 2018年11月3日 12:03 下午

dalao 强啊 QwQ

XZYQvQ · 2018年11月3日 7:41 上午

嘤嘤嘤。。。你把K-XZY的第600篇文章占了。。。
你还我坑位我要用第600篇写退役总结。。。
(QwQ开玩笑的,恭喜你喜提第600篇文章OvO!)

    quhengyi11 · 2018年11月3日 10:33 上午

    您可以再写一百篇再退役(不过那时候您就进队了QvQ(逃

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *