最大异或对-Trie--acwing

最大异或对-Trie--acwing

建立树之后对树进行操作:将每个数与其他的进行 1匹配,次数最高不过30,然后求max即可

#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
#include <cstdio>
#include <stdio.h>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <iomanip>
#define rep(i,a,b) for(int i = a; i <= b ; i ++ )
#define pre(i,a,b) for(int i = b ; i >= a ; i --)
#define ll long long
#define inf 0x3f3f3f3f
#define ull unsigned long long
#define ios ios::sync_with_stdio(false),cin.tie(0)
using namespace std;
typedef pair<int,int> PII ;
const int N = 2e6 + 10;

int son[N][2],cnt[N],idx; //下标是0的点,既是根节点,也是空节点
int n;
int a[N];

void insert_digital(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 query(int x)
{
    int res=0,p=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()
{
    ios;
    cin>>n;
    rep(i,0,n-1){
        cin>>a[i];
        insert_digital(a[i]);
    }
    int res=0;
    rep(i,0,n-1){
        res=max(res,query(a[i]));
    }

    cout<<res<<endl;
}

  

 

最大异或对-Trie--acwing

上一篇:从本机到vmware win7虚拟机传输文件卡顿问题的解决


下一篇:PHP 反射API 例子