最大异或对(trie树)

题目描述: 


思路: 

1、首先此题我们要知道异或的规则,这里不赘述了,可以百度
2、如果利用trie树去找到一个数字与其异或能得到最大值
比如二进制数:1010.....是一个很大的数
我们想要异或得到的值更大,就需要让异或的值,最好去找与其相反的数
比如 1010.....最高位是1我当然找到0与其异或是比较好的,况且还在最高位如果异或
是1的话就很好,假如没找到0的话,那只能和1将就一下。
3、为了避免边界情况,少写一个判断,所以我们先插入后查找,不会影响最后结果的 
因为本身异或是0

图解:

如图:

第一个数是5,我们先进行插入操作,101,插入进去

第二个数是6,依然先插入后找最大异或对象,此树中目前只有5和6本身,根据上面规则,

6的二进制是110,最高位是1我们想找一个0与其匹配最好,但是5的二进制是101,第一位是1,加上trie树中没有最高位0与其匹配所以只能勉强,和1匹配后是1,再依次按照规则,继续,6异或5是3(011-->二进制数)

第三个数是3(011-->二进制),依旧先插入,最高位是0,所以我们要去找1与其匹配,trie树中有1,所以继续,第二位是1,最好情况是找到0与其匹配, 同样0我们也找到了,继续第三位是1,我们还想找0,但是trie树中好像没有0与其匹配,我们只好将就一下找1吧~,所以3与其匹配的二进制数是101-->5,3^5--->110(6)

第四个数是4(100-->二进制),先插入,最高位是1,我们可以找0与其匹配的,我们可以找到0,此0来源于3的二进制011中的最高位0,第二位是0我们就要找1与其匹配,1也同样有,继续往下走,第三位也是0,同样要找1,还是有,所以4^3--->7(111)

第五个数是7(111-->二进制),先插入,最高位是 1,我们还是找到0与其匹配,然后按照规则走下去,7^3--->4(100)

通过上述图解和例子,我们可以看出5 6 3 4 7这组数的最大异或对是4 和 3  -----> 7(111)


AC代码:

#include<iostream>

using namespace std;

//解释一下M为啥是31*N,因为根据数据范围,一个数小于2^31-->一个数31位,N个数
//就是31*N
const int N  = 1e5+10, M = 31*N;
int a[N];
int son[M][2];
int idx;

void insert(int x)
{
    int p = 0;
    for(int i=30;i>=0;i--)
    {
        //右移动大最大的位置,看下当前位置是1还是0
        int u = x >> i & 1;
        //如果没有创建一个节点存一下
        if(!son[p][u]) son[p][u] = ++idx;
        p = son[p][u];//指向下一个节点
    }
}

int query(int x)
{
    int p = 0;
    int res = 0;
    for(int i=30;i>=0;i--)
    {
        int u = x >> i & 1;
        if(son[p][!u])
        {
            p = son[p][!u];
            //这里等价于十进制中的 n = n * 10 + x;
            //八进制的话就是n = n * 8 + x;
            res = res * 2 + !u; 
        }
        else
        {
            p = son[p][u];
            res = res * 2 + u;
        }
    }
}

int main()
{
    int n;
    scanf("%d", &n);
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    int res = 0;
    for(int i=0;i<n;i++)
    {
        insert(a[i]); //插入
        int t = query(a[i]); //查找最合适的那个他
        res = max(res,a[i]^t); //找出最大值
    }
    printf("%d",res);
    return 0;
}

如果有错误,欢迎大家指正~

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/461944.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

AST解web控制流平坦化

此代码可以解决大部分 while if else 控制流平坦化原理&#xff1a; 先将 if 语句转为 switch 语句&#xff0c;再将 switch 分支合并&#xff0c;最后删除已合并的分支&#xff08;具体看代码&#xff09; 实现效果图 首先安装依赖&#xff1a; npm install babel/parser npm…

分布式文件存储与数据缓存(一)| FastDFS

目录 分布式文件系统FastDFS概述_简介FastDFS特性&#xff1a;分布式文件服务提供商 FastDFS概述_核心概念trackerstorageclientgroup FastDFS概述_上传机制内部机制如下 FastDFS概述_下载机制内部机制如下 FastDFS环境搭建_Linux下载安装gcc下载安装FastDFS下载安装FastDFS依赖…

c语言的字符串函数详解

文章目录 前言一、strlen求字符串长度的函数二、字符串拷贝函数strcpy三、链接或追加字符串函数strcat四、字符串比较函数strcmp五、长度受限制字符函数六、找字符串2在字符串1中第一次出现的位置函数strstr七、字符串切割函数strtok&#xff08;可以切割分隔符&#xff09;八、…

THM学习笔记—RootMe

nmap扫描&#xff0c;发现22端口和80端口打开 dirsearch扫描&#xff0c;注意到/panel和/uploads&#xff0c;在浏览器中打开 可以上传文件&#xff0c;尝试反弹shell 在尝试过程中发现网站不能上传.php文件&#xff0c;只需要将后缀更改为.php5之类即可 成功 查找文件&#x…

页面事件

下拉刷新事件 1. 什么是下拉刷新 下拉刷新是移动端的专有名词&#xff0c;指的是通过手指在屏幕上的下拉滑动操作&#xff0c;从而重新加载页面数据的行为。 2. 启用下拉刷新 启用下拉刷新有两种方式&#xff1a; ① 全局开启下拉刷新  在 app.json 的 window 节点中&…

Docker常用命令的使用及镜像的构建

1.docker的好处 在开发中可能会遇到一个问题&#xff0c;一个程序在自己电脑上能跑&#xff0c;但是换到服务器上就不行了。如果我们重新搭建环境&#xff0c;需要重新部署mysql,es,redis等组件很麻烦。有了docker之后&#xff0c;我们可以快速完成项目的部署。同时docker的隔…

MyBatis3源码深度解析(十二)MyBatis的核心组件(一)Configuration

文章目录 第四章 MyBatis的核心组件4.1 使用MyBatis操作数据库4.2 MyBatis核心组件4.3 Configuration组件4.3.1 属性4.3.2 设置4.3.3 类型别名4.3.3 类型处理器4.3.5 对象工厂4.3.6 插件4.3.7 配置环境4.3.8 映射器 第四章 MyBatis的核心组件 4.1 使用MyBatis操作数据库 在研…

《操作系统实践-基于Linux应用与内核编程》第10章-Linux综合应用

前言: 内容参考《操作系统实践-基于Linux应用与内核编程》一书的示例代码和教材内容&#xff0c;所做的读书笔记。本文记录再这里按照书中示例做一遍代码编程实践加深对操作系统的理解。 引用: 《操作系统实践-基于Linux应用与内核编程》 作者&#xff1a;房胜、李旭健、黄…

网络通信与网络协议

网络编程是指利用计算机网络实现程序之间通信的一种编程方式。在网络编程中&#xff0c;程序需要通过网络协议(如 TCP/IP)来进行通信&#xff0c;以实现不同计算机之间的数据传输和共享。在网络编程中&#xff0c;通常有三个基本要素 IP 地址:定位网络中某台计算机端口号port:定…

Pyqt5中,QGroupBox组件标题字样(标题和内容样式分开设置)相对于解除继承

Python代码示例&#xff1a; import sys from PyQt5.QtWidgets import QApplication, QWidget, QVBoxLayout, QGroupBox, QLabelclass MyApp(QWidget):def __init__(self):super().__init__()# 创建一个 QVBoxLayout 实例layout QVBoxLayout()# 创建 QGroupBox 实例self.grou…

【中等】保研/考研408机试-二叉树相关

目录 一、基本二叉树 1.1结构 1.2前序遍历&#xff08;注意三种遍历中Visit所在的位置&#xff09; 1.2中序遍历 1.3后序遍历 二、真题实战 2.1KY11 二叉树遍历&#xff08;清华大学复试上机题&#xff09;【较难】 2.2KY212 二叉树遍历二叉树遍历&#xff08;华中科技大…

王道机试C++第8章递归与分治 Day35和蓝桥杯两道真题程序

第 8 章 递归与分治 递归是指&#xff1a;函数直接或间接调用自身的一种方法&#xff0c;通常可把一个复杂的大型问题层层转化为与原问题相似但规模较小的问题来求解。 递归策略只需少量的程序就可描述解题过程所需的多次重复计算&#xff0c;因此大大减少了程序的代码量。 8.…

OLED 菜单操作

本次介绍一款中景园带字库的OLED显示屏&#xff0c;并基于该模块描述一种菜单操作方法&#xff0c;能够极大的减少显示界面开发工作量。 使用的2.08寸OLED显示屏&#xff0c;字库芯片为GT30L32S4W&#xff0c;支持多种字号中英文。 官方提供了很完善的参考资料&#xff0c;包括…

结构体联合体枚举和位段

文章目录 结构体结构体类型的声明特殊的声明 结构的自引用结构体变量的定义和初始化结构体内存对齐为什么要内存对齐结构体传参结构体实现位段&#xff08;位段的填充&可移植性&#xff09;位段位段的内存分配空间如何开辟位段的跨平台问题位段的应用 枚举枚举类型的定义枚…

鸿蒙Harmony应用开发—ArkTS声明式开发(容器组件:Column)

沿垂直方向布局的容器。 说明&#xff1a; 该组件从API Version 7开始支持。后续版本如有新增内容&#xff0c;则采用上角标单独标记该内容的起始版本。 子组件 可以包含子组件。 接口 Column(value?: {space?: string | number}) 从API version 9开始&#xff0c;该接口…

vscode 生成树状图工具:project-tree

按下快捷键“CtrlShiftP”, 在弹框中输入 Project Tree&#xff0c;然后敲回车即会在根目录自动生成README.md&#xff08;如果之前没有的话&#xff09;。

pytorch 入门基础知识二(Pytorch 02)

一 微积分 1.1 导数和微分 微分就是求导&#xff1a; %matplotlib inline import numpy as np from matplotlib_inline import backend_inline from d2l import torch as d2l def f(x):return 3 * x ** 2 - 4 * x 定义&#xff1a; 然后求 f(x) 在 x 1 时的导数&#xff…

HarmonyOS NEXT应用开发—折叠屏音乐播放器方案

介绍 本示例介绍使用ArkUI中的容器组件FolderStack在折叠屏设备中实现音乐播放器场景。 效果图预览 使用说明 播放器预加载了歌曲&#xff0c;支持播放、暂停、重新播放&#xff0c;在折叠屏上&#xff0c;支持横屏悬停态下的组件自适应动态变更。 实现思路 采用MVVM模式进…

【Algorithms 4】算法(第4版)学习笔记 18 - 4.4 最短路径

文章目录 前言参考目录学习笔记0&#xff1a;引入介绍1&#xff1a;APIs1.1&#xff1a;API&#xff1a;加权有向边1.2&#xff1a;Java 实现&#xff1a;加权有向边1.3&#xff1a;API&#xff1a;加权有向图1.4&#xff1a;Java 实现&#xff1a;加权有向图1.5&#xff1a;AP…

Unity类银河恶魔城学习记录10-12 p100 Improve aliments - chill源代码

Alex教程每一P的教程原代码加上我自己的理解初步理解写的注释&#xff0c;可供学习Alex教程的人参考 此代码仅为较上一P有所改变的代码 【Unity教程】从0编程制作类银河恶魔城游戏_哔哩哔哩_bilibili CharacterStats.cs using System.Collections; using System.Collections…