UESTC 1582 奇迹的魔法啊，再度出现！ 二进制树(字典树的一种特殊情况)

奇迹的魔法啊，再度出现！二进制树

Source

17暑假前集训-数据结构专题 By
AutSky_JadeK，思路非原创

2017 UESTC Training for Data Structures

UESTC 1582 奇迹的魔法啊，再度出现！

My Solution

题意：给出n个非负整数a1,a2,…,an
对于m次询问，第j次询问给定一个正整数xj，
输出max{a1XORxj,a2XORxj,…,anXORxj}。

二进制树(字典树的一种特殊情况)
先把所有的ai按照31比特位存入到二进制树(不够的相当于在前面补了0)，
child[x][k] 表示以x为父节点， k 为边， 的子节点
sz[x]表示这个节点的值, 值为0的时候节点不存在

查询的时候，从根开始走，尽量去走和val的当前二进制为不相等的节点，
此时的二进制异或为1，k = ((val >> i) & 1) ^ 1, res ^= 1 << i;
如果没有再走二进制为相等的节点且把加上的(1<<i)重新去掉
if(!sz[child[x][k]]) k ^= 1, res ^= 1 << i;
每次直接走完31位(不存在的时候都是+0,没有影响)， res就是答案了
复杂度 O(n*32)

#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int maxn = 1e5 + 8;

int child[maxn*31][2], sz[maxn*31], tot = 1;
inline void modify(int val, int d)
{
    int k, x = 1;
    for(int i = 30; i >= 0; i--){
        k = (val >> i) & 1;
        if(!child[x][k]) child[x][k] = ++tot;
        sz[x] += d;
        x = child[x][k];
    }
    sz[x] += d;
}
inline int query(int val)
{
    int k, x = 1, res = 0;
    for(int i = 30; i >= 0; i--){
        k = ((val >> i) & 1) ^ 1, res ^= 1 << i;
        if(!sz[child[x][k]]) k ^= 1, res ^= 1 << i;
        x = child[x][k];
    }
    return res;
}


int main()
{
    #ifdef LOCAL
    freopen("f.txt", "r", stdin);
    //freopen("f.txt", "w", stdout);
    int T = 1;
    while(T--){
    #endif // LOCAL
    //ios::sync_with_stdio(false); cin.tie(0);

    int n, m, i, x;
    scanf("%d", &n);
    for(i = 0; i < n; i++){
        scanf("%d", &x);
        modify(x, 1);
    }
    scanf("%d", &m);
    for(i = 0; i < m; i++){
        scanf("%d", &x);
        printf("%dn", query(x));
    }


    #ifdef LOCAL
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx