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

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

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

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

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

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

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

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

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