1 条题解
-
0
#include <bits/stdc++.h> using namespace std; const int MAXNODE = 100000 * 31; // 单词数*单词长度(最坏情况下节点数量) int tot, root, son[MAXNODE + 5][2]; int tag[MAXNODE + 5]; // 存在几个单词 void clearNode(int nId) { for (int i = 0; i < 2; i++) son[nId][i] = 0; tag[nId] = 0; } void ins(int s) { int now = root; for (int i = 30; i >= 0; i--) { // s的2^i位是多少 int j = ((s >> i) & 1); if (!son[now][j]) { son[now][j] = ++tot; clearNode(tot); } now = son[now][j]; } } int check(int s) { int res = 0; int now = root; for (int i = 30; i >= 0; i--) { int j = ((s >> i) & 1); // 尽可能走不同的 if (son[now][1 - j]) { res += (1 << i); now = son[now][1 - j]; } else { now = son[now][j]; } } return res; } int n, x; int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n; cin >> x; tot = root = 1; clearNode(tot); ins(x); int ans = 0; for (int i = 2; i <= n; i++) { cin >> x; ans = max(ans, check(x)); ins(x); } cout << ans << "\n"; return 0; }
- 1
信息
- ID
- 692
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 3
- 标签
- 递交数
- 28
- 已通过
- 19
- 上传者