hdu 5536 || 2015 长春区域赛 J Chip Factory (带删除操作的trie树)
题意：给出n个数，然后问最大的(a[i]+a[j])^a[k] (i,j,k互不相同)
思路：异或和最大很容易想到字典树。。但是如何保证i,j,k互不相同这里没有想明白。。。。。我的想法是加一个标记代表之前的id，但是我加的标记是只有在叶子节点上才有的。。。也就是会出现走到了最后一步才发现这个节点是不能走的情况。。。
正确的做法是，加一个cnt标记。
每次插入的时候，这个数从根节点到叶子节点每个节点的cnt都+1
删除的时候做就是每个节点的cnt都-1.
这样子每次Find的时候只走cnt>0的点。。
这种做法的正确性基与：
两个不同的数。。一定有至少一位的二进制数不同。。。保证了当只出现过一次的数x被删掉以后，其他的数y的存在不会导致经过x的路径
** 两个相同的数，每一位二进制数位都是相同搞的。 **保证了id不同的相同的数。。即使一个被删掉。。另外的也可以继续访问。。。因为cnt仍然是大于0的。。。
1/* ***********************************************
2Author :111qqz
3Created Time :2016年08月15日 星期一 22时54分03秒
4File Name :code/hdu/5536.cpp
5************************************************ */
6#include <cstdio>
7#include <cstring>
8#include <iostream>
9#include <algorithm>
10#include <vector>
11#include <queue>
12#include <stack>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <deque>
19#include <ctime>
20#define fst first
21#define sec second
22#define lson l,m,rt<<1
23#define rson m+1,r,rt<<1|1
24#define ms(a,x) memset(a,x,sizeof(a))
25typedef long long LL;
26#define pi pair < int ,int >
27#define MP make_pair
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int LEN=32;
34const int N=1005;
35int n;
36char str[35];
37int a[N];
38struct Trie
39{
40 struct Node
41 {
42 Node *nxt[2];
43 int val;
44 int cnt;
45 Node()
46 {
47 for (int i = 0 ; i < 2 ; i++) nxt[i] = NULL;
48 cnt = 0 ;
49 }
50 };
51 Node *root;
52 void init()
53 {
54 root = new Node();
55 }
56 Trie()
57 {
58 root = new Node();
59 }
60 void Insert(char *s,int num)
61 {
62 Node *u = root;
63 int len = strlen(s);
64 for ( int i = 0 ; i < len ; i++)
65 {
66 int v = s[i]-'0';
67 if (u->nxt[v]==NULL) u->nxt[v] = new Node();
68 u=u->nxt[v];
69 u->cnt++;
70 }
71 u->val = num;
72 }
73 void Delete(char *s)
74 {
75 Node *u = root;
76 int len = strlen(s);
77 for ( int i = 0 ; i < len ; i++)
78 {
79 int v = s[i]-'0';
80 if (u->nxt[v]!=NULL)
81 {
82 u=u->nxt[v];
83 u->cnt--;
84 }
85 }
86 }
87 int Find(char *s)
88 {
89 Node *u = root;
90 int len = strlen(s);
91 for ( int i = 0 ; i < len ; i++)
92 {
93 int x = s[i]-'0';
94 int y = !x;
95 if (u->nxt[y]!=NULL&&u->nxt[y]->cnt>0)
96 u = u->nxt[y];
97 else u = u->nxt[x];
98 }
99 return u->val;
100 }
101}trie;
102void change(int x)
103{
104 for ( int i = LEN-1,j=0; i>=0 ; i--,j++)
105 str[i]=((x>>j)&1)+'0';
106}
107int main()
108{
109 #ifndef ONLINE_JUDGE
110 freopen("code/in.txt","r",stdin);
111 #endif
112 int T;
113 cin>>T;
114 while (T--)
115 {
116 scanf("%d",&n);
117 trie.init();
118 for ( int i = 1 ; i <= n ; i++)
119 {
120 scanf("%d",&a[i]);
121 change(a[i]);
122// cout<<" str:"<<str<<endl;
123 trie.Insert(str,a[i]);
124 }
125 int ans = 0 ;
126 for ( int i = 1 ; i <= n-1 ; i++)
127 {
128 change(a[i]);
129 trie.Delete(str);
130 for ( int j = i+1 ; j <= n ; j++)
131 {
132 change(a[j]);
133 trie.Delete(str);
134 change(a[i]+a[j]);
135 int cur = trie.Find(str)^(a[i]+a[j]);
136// cout<<"cur:"<<cur<<endl;
137 ans = max(ans,cur);
138 change(a[j]);
139 trie.Insert(str,a[j]);
140 }
141 change(a[i]);
142 trie.Insert(str,a[i]); //只是暂时性的删除。。查询玩记得再插回去。。。
143 }
144 printf("%d\n",ans);
145 }
146 #ifndef ONLINE_JUDGE
147 fclose(stdin);
148 #endif
149 return 0;
150}