最大差异对(每周一课)
今天我们来看这个最大异或类这道题 最大异或对
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树的模版掌握并会自己写,就可以迎刃而解
上一篇: 0、Verilog 基础知识专栏注释
下一篇: 代码随机器 103.
推荐阅读
-
最大差异对(每周一课)
-
RCWL-0516/RCWL-9196模块简介 & 微波感应模块简介-前言 RCWL-0516是一款由无锡日晨物联科技有限公司开发的微波感应模块(资料下载),见图0.0、图0.1,用于检测物体(人体)移动,具有以下特征: 1.穿透感应:可穿透适当厚度的玻璃、木板以及墙壁。 2.抗干扰:不受温度、灰尘等环境因素影响。 3.感应距离:5~8m(可调,见后文) 4.可重复触发、触发时间可调(见后文) 5.工作电压:3.3~18V 6.稳压输出:提供3.3V电压输出(最大100mA) 7.夜晚自动工作:外接光敏电阻和一个电阻实现 当模块检测到物体在感应范围内移动时,OUT引脚输出一段时间的高电平(该时间可通过电容“C-TM”调节,见后文);若在输出高电平期间再次检测到物体移动,高电平持续时间将延长一段时间(又称为重复触发),该时间不可叠加。 模块使用的注意事项如下,示意图见图0.2: 1. 感应面正前方不能有金属遮挡。 2. 感应面前后方预留2cm以上空间。若对灵敏度要求很高,应预留4cm以上距离,且模块后方遮挡空间应尽可能小。 3. 模块与安装载体平面尽可能平行。 4. 有元器件面为正感应面,反面为负感应面,负感应面效果略差。 5. 相同模块,单个个体之间间距应大于2m。 图0.0-模块实物图(正) 图0.1-模块实物图(反) 图0.2-感应区域示意图 原理 关于此模块的原理,有2种主流观点,这些观点所争论的焦点在于哪种解释是最主要的: 1. 以Roger Clark为代表的“反射”解释:模块上的振荡器会发射出微波信号,位于模块感应区域内的物体会反射模块所发出的微波信号,这些反射信号又被模块所接收,接收到的反射信号会改变流经晶体管发射极的电流I。外界环境不变的情况下,模块内部的调节电路会稳定振荡器,此时振荡器处于稳定状态,电流I也处于稳定;当外界环境发生变化(例如,有物体进入感应区域),该物体的反射信号会使振荡器暂时失去稳定,从而导致电流I发生变化。模块通过检测该电流I的变化,以检测物体移动。此过程中,发射频率的变化只是由于振荡器受反射信号影响而进入一个“暂稳态”所导致。 2.以Joe Desbonnet为代表的“多普勒效应”解释:位于模块感应区域内的物体会反射模块所发出的微波信号,这些反射信号的频率由于物体移动而发生改变(多普勒效应)。模块通过对比发射与反射频率的差异,以判断是否有物体进入感应区域。 应用 降低感应距离:模块背面丝印“R-GN”处添加1MΩ的电阻,模块的感应距离可降低到5m;如果不接,感应距离为7m。 调节触发时间:模块背面丝印“C-TM”处添加不同容值的电容,可以调节触发时间(“C-TM”电容容值的选择见后文);若不安装电容,触发时间为2~4s。 夜晚自动工作:模块正面丝印“CDS”处添加光敏电阻、模块背面丝印“R-CDS”处添加适当阻值的电阻,可控制模块在夜晚自动工作。“CDS”与“R-CDS”的选择方法见后文。 以上应用的实际电路请参考图1.0、图1.1。 图1.0-测试电路(正) 图1.1-测试电路(反) 测试 测试由5部分组成: 1.测量模块处于不同状态时的功耗,见表0.0。 2.未接入电阻“R-GN”时,测试模块最大感应距离,见表0.1。 3.接入电阻“R-GN”,测试模块最大感应距离,见表0.2。 4.以下步骤将介绍如何根据确定的光敏电阻“CDS”,选择电阻“R-CDS”的阻值,以实现模块夜间自动工作的功能。 1-白天,接入可调电阻“R-CDS”(推荐2MΩ)、光敏电阻“CDS”。 2-触发模块后(在模块面前走动),调节可调电阻,直到触发消失。再次尝试触发模块,正常情况下,模块应该无法被触发(如果可以触发,重复步骤2)。 3-将光敏电阻感光面遮住,尝试触发模块,正常情况下,模块应该可以被触发(如果无法触发,重复步骤3)。 4-此时可调电阻阻值即为电阻“R-CDS”的正确阻值。 5.电容“C-TM”分别接入不同容值的无极电容,测试模块单次触发所持续的时间,见表0.3。 测试条件 总电流(mA) 总功耗(mW) +5V供电电压,模块未触发 3.63 18.15 +5V供电电压,模块被触发 4.33 21.65 表0.0-模块功耗信息 正面最大感应距离(M) 6 反面最大感应距离(M) 2 表0.1-未接入电阻“R-GN”时,模块最大感应距离[1] 正面最大感应距离(M) 5 反面最大感应距离(M) 1 表0.2-接入电阻“R-GN”=1MΩ时,模块最大感应距离[1] 电容“C-TM”容值 悬空 103(10nF) 104(100nF) 224(220nF) 474(470nF) 105(1uF) 理论单次触发时间(s) 2~4 6 30 66 140 300 实际单次触发时间(s) 3 6 32 67 122 210 表0.3-电容“C-TM”容值 vs. 模块单次触发持续时间 结论 RCWL-0516是一款性价比高的人体感应模块,具有以下优缺点: 优点: