异或：01字典树

浅浅的花香味﹌ 2023-06-07 03:21 17阅读 0赞

给你一组数，给你一个数字，*求这组数字中和这个数异或和最大的数*

*模板：*

#include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    const int M=1e5+5;
    int n,m,t[M*33][2],tot;
    ll val[33*M];
    void inter(ll x){
        int rt=0;
        for(int i=32;i>=0;i--){
            int id=(x>>i)&1;
            if(!t[rt][id])t[rt][id]=++tot;
            rt=t[rt][id];
        }
        val[rt]=x;
    }//这个位置的数字是几
    ll find(ll x){
        int rt=0;
        for(int i=32;i>=0;i--){
            int id=(x>>i)&1;
            if(t[rt][id^1])rt=t[rt][id^1];//能找到相反的就去相反的
            else rt=t[rt][id];
        }
        return val[rt];
    }
    int main(){
        int T,cas=0;
        scanf("%d",&T);
        while(T--){
            memset(val,0,sizeof(val));
            for(register int i=0;i<=M*32;i++)t[i][0]=t[i][1]=0;
            tot=0;
            scanf("%d%d",&n,&m);
            for(int x,i=1;i<=n;i++)scanf("%d",&x),inter(x);
            printf("Case #%d:\n",++cas);
            for(int x,i=1;i<=m;i++)scanf("%d",&x),printf("%lld\n",find(x));
        }
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，17人围观）

还没有评论，来说两句吧...

相关阅读

相关 01字典树之求树上最长异或路径

*题目描述** 给定一棵 n 个点的带权树，结点下标从 1 开始到 N 。寻找树中找两个结点，求最长的异或路径。异或路径指的是指两个结点之间唯一路径上的所有边权的异...

深藏阁楼爱情的钟/ 2024年04月18日 09:24/ 0 赞/ 131 阅读

相关 c语言异或(c语言异或符号)

请帮我讲解一下C语言中的异或运算首先，我们看一下异或的原理： a = 3 ^ 5; 3的二进制是0011，5的二进制是0101。异或发现两者的不同之处，所以a最终为

Myth丶恋晨/ 2023年09月26日 12:30/ 0 赞/ 229 阅读

相关二进制异或

[https://blog.csdn.net/qq\_35937273/article/details/82724247][https_blog.csdn.net_qq_359

刺骨的言语ヽ痛彻心扉/ 2023年08月17日 16:26/ 0 赞/ 222 阅读

相关可持久化01字典树 hdu5536

题目大意：在一个数组中找出 (s\[i\]+s\[j\])^s\[k\] 最大的值，其中 i、j、k 各不相同。数据范围太小了做法见代码： inclu

小鱼儿/ 2023年06月07日 12:06/ 0 赞/ 132 阅读

相关异或：01字典树

给你一组数，给你一个数字，求这组数字中和这个数异或和最大的数模板： include<bits/stdc++.h> using namespace std;

浅浅的花香味﹌/ 2023年06月07日 03:21/ 0 赞/ 18 阅读

相关异或运算符

/ ^的特点：a 异或 b 两次得到的还是 a。 / class OperatorDemo{ public static void main(S

桃扇骨/ 2022年05月22日 06:41/ 0 赞/ 372 阅读

相关 HDU5536 01字典树求模板

include<bits/stdc++.h> using namespace std; const int N=1e5+10; struct T

傷城~/ 2022年05月09日 05:18/ 0 赞/ 296 阅读

相关与、或、非、异或

与 & 两个数中位都为1，结果才为1，否则为0 或 | 两个数中只要有一个为1，结果就为1，否则为0 非 ! 位为0，结果

Love The Way You Lie/ 2022年03月06日 10:58/ 0 赞/ 523 阅读

相关（前缀异或和）51nod 2128 前缀异或

[2128 前缀异或][2128] 输入一个长度为n(1 <= n <= 100000)数组a\[1\], a\[2\], ..., a\[n\]。输入一个询问数m(

淡淡的烟草味﹌/ 2022年02月16日 03:29/ 0 赞/ 471 阅读

相关 143. 最大异或对(字典树 + 位运算)

题目描述：在给定的N个整数A1，A2……AN 中选出两个进行xor（异或）运算，得到的结果最大是多少？输入格式第一行输入一个整数N。第二行输入N个整数A

刺骨的言语ヽ痛彻心扉/ 2021年12月05日 21:43/ 0 赞/ 367 阅读