[Acwing] 143. 最大异或对 Tire树

前言

一看就是Tire树 一做就不会

思路

常规暴力解法: O n 2 n^2 n2 枚举出 所有选法取最大即可

使用Tire树优化第二层循环: O n l o g n nlogn nlogn , 使用Tire存放每个数的 二进制数 即 T i r e [ N ∗ 31 ] [ 2 ] Tire[N*31][2] Tire[N∗31][2]

然后我们在枚举每一个 a [ i ] a[i] a[i]的时候,

• 如果 a [ i ] a[i] a[i]是1 那么我们就走 0
• 反之则然

因此这样子就保证了对于每个 a [ i ] a[i] a[i]我们都可以取得最大值

CODE

#include 
using namespace std;
const int N = 1e5+10,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 += 1n;
    for(int i=0;i>a[i];
        insert(a[i]);
    }
    int res = 0;
    for(int i=0;i