欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

CSU 1216异或最大值

程序员文章站 2022-10-04 16:04:11
Description 给定一些数,求这些数中两个数的异或值最大的那个值 Input 多组数据。第一行为数字个数n,1 Hint Source CSGrandeur的数据结构习题 异或运算符(^ 也叫xor(以后做题会遇到xor,就是异或)) 规则:0^0 = 0,0^1=1,1^0=1,1^1=0 ......

Description

给定一些数,求这些数中两个数的异或值最大的那个值

Input

多组数据。第一行为数字个数n,1 <= n <= 10 ^ 5。接下来n行每行一个32位有符号非负整数。

Output

任意两数最大异或值

Sample Input

3
3
7
9

Sample Output

14

Hint
Source
CSGrandeur的数据结构习题

异或

异或运算符(^ 也叫xor(以后做题会遇到xor,就是异或))
规则:0^0 = 0,0^1=1,1^0=1,1^1=0 参加位运算的两位只要相同为0,不同为1
例子:3^5 = 6(00000011^00000101=00000110)

暴力(不用说)

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
const int maxN = 1e5 + 7;

int a[maxN];

int main() {
    int n;
    scanf("%d",&n);
    for(int i = 1;i <= n;++ i) {
        scanf("%d",a[i]);
    }
    int maxn = 0;
    for(int i = 1;i < n;++ i) {
        for(int j = i + 1;j <= n;++ j) {
            maxn = max(maxn,a[i] xor a[j]);
        }
    }
    printf("%d",maxn);
}

正解:我们可以发现异或的一些性质,不同为1,根据等比数列求和,
等比数列求和

$2^1 + 2^2 + 2^3 + 2^4 < 2^5 $
证明: 设$2^1 + 2^2 + 2^3 + 2^4$为S,那么$2S = 2^2 + 2^3 + 2^4 + 2^5 - S$;
等于$2^5 - 1 < 2^5 $
为什么要涉及到这个呢,因为我们要贪心的选取,一定要看看有没有特殊情况.
我们从高位开始选择与其不同的二进制位.就Ok了.

code

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#define ll long long
using namespace std;
const int maxN = 1e5 + 7;

int a[maxN];
int son[maxN * 20][3],cnt;

void init() {
    memset(son,0,sizeof(son));
    cnt = 0;
    return;
}
void build(ll a) {
    int now = 0;
    for(int i = 32;i >= 0;-- i) {
        int qwq = (a >> i & 1);
        if( !son[now][qwq] )son[now][qwq] = ++ cnt;
        now = son[now][qwq];
    }
}

ll find(ll a) {
    ll res = 0,now = 0;
    for(int i = 32;i >= 0;-- i) {
        bool tmp = ((a >> i & 1) ^ 1);
        if(son[now][tmp]) now = son[now][tmp],res = res | (1LL << i);
        else now = son[now][tmp ^ 1];
    }
    return res;
}

int main() {
    int n;
    while(~scanf("%d", &n)) {
        init();
        for(int i = 1;i <= n;++ i) 
            scanf("%d",&a[i]);
        for(int i = 1;i <= n;++ i) 
            build(a[i]);
        ll Ans = 0;
        for(int i = 1;i <= n;++ i) {
            Ans = max(Ans,find(a[i]));
        } 
        printf("%lld\n",Ans);//一定要注意:换行!!!!
    }
}

上一篇: QT 启动shell脚本

下一篇: CSS进阶