01字典树_01字典树找未出现的串__-Y-_-Y-_的博客-程序员秘密

转自：https://blog.csdn.net/zuzhiang/article/details/79872805

$01 字典树主要用于解决求异或最值的问题。$
1. 01字典树是一棵二叉树，每条节点的两条边分别表示二进制的某一位值是0还是1，
2. 将某个从根节点出发路径上边的值连起来就可以得到一个二进制串，这个二进制串是从根节点出发且最高位靠与根节点相连
3. 通过贪心的策略来寻找与x异或结果最大的数，即优先找和 x二进制的未处理的最高位值不同的边对应的点，这样保证结果最大
4. 这张图片讲的是在最大为4位二进制，3，4，5 是怎么插在01字典树上，以及val怎么存
配合下面模板和 https://cn.vjudge.net/problem/HDU-4825 请看这张图
在这里插入图片描述

模板

int tol; //节点个数 
LL val[32*MAXN]; //点的值 
int ch[32*MAXN][2]; //边的值 
 
void init()
{
     //初始化 
    tol=1;
    ch[0][0]=ch[0][1]=0;
}
 
void insert(LL x)
{
     //往 01字典树中插入 x 
    int u=0;
    for(int i=32;i>=0;i--)
    {
    
        int v=(x>>i)&1;
        if(!ch[u][v])
        {
     //如果节点未被访问过 
            ch[tol][0]=ch[tol][1]=0; //将当前节点的边值初始化 
            val[tol]=0; //节点值为0，表示到此不是一个数 
            ch[u][v]=tol++; //边指向的节点编号 
        }
        u=ch[u][v]; //下一节点 
    }
    val[u]=x; //节点值为 x，即到此是一个数 
}
 
LL query(LL x)
{
     //查询所有数中和 x异或结果最大的数 
    int u=0;
    for(int i=32;i>=0;i--)
    {
    
        int v=(x>>i)&1;
        //利用贪心策略，优先寻找和当前位不同的数 
        if(ch[u][v^1]) u=ch[u][v^1];
        else u=ch[u][v];
    }
    return val[u]; //返回结果 
}

例题

https://cn.vjudge.net/problem/HDU-4825

AC code

#include <bits/stdc++.h>
using namespace std;
#define maxn 100000
#define ll long long
int tol;
ll val[32*maxn];
int ch[32*maxn][2];
void init(){
    
  tol=1;
  ch[0][0]=ch[0][1]=0;
}
void insert(ll x){
    
  int u=0;
  for(int i=32;i>=0;i--){
    
    int v=(x>>i)&1;
    if(!ch[u][v]){
    
      ch[tol][0]=ch[tol][1]=0;
      val[tol]=0;
      ch[u][v]=tol++;
    }
    u=ch[u][v];
  }
  val[u]=x;
}
ll query(ll x){
    
  int u=0;
  for(int i=32;i>=0;i--){
    
    int v=(x>>i)&1;
    if(ch[u][v^1]) u=ch[u][v^1];
    else u=ch[u][v];
  }
  return val[u];
}
int main(){
    
  int T,n,m;
  ll a;
  scanf("%d",&T);
  for(int s=1;s<=T;s++){
    
    init();
    scanf("%d %d", &n, &m);
    for(int i=0;i<n;i++){
    
      scanf("%lld", &a);
      insert(a);
    }
    printf("Case #%d:\n", s);
    for(int i=0;i<m;i++){
    
      scanf("%lld", &a);
      printf("%d\n", query(a));
    }
  }
}

本文链接：https://blog.csdn.net/weixin_44410512/article/details/97004184

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

Java开发面试技巧，java开发经理面试题_普通网友的博客-程序员秘密

前言想必很多人在为接下来的金九银十做准备，或许你只是想找到一份工作，亦或许你希望通过今年最后这波拿到一个理想的工作和薪酬。不管是哪一种情况，你都需要提前做好准备，而不是临时抱佛脚。LZ为大家分享的这些面试真题一定要基于自己的技术栈来思考，而不是背一下就觉得这个我会了。试想一下，如果面试官接着往深处问，你能保证自己回答的上来吗？这样的跳槽方式在以前或许还比较适用，但是在今年一定是没有效果的，没有意义的。LZ把这350道Java面试真题分成了五大专题，分别是：性能优化、微服务架构、并发编程（高级）、开源框

ORA-04063: package body “SYS.DBMS_DATAPUMP“ has errors_好记忆不如烂笔头abc的博客-程序员秘密

由于手工修改编译了sys.DBMS_DATAPUMP的start_job里cluster_ok的默认参数值，1为0，编译成功后，导致导出报错。ORA-04063: package body "SYS.DBMS_DATAPUMP" has errorsSQL> CREATE TABLE "test" 2 ( " " VARCHAR2(255), "YPID" VARCHAR2(255));Table created.SQL> insert into "tes...

ASP.NET中引用dll“找不到指定模块"的完美解决办法 _junjieking的博客-程序员秘密

<br />最近继续用ASP.Net来重新开发ACM的Online Judge系统，因为要进行进程的监控，所以自己编写了一个非托管的DLL供ASP.Net调用。<br />我用的是VS2005的开发环境，后来发现使用[DllImport("Judge.dll")]后提示无法加载 DLL “Judge.dll” 找不到指定的模块<br />我这时是把Judge.dll拷贝到Bin目录下的，但仍然提示找不到DLL，在工程里添加DLL引用的时候，发现添加这个非托管DLL就会令VS2005异常退出（上网搜索后也

设计模式教程(4)-单例模式_chenjianqing1983的博客-程序员秘密

单例模式（Singleton Pattern）软件工程中，单例模式是限制一个类仅有一个实例对象。这在当系统中仅需一个对象进行协调动作时是非常有用的。这个概念是有时系统的操作当仅有一个对象时更加有效。或者严格限制对象实例的数量。这一概念是来自于数学中的单例的概念。批评者认为，单例模式是...

企业SSD中everspin的DDR3 STT-MRAM_everspin ssd_EVERSPIN的博客-程序员秘密

随着企业固态驱动器（SSD）在系统性能和更小的外形尺寸方面不断前进，SSD解决方案提供商面临着更大的挑战。在提高密度及耐用性，性能和添加重要的新功能的同时，还需要继续保护飞行中的数据免受电源故障的影响。通过使用更多具有更快接口速度的闪存通道和更高密度的闪存设备，下一代SSD将迅速增长到32TB甚至更高。如果采用具有DRAM工作存储器的控制器的传统体系结构，这将大大增加对能量存储以提供电源故障保护...

android button setbackgroundcolor,Xamarin(Android)中资源文件中的Button的SetBackgroundColor_weixin_39819327的博客-程序员秘密

我想设置按钮的背景色.我正在将Visual Studio与Xamarin一起使用.在Android中,我们使用：Java代码：button_vstrong_fluorescence.setBackgroundColor(ContextCompat.getColor(InventoryActivity.this, R.color.linear_filter_background));但是在Xamar...