Run ID | 作者 | 问题 | 语言 | 测评结果 | 分数 | 时间 | 内存 | 代码长度 | 提交时间 |
---|---|---|---|---|---|---|---|---|---|
33473 | _ | Chip Factory | C++ | 通过 | 100 | 653 MS | 512 KB | 1493 | 2021-12-06 13:56:22 |
#include <bits/stdc++.h> using namespace std; struct Node { int son[2], sz; Node(): sz(0) { son[0] = son[1] = 0; } }; struct Trie01 { static const int MAXD = 30; vector<Node> nodes; Trie01() { nodes.resize(2); } void add(int x, int val) { int cur(1); nodes[cur].sz += val; for (int i(MAXD); ~i; --i) { int dg(x >> i & 1); if (!nodes[cur].son[dg]) nodes[cur].son[dg] = nodes.size(), nodes.push_back(Node()); cur = nodes[cur].son[dg]; nodes[cur].sz += val; } } int getxor(int x) const { int cur(1), res(0); for (int i(MAXD); ~i; --i) { int dg(x >> i & 1); if (nodes[nodes[cur].son[dg ^ 1]].sz > 0) cur = nodes[cur].son[dg ^ 1], res ^= 1 << i; else cur = nodes[cur].son[dg]; } return res; } }; int read() { int x(0); char c(getchar()); while (c < '0' || c > '9') c = getchar(); while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getchar(); return x; } int main() { int T(read()); while (T--) { const int N(read()); vector<int> nums(N); Trie01 trie; for (int i(0); i != N; ++i) { nums[i] = read(); trie.add(nums[i], 1); } int res((nums[0] + nums[1]) ^ nums[2]); for (int i(0); i != N; ++i) { trie.add(nums[i], -1); for (int j(i + 1); j != N; ++j) { trie.add(nums[j], -1); res = max(res, trie.getxor(nums[i] + nums[j])); trie.add(nums[j], 1); } trie.add(nums[i], 1); } printf("%d\n", res); } return 0; }