AcWing 143. 最大异或对

最大异或对

#include <iostream>

using namespace std;

const int N = 1e6 + 10, M = N * 3;
int n;
int a[N];
int son[M][2], cnt[N], idx;

void insert(int x){
    int p = 0;
    for(int i = 30; ~i; i--){
        int &s = son[p][x >> i & 1];
        if(!s) s = ++idx;
        //创建一个新节点
        p = s;
    }
}

int query(int x){
    int p = 0, res = 0;
    for(int i = 30; ~i; i--){
        int u = x >> i & 1;
        if(son[p][!u]){
	        res += 1 << i;
            //等价于 res = res * 2 + !u
            //但是用这个的话下面的 else 就要多写一行更新
            p = son[p][!u];
        }
        else p = son[p][u];
    }
    return res;
}
int main(){
	cin >> n;
	for(int i = 0; i < n; i++){
		cin >> a[i];
		insert(a[i]);
	}
	int res = 0;
	for(int i = 0; i < n; i++) res = max(res, query(a[i]));
	cout << res << endl;
	return 0;
}

# 小技巧！当我们写 i >= 0 的时候 它是等价于～i 的

以为当 i 是 -1 的时候 -1 在二进制里表示全是 1 所以取反是 0

# << 的优先级比 + 要小

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e6 + 10, M = 31 * N;

int n;
int a[N];
int son[M][2], idx;

void insert(int x){
    int p = 0;
    for(int i = 30; i >= 0; i--){
    //小技巧！当我们写 i >= 0 的时候 它是等价于 ~i 的
        int u = x >> i & 1; //这个是取出 x 的 第 i 位的二进制数是什么东西
        if(!son[p][u]) son[p][u] = ++idx;//如果说不存在x的话就把x创建出来
        p = son[p][u];//然后走到儿子上面去
    }
}

int query(int x){
    int p = 0, res = 0;
    for(int i = 30; i >= 0; i--){
        int u = x >> i & 1;
        //尽量往和当前这一位不同的方向走 如果不能走的话再走到当前这一位
        //因此先判断一下另外一个方向是否存在 如果存在的话 p就走到另外一个方向上去
        if(son[p][!u]){
            p = son[p][!u];
            res = res * 2 + !u;
        }
        else{
            p = son[p][u];
            res = res * 2 + u;
        }
    }
    
    return res;
    
    
}

int main(){
    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]);
        res = max(res, a[i] ^ t);
    }
    
    printf("%d\n", res);
    
    return 0;
}

# 问一下各位大佬，res 为什么要左移呀

更新 res 的值，每次把旧值乘以 2（这一步相当于左移一位）再加上当前值。
比如给你一个字符串类型的二进制数 str，让你转化成 10 进制数，就可以用下面这段代码实现

int res = 0;
for(int i = 0; i < str.size(); i ++) 
{
    res = res * 2 + (str[i] - '0');
    //也可以写成 res = res << 1 + (str[i] - '0');
}

# cin.tie (0); 什么作用呀？加速输入吗

c++ primer ，是解除与 cout 输出流的关联，这样每次 cin 或 cout 之前都不会刷新彼此的缓冲区

是的，作用好像和ios::sync_with_stdio(false)是等价的