HDU 5536 – Chip Factory [字典树+二进制]

Link

点击打开hdu题目链接

Problem

John is a manager of a CPU chip factory, the factory produces lots of chips everyday. To manage large amounts of products, every processor has a serial number. More specifically, the factory produces n chips today, the i-th chip produced this day has a serial number si.
At the end of the day, he packages all the chips produced this day, and send it to wholesalers. More specially, he writes a checksum number on the package, this checksum is defined as below:

maxi,j,k(si+sj)sk

which i,j,k are three different integers between 1 and n. And is symbol of bitwise XOR.
Can you help John calculate the checksum number of today?

Mean

题意就是给你N个数,让你选三个数,求出两数的和异或上另一个数,找出此值的最大值。

Analyse

这是2015年长春区域赛的题,不想再吐槽了,当时N3暴力可过,现在挂在hdu上不行了。

正解是字典树,其实就是一个普通的二叉树。把每个数都插在树上,枚举两个数,直接在树上找出异或最大值。涉及到节点的删除和查找,因此要注意赋值方法。

C++ Code

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1024;
int n, sz, v[maxn], ch[maxn*32][2], val[maxn*32];

void insert(int x, int d) {
    int u = 0;
    for(int i = 30; i >= 0; --i) {
        int id = (x >> i) & 1;
        if(ch[u][id] == 0) {
            val[sz] = 0;
            ch[u][id] = sz++;
        }
        u = ch[u][id];
        val[u] += d;
    }
}

int query(int x) {
    int u = 0, t = 0;
    for(int i = 30; i >= 0; --i) {
        int id = (x >> i) & 1;
        if(ch[u][id^1] && val[ch[u][id^1]]) {
            t |= (1<<i);
            u = ch[u][id^1];
        }
        else u = ch[u][id];
    }
    return t;
}

int main() {
    int T; scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        sz = 1; memset(ch, 0, sizeof(ch));
        for(int i = 0; i < n; ++i) {
            scanf("%d", v + i);
            insert(v[i], 1);
        }
        int ans = 0;
        for(int i = 0; i < n; ++i) {
            insert(v[i], -1);
            for(int j = i + 1; j < n; ++j) {
                insert(v[j], -1);
                ans = max(ans, query(v[i] + v[j]));
                insert(v[j], 1);
            }
            insert(v[i], 1);
        }
        printf("%d\n", ans);
    }
    return 0;
}

欢迎留言