ACM学习历程—CSU 1216 异或最大值（xor && 贪心 && 字典树）

题目链接：http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1216

题目大意是给了n个数，然后取出两个数，使得xor值最大。

首先暴力枚举是C(n, 2)，显然不行。

考虑每一个数，显然，从最高位开始，如果它能和某一个数xor，让最高位为1，效果肯定是最佳的。其次考虑次高位，以此类推。

简单说，就是x的某一位，如果能找到某些数与x这一位xor为1，则考虑这些数，然后比较下一位；否则，就直接考虑下一位。起始从最高位开始考虑。

在这种贪心策略下，用字典树保存搜索每一位的效率比较高。

需要注意的是，由于是xor运算，所以需要保证每一个数的位数一样长，因为是32位有符号的int型，于是统一成31位长。

还有就是，理论上需要先把所有数，存入字典树，然后讨论每一个数，但是对于一个x，如果它能和y这个数xor出最大值，那么不管是先存入了x，还是先存入了y，(x, y)这个数对是肯定会被讨论的。所以，完全可以存入一个数，就讨论一个数。

代码：

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <cstring>

#include <algorithm>

#include <set>

#include <map>

#include <queue>

#include <string>

#define LL long long

using namespace std;

const int maxN = ;

const int len = ;//len表示数的二进制最大长度

struct Trie

{

    int next[];

}tree[maxN*len];

int cnt, ans, n;

void initTree()

{

    cnt = ;

    memset(tree, -, sizeof(tree));

}

void add(int x)

{

    int now = ;

    bool k;

    for (int i = len; i >= ; i--)

    {

        k = x&(<<i);

        if (tree[now].next[k] == -)

            tree[now].next[k] = ++cnt;

        now = tree[now].next[k];

    }

}

//返回当前数中能和x合成最大数的数

int query(int x)

{

    int v = , now = ;

    bool k;

    for (int i = len; i >= ; i--)

    {

        k = x&(<<i);

        if (tree[now].next[!k] != -)

            k = !k;

        v = v|(k<<i);

        now = tree[now].next[k];

    }

    return v;

}

void work()

{

    ans = ;

    initTree();

    int x;

    for (int i = ; i < n; ++i)

    {

        scanf("%d", &x);

        add(x);

        ans = max(ans, x^query(x));

    }

    printf("%d\n", ans);

}

int main()

{

    //freopen("test.in", "r", stdin);

    while (scanf("%d", &n) != EOF)

    {

        work();

    }

    return ;

}

巴特西

ACM学习历程—CSU 1216 异或最大值（xor && 贪心 && 字典树）

最新文章

热门文章