[28. Maximum XOR pair]

summary

• The largest XOR pair is in a given number , Find two numbers to make , The result of exclusive or of these two numbers is the largest .
• It is generally used Violence law and Dictionary tree Methods .

Violent writing

#include <iostream>
#include <algorithm>
using namespace std;

const int N  = 100010;
int a[N];
int main()
{
    
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i ++)
    {
    
      scanf("%d", &a[i]);
    }
    int res = 0;
    for (int i = 0; i < n; i ++)
    {
    
        for (int j = 0; j < i; j ++)
        {
    
            res = max(res, a[i] ^ a[j]);
           
        }
    }
    cout << res << endl;
    return 0;
   
}

Dictionary tree optimization

The building process

• Start from the top , Because in the XOR process （ Dissimilarity is 1, Same as 0）, We try to satisfy High maximum .

Program realization

void insert(int x)
{
    
    int p = 0;                                        // The root node 
    for (int i = 30; i >= 0; i --)                    // Start with the largest bit 
    {
    
        int u = x >> i & 1;                           // take X Of the i What is the binary number of bits  x>>k&1( The front template )
        if (!son[p][u]) son[p][u] = ++ idx;           // If no child node is found in the insertion , Take this road 
        p = son[p][u];                                // The pointer points to the next layer 
    }
}

Find the maximum XOR result

Exclusive or

• Both numbers are converted to binary , If two bits are the same, XOR is followed by 0, Different XOR is 0.（ Dissimilarity is 1, Same as 0）

Realization

• When there is no number of root nodes , Let's first insert a number
• When inserting the second number again , You should XOR with the first number inserted first .
• When inserting the third number again , It should be XOR with all numbers inserted before , Get the maximum .

How to find the largest

• For everyone , For example, the current highest level is 1, In order to maximize the post XOR value , We need to find the highest position is 0 Exclusive or of , In this way, the final result is the biggest
• If the number after XOR is 1, best , If not , It can only be 0.

Code implementation

int query(int x)
{
    
    int p = 0, res = 0;  // use res To access the number represented by the current path 
    for (int i = 30; i >= 0; i --)                   // Start with the largest bit 
    {
    
        int u = x >> i & 1;
        if (son[p][!u])                              // If the current layer has a corresponding different number 
        {
    
            p = son[p][!u];                          //p The pointer points to different numbers of addresses 
            res = res * 2 + !u;                      //*2 Represents a shift to the left , Add the next one 
        }                                            // for example  001 * 2 = 0010  The next one is 1,
                                                     // 0010 + 1 = 00101
                                                                                 
        else
        {
    
            p = son[p][u];
            res = res * 2 + u;
        }
       
    }
    return res;
}

subject

Code

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010, M = 31 * N;
int son[M][2];   //M Number of representative nodes (M Represents how long a binary string of numbers can go ),2 There are only two branches , One is 0, One is 1

int a[N];
int idx;

void insert(int x)
{
    
    int p = 0;                                        // The root node 
    for (int i = 30; i >= 0; i --)                    // Start with the largest bit 
    {
    
        int u = x >> i & 1;                           // take X Of the i What is the binary number of bits  x>>k&1( The front template )
        if (!son[p][u]) son[p][u] = ++ idx;           // If no child node is found in the insertion , Take this road 
        p = son[p][u];                                // The pointer points to the next layer 
    }
}

int query(int x)
{
    
    int p = 0, res = 0;  // use res To access the number represented by the current path 
    for (int i = 30; i >= 0; i --)                   // Start with the largest bit 
    {
    
        int u = x >> i & 1;
        if (son[p][!u])                              // If the current layer has a corresponding different number 
        {
    
            p = son[p][!u];                          //p The pointer points to different numbers of addresses 
            res = res * 2 + !u;                      //*2 Represents a shift to the left , Add the next one 
        }                                            // for example  001 * 2 = 0010  The next one is 1,
                                                     // 0010 + 1 = 00101
                                                                                 
        else
        {
    
            p = son[p][u];
            res = res * 2 + u;
        }
       
    }
    return res;
}
int main()
{
    
    int n;
    scanf("%d", &n); 
    for (int i = 0; i < n; i ++)  scanf("%d", &a[i]);
    
    int res = 0;
    for (int i = 0; i < n; i ++)
    {
    
        insert(a[i]);
        int t = query(a[i]);                         //query(a[i]) Looking for a[i] The maximum and or value of the value 
        res = max(res, a[i] ^ t);
    }
    printf("%d\n", res);
    return 0;
   
}