本文共 2894 字,大约阅读时间需要 9 分钟。
题目大意:求max( (a[i] + a[j]) ^ a[k] ) (i, j, k都不相同)
思路:暴力可搞
#include大神的0/1trie#include #include #include #include #include #include #include
#include#include #include using namespace std; int const MAX = 1e5; int a[MAX]; struct Trie { int root, tot, next[MAX][2], cnt[MAX], end[MAX]; inline int Newnode() { memset(next[tot], -1, sizeof(next[tot])); cnt[tot] = 0; end[tot] = 0; return tot ++; } inline void Init() { tot = 0; root = Newnode(); } inline void Insert(int x) { int p = root; cnt[p] ++; for(int i = 31; i >= 0; i --) { int idx = ((1 << i) & x) ? 1 : 0; if(next[p][idx] == -1) next[p][idx] = Newnode(); p = next[p][idx]; cnt[p] ++; } end[p] = x; } inline void Del(int x) { int p = root; cnt[p] --; for(int i = 31; i >= 0; i --) { int idx = ((1 << i) & x) ? 1 : 0; p = next[p][idx]; cnt[p] --; } } inline int Search(int x) { int p = root; for(int i = 31; i >= 0; i --) { int idx = ((1 << i) & x) ? 1 : 0; if(idx == 0) { if(next[p][1] != -1 && cnt[next[p][1]]) p = next[p][1]; else p = next[p][0]; } else { if(next[p][0] != -1 && cnt[next[p][0]]) p = next[p][0]; else p = next[p][1]; } } return x ^ end[p]; } }tr; int main() { int T; scanf("%d", &T); while(T--) { tr.Init(); int n, ma = 0; scanf("%d", &n); for(int i = 0; i < n; i++) { scanf("%d", &a[i]); tr.Insert(a[i]); } for(int i = 0; i < n; i++) { for(int j = i + 1; j < n; j++) { tr.Del(a[i]); tr.Del(a[j]); ma = max(ma, tr.Search(a[i] + a[j])); tr.Insert(a[i]); tr.Insert(a[j]); } } printf("%d\n", ma); } }
转载地址:http://dlali.baihongyu.com/