Trie树应用(最大异或对)C++(Acwing)

代码:

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010, M = 3100010;

int n;
int a[N], son[M][2], idx;

void insert(int x)
{
    int p = 0;
    for (int i = 30; i >= 0; i -- )
    {
        int &s = son[p][x >> i & 1];
        if (!s) s = ++ idx;
        p = s;
    }
}

int search(int x)
{
    int p = 0, res = 0;
    for (int i = 30; i >= 0; i -- )
    {
        int s = x >> i & 1;
        if (son[p][!s])
        {
            res += 1 << i;
            p = son[p][!s];
        }
        else p = son[p][s];
    }
    return res;
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ )
    {
        scanf("%d", &a[i]);
        insert(a[i]);
    }

    int res = 0;
    for (int i = 0; i < n; i ++ ) res = max(res, search(a[i]));

    printf("%d\n", res);

    return 0;
}

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

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

相关文章

Java+SpringBoot:滑雪场管理的技术革新

✍✍计算机编程指导师 ⭐⭐个人介绍&#xff1a;自己非常喜欢研究技术问题&#xff01;专业做Java、Python、微信小程序、安卓、大数据、爬虫、Golang、大屏等实战项目。 ⛽⛽实战项目&#xff1a;有源码或者技术上的问题欢迎在评论区一起讨论交流&#xff01; ⚡⚡ Java实战 |…

【视频编解码】M-JPEG压缩、H.264压缩 对比

简介 参考这篇文章&#xff1a;https://blog.csdn.net/qq_41248872/article/details/83590337 写的比较好&#xff0c;这里就不赘述了。 我们在视频传输的时候&#xff0c;需要压缩&#xff0c;常见的压缩包括: jpeg 压缩h264 压缩 当然使用最多的还是 264, 毕竟他的压缩比…

我国无水氢氟酸产量逐渐增长 东岳集团市场占比较大

我国无水氢氟酸产量逐渐增长 东岳集团市场占比较大 无水氢氟酸是一种十分重要的化工产品&#xff0c;在常温常压下多表现为一种无色发烟液体。无水氢氟酸具有吸水性强、化学活性高、介电常数高、阻燃性能好等优点。经过多年发展&#xff0c;无水氢氟酸制备方法已经成熟&#xf…

【C++】 类与对象——流操作符重载,const成员函数

类与对象 流操作符重载1 << 重载2 >> 重载 const 修饰Thanks♪(&#xff65;ω&#xff65;)&#xff89;谢谢阅读&#xff01;&#xff01;&#xff01;下一篇文章见&#xff01;&#xff01;&#xff01; 流操作符重载 流操作符功能<<输出操作符>>输…

小程序--模板语法

一、插值{{}}语法 1、内容绑定 <view>{{iptValue}}</view> 2、属性绑定 <switch checked"{{true}}" /> Page({data: {iptValue: 123} }) 二、简易双向数据绑定 model:value&#xff1a;支持双向数据绑定 注&#xff1a;仅input和textarea支持&a…

QT编写工具基本流程(自用)

以后有人让你写工具的时候&#xff0c;可以方便用这个模版及时提高工作效率&#xff0c;可以争取早点下班。包含库目录&#xff0c;头文件目录&#xff0c;输出目录以及翻译和部署&#xff0c;基本上都全了&#xff0c;也可以做收藏用用。 文章目录 1、创建项目Dialog Widget都…

SpringBoot + Nacos + K8s 优雅停机

1 概念 2 用案例说话 案例前&#xff1a;k8s 停机流程 k8s springboot nacos 案例 案例优化 3 再次优化 mq 和 定时任务 流量控制 4 小结 1 概念 优雅停机是什么&#xff1f;网上说的优雅下线、无损下线&#xff0c;都是一个意思。 优雅停机&#xff0c;通常是指在设…

推荐“应用随机过程”学习材料

今天在检索资料的时候&#xff0c;无意间发现了这份由李东风老师的“应用随机过程 (pku.edu.cn)”。

LeetCode.105. 从前序与中序遍历序列构造二叉树

题目 105. 从前序与中序遍历序列构造二叉树 分析 这道题是告诉我们一颗二叉树的前序和中序&#xff0c;让我们根据前序和中序构造出整颗二叉树。 拿到这道题&#xff0c;我们首先要知道前序的中序又怎样的性质&#xff1a; 前序&#xff1a;【根 左 右】中序&#xff1a;…

LeetCode 450.删除二叉搜索树中的节点和669.修建二叉搜索树思路对比 及heap-use-after-free问题解决

题目描述 450.删除二叉搜索树中的节点 给定一个二叉搜索树的根节点 root 和一个值 key&#xff0c;删除二叉搜索树中的 key 对应的节点&#xff0c;并保证二叉搜索树的性质不变。返回二叉搜索树&#xff08;有可能被更新&#xff09;的根节点的引用。 一般来说&#xff0c;…

Python从进阶到高级—通俗易懂版

Python从进阶到高级—通俗易懂版 一、简介 Python 进阶是我一直很想写的&#xff0c;作为自己学习的记录&#xff0c;过去自己在看一些代码的时候经常会困惑&#xff0c;看不懂&#xff0c;然后自己去查资料、看书籍&#xff0c;慢慢的一个个弄懂&#xff0c;经常沉浸其中。关…

Spring Boot项目中TaskDecorator的应用实践

一、前言 TaskDecorator是一个执行回调方法的装饰器&#xff0c;主要应用于传递上下文&#xff0c;或者提供任务的监控/统计信息&#xff0c;可以用于处理子线程与主线程间数据传递的问题。 二、开发示例 1.自定义TaskDecorator import org.springframework.core.task.Task…

算法沉淀——穷举、暴搜、深搜、回溯、剪枝综合练习一(leetcode真题剖析)

算法沉淀——穷举、暴搜、深搜、回溯、剪枝综合练习一 01.全排列02.子集03.找出所有子集的异或总和再求和04.全排列 II05.电话号码的字母组合 01.全排列 题目链接&#xff1a;https://leetcode.cn/problems/permutations/ 给定一个不含重复数字的数组 nums &#xff0c;返回其…

BioTech - 大型蛋白质复合物的组装流程 (CombFold)

欢迎关注我的CSDN&#xff1a;https://spike.blog.csdn.net/ 本文地址&#xff1a;https://spike.blog.csdn.net/article/details/136187314 CombFold是用于预测大型蛋白质复合物结构的组合和分层组装算法&#xff0c;利用AlphaFold2预测的亚基之间的成对相互作用。CombFold的组…

C++学习:总结

#include <bits/stdc.h> using namespace std; int main() {int n;cin >> n;int a[n];for(int i0 ; i < n ;i ){cin >> a[i];}sort(a,a n);for(int i 0;i< n;i){cout << a[i] << " ";}cout << endl;// 请在此输入您的代…

IDEA查询对应功能的快捷键

首先要知道快捷键的key叫什么&#xff0c;然后通过key来找到对应的快捷键 比如下面这个查找删除导入未使用的类 跳转 或者安装对应插件

【sgCreateTableData】自定义小工具:敏捷开发→自动化生成表格数据数组[基于el-table]

源码 <template><!-- 前往https://blog.csdn.net/qq_37860634/article/details/136141769 查看使用说明 --><div :class"$options.name"><div class"sg-head">表格数据生成工具</div><div class"sg-container&quo…

设计模式----工厂模式

工厂模式 工厂模式即建立创建对象的工厂&#xff0c;实现创建者和调用者分离。 简单工厂模式&#xff1a;该模式对对象创建管理方式最为简单&#xff0c;因为他简单的对不同类对象的创建进行了一层薄薄的封装。该模式通过向工厂传递类型来指定要创建的对象。 工厂方法模式&am…

pip镜像源:清华镜像、阿里云镜像、豆瓣镜像与如何修改默认镜像源

pip镜像源&#xff1a;清华镜像、阿里云镜像、豆瓣镜像与如何修改默认镜像源 &#x1f308; 个人主页&#xff1a;高斯小哥 &#x1f525; 高质量专栏&#xff1a;【Matplotlib之旅&#xff1a;零基础精通数据可视化】 &#x1f3c6;&#x1f3c6;关注博主&#xff0c;随时获取…

MyBatis关联查询和部分主配置文件映射文件

一、主配置文件 注意必须按规定的结构来配置 设置&#xff08;settings&#xff09; 这是 MyBatis 中极为重要的调整设置&#xff0c;它们会改变 MyBatis 的运行时行为。 下表描述了设置中各项设置的含义、默认值等。 看mybatis <settings><setting name"useGe…