Blackops

初心易得，始终难守

0%

HDU 5536 Chip Factory（01字典树）

发表于 分类于 ， ，

Chip Factory

Time Limit: 18000/9000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 3814 Accepted Submission(s): 1678

Problem Description
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?

Input
The first line of input contains an integer T indicating the total number of test cases.

The first line of each test case is an integer n, indicating the number of chips produced today. The next line has n integers s1,s2,..,sn, separated with single space, indicating serial number of each chip.

1≤T≤1000
3≤n≤1000
0≤si≤109
There are at most 10 testcases with n>100

Output
For each test case, please output an integer indicating the checksum number in a line.

Sample Input
2
3
1 2 3
3
100 200 300

Sample Output
6
400

Source
2015ACM/ICPC亚洲区长春站-重现赛（感谢东北师大）

题目链接：HDU 5533
今天训练的时候队友突然跟我说减掉$k$一开始没听懂，后来想着确定$i$与$j$，然后把区间分成三段，用可持久化01字典树嘛，结果T了（暴力据说才6s，苦逼……）。然后有发现每一次查询前把$arr[i]$和$arr[j]$从字典树中删除，查询好再加回去不就好了吗，判断一条路可不可走就用$cnt$记录这条路被覆盖过几次即可，然后就是个大水题了，但是不知道为什么中间好几分钟没调出来样例……
代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <bitset>
#include <string>
#include <stack>
#include <cmath>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define fin(name) freopen(name,"r",stdin)
#define fout(name) freopen(name,"w",stdout)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 1010;
struct Trie
{
    int nxt[2], cnt, v;
    void init()
    {
        nxt[0] = nxt[1] = 0;
        cnt = v = 0;
    }
} L[N * 31];
int sz;
int arr[N];

void init()
{
    sz = 0;
    L[sz++].init();
}
inline int newnode()
{
    L[sz].init();
    return sz++;
}
void ins(int val)
{
    bitset<31>s(val);
    int u = 0;
    for (int i = 30; i >= 0; --i)
    {
        int v = s[i];
        if (!L[u].nxt[v])
            L[u].nxt[v] = newnode();
        u = L[u].nxt[v];
        ++L[u].cnt;
    }
    L[u].v = val;
}
void update(int val, int c)
{
    bitset<31>s(val);
    int u = 0;
    for (int i = 30; i >= 0; --i)
    {
        int v = s[i];
        u = L[u].nxt[v];
        L[u].cnt += c;
    }
}
int query(int val)
{
    bitset<31>s(val);
    int u = 0;
    for (int i = 30; i >= 0; --i)
    {
        int v = s[i];
        if (L[L[u].nxt[v ^ 1]].cnt)
            u = L[u].nxt[v ^ 1];
        else
            u = L[u].nxt[v];
    }
    return L[u].v;
}
int main(void)
{
    int TC, n, i, j;
    scanf("%d", &TC);
    while (TC--)
    {
        init();
        scanf("%d", &n);
        for (i = 1; i <= n; ++i)
        {
            scanf("%d", &arr[i]);
            ins(arr[i]);
        }
        int ans = 0;
        for (i = 1; i <= n; ++i)
        {
            for (j = i + 1; j <= n; ++j)
            {
                update(arr[i], -1);
                update(arr[j], -1);
                int t = arr[i] + arr[j];
                ans = max(ans, query(t)^t);
                update(arr[i], 1);
                update(arr[j], 1);
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}