最大异或对(Trie树）c++（个人纪录向）_C

首先异或就是每个十进制数都可以化为二进制数，然后将他们一一对比，相同的就是0，不同的就是1.比如3就是011，5就是101。那么3与5的异或是多少呢就是110也就是十进制的6

如上图所示确实如此。

简单的概念理清楚了之后。就可以来解题了。首先想想暴力解法

int ans=0;
for(int i=0;i

 
这样内层循环时间复杂度就是o(n)的,想办法优化一下就是用我们的trie树,把一个十进制数用二进制的形式存储到这样的一个树中 
我们先插入一个数，然后再在树中serach这个数的最大异或数，这样避免了重复寻找，也就是1号和3号匹配与3号和1号匹配是一样的道理。 
我们先写一下主函数: 
#include
using namespace std;
const int N=1e5+10;
const int M=31*M;//N个十进制数,最多需要31*N个节点

int s[M][2];//[2]是因为只存1和0两个数
int idx;
int cnt[M];
int a[N];//存要输入的数

int main(){
int n;
scanf("%d",&n);

for(int i=0;i
 
插入代码如下： 
int idx=0;

vodi insert(int x)
{
int p=0//用来记录当前的节点
for(int i=30;i>=0;i--){
int u=x>>i&i;
if(!s[p][u]){s[p][u]=++idx;//赋予节点
            p=s[p][u];
}
cnt[p]=x;//用于记录p这个节点存储的是哪个数，省去了后续需要计算的步骤。
} 
那么我们如何查询到与其异或的最大值呢,首先得从二进制的最高位开始查起，查与其相反的数 
比如你要查1101的最大异或数,首先你就要找其同一位上的为0的数就这样按顺序找下去，若是碰到没有相反的数，那只能沿着相同的那条路走下去。直至走到最后一位，既是答案。 
 
查询的代码如下： 
int search(int x){
int p=0;
for(int i=30;i>=0;i--){
    int u=x>>i&1;
    if(s[p][!u]){
    p=s[p][!u];//往其反的数走
}    else{//若无则接着往下走
        p=s[p][u];}

}return cnt[p];

} 
全部代码如下： 
#include
using namespace std;

const int N=1e5+10;
const int M=31*N;
int s[M][2];
int a[N];
int idx;
int cnt[M];
void insert(int x){
    int p=0;
    for(int i=30;i>=0;i--){
        int u=x>>i&1;
        if(!s[p][u])s[p][u]=++idx;
        p=s[p][u];
    }
    cnt[p]=x;
}
int quiry(int x){
    int p=0,res=0;
    for(int i =30;i>=0;i--){
        int u=x>>i&1;
        if(s[p][!u]){
            p=s[p][!u];
        }else{
            p=s[p][u];
        }
    }
    
    return cnt[p];
    
}
int main(){
    int n;
    scanf("%d",&n);
    int cnt=0;
    for(int i=0;i
 
					
										


					
						欢迎分享，转载请注明来源：内存溢出
原文地址: https://outofmemory.cn/langs/2889669.html

最大异或对(Trie树）c++（个人纪录向）

发表评论

评论列表（0条）