首页 > ACM题库 > HDU-杭电 > HDU 4825-Xor Sum-字典树-[解题报告]HOJ
2015
09-18

HDU 4825-Xor Sum-字典树-[解题报告]HOJ

Xor Sum

问题描述 :

Zeus 和 Prometheus 做了一个游戏,Prometheus 给 Zeus 一个集合,集合中包含了N个正整数,随后 Prometheus 将向 Zeus 发起M次询问,每次询问中包含一个正整数 S ,之后 Zeus 需要在集合当中找出一个正整数 K ,使得 K 与 S 的异或结果最大。Prometheus 为了让 Zeus 看到人类的伟大,随即同意 Zeus 可以向人类求助。你能证明人类的智慧么?

输入:

输入包含若干组测试数据,每组测试数据包含若干行。
输入的第一行是一个整数T(T < 10),表示共有T组数据。
每组数据的第一行输入两个正整数N,M(<1=N,M<=100000),接下来一行,包含N个正整数,代表 Zeus 的获得的集合,之后M行,每行一个正整数S,代表 Prometheus 询问的正整数。所有正整数均不超过2^32。

输出:

输入包含若干组测试数据,每组测试数据包含若干行。
输入的第一行是一个整数T(T < 10),表示共有T组数据。
每组数据的第一行输入两个正整数N,M(<1=N,M<=100000),接下来一行,包含N个正整数,代表 Zeus 的获得的集合,之后M行,每行一个正整数S,代表 Prometheus 询问的正整数。所有正整数均不超过2^32。

样例输入:

2
3 2
3 4 5
1
5
4 1
4 6 5 6
3

样例输出:

Case #1:
4
3
Case #2:
4

题目链接:hdu 4825 Xor Sum

题目大意:中文题。

解题思路:将给定得数按照二进制建成一颗字典树,每一层分别对应的各个位数上的01状态。然后每一次查询,如果对应位置为0,则要往1的方向走,如果是1,则要往0的方向走。但是要注意,走的前提是对应分支是存在的。

#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;
//typedef __int64 ll;
typedef long long ll;

const int M = 55;
const int N = M*1e5;

struct Node {
    ll val;
    int l;
    int r;

    void clear() {
        l = r = -1;
    }
}node[N];

int p;
ll a, t[M];

void insert (int& root, int d, ll u) {

    if (root == -1) {
        root = p++;
        node[root].clear();
    }

    if (d == -1) {
        node[root].val = u;
        return;
    }

    if (u & t[d])
        insert(node[root].r, d - 1, u);
    else
        insert(node[root].l, d - 1, u);
}

void query(int root, int d, ll u) {

    if (d == -1) {
        printf("%lld\n", node[root].val);
        return;
    }

    if (((u & t[d]) && node[root].l != -1) || node[root].r == -1)
        query(node[root].l, d - 1, u);
    else
        query(node[root].r, d - 1, u);
}

int main () {
    int cas, n, m;
    scanf("%d", &cas);

    t[0] = 1;
    for (int i = 1; i < 55; i++)
        t[i] = t[i-1] * 2;

    for (int i = 1; i <= cas; i++) {
        p = 0;
        int root = -1;

        scanf("%d%d", &n, &m);
        for (int j = 0; j < n; j++) {
            scanf("%lld", &a);
            insert(root, 50, a);
        }

        printf("Case #%d:\n", i);
        for (int j = 0; j < m; j++) {
            scanf("%lld", &a);
            query(root, 50, a);
        }
    }
    return 0;
}

参考:http://blog.csdn.net/keshuai19940722/article/details/26517269


  1. 我就是用opera,话说opera支持的是标准html,firefox能正常显示,opera也应该能吧。你可以用Chrome里的审核元素看看是哪里出问题了。

  2. 1945年,一位非籍少女latualatuka,乘一艘灰色小漂到美国,一位神秘男人杀死了她,并在脊背上割了latualatuka几个字母,一星期后,这消息已经传到亚洲,现在你已经看完这条信息,她会在一星期内飘到你家,夺取你最重要家人的性命,解咒方法只有完

  3. 別搞笑我了… 看這些評論的分析我真的笑趴了.. 團藏早就自己用里四象封印…哪裡來的回收.. 屍體都沒了..真的好搞笑… 你們的分析完全牛頭不對馬嘴

  4. 別搞笑我了… 看這些評論的分析我真的笑趴了.. 團藏早就自己用里四象封印…哪裡來的回收.. 屍體都沒了..真的好搞笑… 你們的分析完全牛頭不對馬嘴

  5. 別搞笑我了… 看這些評論的分析我真的笑趴了.. 團藏早就自己用里四象封印…哪裡來的回收.. 屍體都沒了..真的好搞笑… 你們的分析完全牛頭不對馬嘴

  6. 別搞笑我了… 看這些評論的分析我真的笑趴了.. 團藏早就自己用里四象封印…哪裡來的回收.. 屍體都沒了..真的好搞笑… 你們的分析完全牛頭不對馬嘴

  7. 別搞笑我了… 看這些評論的分析我真的笑趴了.. 團藏早就自己用里四象封印…哪裡來的回收.. 屍體都沒了..真的好搞笑… 你們的分析完全牛頭不對馬嘴

  8. 別搞笑我了… 看這些評論的分析我真的笑趴了.. 團藏早就自己用里四象封印…哪裡來的回收.. 屍體都沒了..真的好搞笑… 你們的分析完全牛頭不對馬嘴

  9. 別搞笑我了… 看這些評論的分析我真的笑趴了.. 團藏早就自己用里四象封印…哪裡來的回收.. 屍體都沒了..真的好搞笑… 你們的分析完全牛頭不對馬嘴

  10. ዏ高仿鞋ዏPaul Homme(大嘴猴)维思努比阎双/哈品Lucky BrandJuicy Couture (橘滋)奇安马可·罗伦兹(Gianmarco Lorenzi)Max Mara(麦丝玛拉)微信:LoveMeJck

  11. 黑丝袜网ࢬ丝袜诱惑17pࢬ黑丝袜美女ࢬ美腿诱惑ࢬ紫色丝袜ࢬ丝袜生活照ࢬU3E.518mei.com