当前位置: 首页 > news >正文

最大异或对(每周一类)

        今天我们来看这个最大异或类这道题 最大异或对 

        1.首先,我们先来了解一下异或是什么,之后还要讲一下同或。

        众所周知,数字在计算机中是由二进制来表示的,比如十进制的7,用二进制表示就是 111,十进制的3,用二进制表示就是011,。形象一点表示如下图:

        3与7进行异或操作就是将二进制相同的地方变成0,不同的地方变成1,在示例中,就变成了4。

        简单理解,就异(不一样的地方)变成1,。

        同或就是相反,同(相同的地方)变成1,不相同的地方变成0。

        好,在理解了基础概念再看这道题,就是我们用暴力的方法,就是两重循环,一个个来做异或,比较他们的大小,最后找出最大的异或对。在c++中,异或的运算符号是^,比如要计算a异或b,就写 a ^ b 就好。

        在理解了题意之后,我们来做一下代码(暴力):

#include <iostream>
#include <algorithm>using namespace std;
const int N = 100010;int main(){int n;cin >> n;int a[N];for(int i = 0; i < n ; i ++ ){scanf("%d",&a[i]);}int res = -1;for(int i = 0; i < n ; i ++ ){for(int j = i + 1; j < n; j ++ ){int x = a[i]^a[j];res = max(res,x);}}printf("%d\n",res);return 0;
}

        时间复杂度是O(n^2)有点太大了,我们要进行优化,方法就是 Trie 树,由于对于每一个数,我们总有办法找到最好的,能匹配它的数,使得他们的异或值最大,如下图,我们找和十进制的 5 匹配的数字,5变成二进制是101,我们要找的就是二进制是010的数字,就是2。

        按照这个思路,我们在存进去一个数的时候,就可以存储Trie树,当查找最大值的时候,我们就可以对刚刚暴力循环的第二层进行优化之后的查找,效率会更高。具体代码如下:

#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(){int n;cin >> 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",res);return 0;
}

        和上一节一样,我们存储的时候要定义索引 p ,刚开始是 0 ,随着 idx 的增加,而递增,用于判断不同的数字变成的二进制串,如果输入的串存在,那么就继续;如果不存在,就创建。在查找的时候,如果查找的串存在,就继续,如果不存在,就输出相反字符,比如我们对 101 的 期望是 010,但如果没有 010 ,只有 011,我们就找 011串。

        其中对于每一个数字的处理,我们是从高位到低位进行处理,我们从31到0位进行存入或者查找。

        这节课可以参照着上节课一起看,将Trie树的模版掌握并会自己写,就可以迎刃而解


http://www.mrgr.cn/news/45752.html

相关文章:

  • 永磁同步电机环路反步法(backstepping)控制
  • 解决重写QSilder::sliderPress后点击位置与滑块显示位置不一样的问题
  • docker compose入门1—概念介绍
  • open3D release版配置及简单使用
  • 『网络游戏』业务系统基类【08】
  • 网络信息安全法律与政策文件
  • 大厂面试真题-说说AtomicInteger 线程安全原理
  • 如何实现一个基于 HTML+CSS+JS 的任务进度条
  • Windows无需管理员权限,命令轻松修改IP和DNS
  • 【C语言刷力扣】1436.旅行终点站
  • 构建MySQL健康检查Web应用
  • 【陪诊系统】打包问题
  • 上半年的一些感想总结(不务正业)
  • Python中的“异常捕获艺术”:如何优雅地处理程序中的那些“不速之客”
  • Cannon-ES中RaycastVehicle的深入探索与实践
  • 2024_10_8 系统进展
  • python学习记录8
  • MES系统:制造业的智能大脑
  • Java中对象和对象变量
  • 【深度学习】yolov8n模型的剪枝操作记录