The XOR Largest Pair(tire树)

2019-08-16 07:53:52来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

The XOR Largest Pair(tire树)

题目

The XOR Largest Pair

解析

一年前听学长讲这道题,什么01trie,好高级啊,所以没学,现在一看。。。。
看到xor就应该想到二进制,一看数据\(A_i< 2^{31}\),考虑把所有的数都处理成长度为32的二进制数,插入字典树中,查询的时候就逐位比较,有不同的先走不同的那边,这样保证了每次插入一个数时查询的结果是最大的,然后不断更新最大值就可以了
我这种不用位运算的懒人就直接用bitset维护了
从高位到地位插入可能好算一些

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 4e6 + 10;

int n, a, num, ans;

struct node {
    int nx[2];
} e[N];

void insert(int n) {
    bitset<35>s(n);
    int rt = 0;
    for (int i = 30; i >= 0; --i) {
        int v = (int)s[i];
        if (!e[rt].nx[v]) e[rt].nx[v] = ++num;
        rt = e[rt].nx[v];
    }
}

int query(int x) {
    bitset<35>s(x);
    int rt = 0, ret = 0;
    for (int i = 30; i >= 0; --i) {
        int v = (int)s[i];
        if (e[rt].nx[v ^ 1]) ret = ret << 1 | 1, rt = e[rt].nx[v ^ 1];
        else ret <<= 1, rt = e[rt].nx[v];
    }
    return ret;  
}

int main() {
    cin >> n;
    for (int i = 1, x; i <= n; ++i) {
        cin >> x;
        ans = max(ans, query(x));
        insert(x);
    }
    cout << ans;
}

原文链接:https://www.cnblogs.com/lykkk/p/11256831.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:在Visual C++ 6.0中为代码添加行号

下一篇:我眼中的虚函数