HDU 4825 Xor Sum

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4825

题意:给定一个含有若干整数的序列,m个询问,在序列中找到一个数字与询问的数字异或的值最大。

思路:异或一般想到用二进制的方法来做。这里我们建立一个字典树,把序列中每个数字以二进制展开插入字典树中,并在叶节点处存储这个数字的值,对于每个询问,我们也将数字展开,贪心的从高到低进行搜索,因为异或就是不进位的加法,如果我们能找到这个数字当前位的值^1的节点,那么我们就能把当前位异或为1就能保证最后的结果最大,如果找不到就顺着当前位的值找下去就可以了。

#pragma comment(linker, "/STACK:102400000,102400000")
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <sstream>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define MOD 1e9+7
#define lson l,mid,root<<1
#define rson mid+1,r,root<<1|1
using namespace std;
typedef long long ll;
const int maxn=100000+5;
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);
template<typename T>
inline T read(T&x){
    x=0;int _f=0;char ch=getchar();
    while(ch<'0'||ch>'9')_f|=(ch=='-'),ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x=_f?-x:x;
}
struct Trie{
    int val;
    int next[2];
}tree[maxn*32];
int T,n,m,cnt;
void Insert(int x);
int Find(int x);
int main(){
    int cas=1;
    for (read(T);T;T--){
        read(n),read(m);
        tree[0].val=0;
        memset(tree[0].next,0,sizeof(tree[0].next));
        cnt=0;
        for (int i=1;i<=n;i++){
            int x;
            read(x);
            Insert(x);
        }
        printf("Case #%d:\n",cas++);
        for (int i=1;i<=m;i++){
            int x;
            read(x);
            printf("%d\n",Find(x));
        }
    }
    return 0;
}

void Insert(int x){
    int pos=0;
    for (int i=31;i>=0;i--){
        int c=((x>>i)&1);
        if (!tree[pos].next[c]){
            cnt++;
            tree[pos].next[c]=cnt;
            tree[cnt].val=0;
            memset(tree[cnt].next,0,sizeof(tree[cnt].next));
        }
        pos=tree[pos].next[c];
    }
    tree[pos].val=x;
}

int Find(int x){
    int pos=0;
    for (int i=31;i>=0;i--){
        int c=((x>>i)&1);
        if (!tree[pos].next[c^1]) pos=tree[pos].next[c];
        else pos=tree[pos].next[c^1];
    }
    return tree[pos].val;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注