【01字典树】hdu-5536 Chip Factory

【题目链接】

http://acm.hdu.edu.cn/showproblem.php?pid=5536

【题意】

求一个式子，给出一组数，其中拿出ai,aj,ak三个数，使得Max{ (ai+aj) ^ ak }

【题解】

其实这里就需要大家做一个删除的操作；

类似于dfs的恢复现场的操作即可。

【代码】

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 const int N = 1e5+10;
 6 int Son[N*31][2];
 7 int a[N],idx;
 8 int Cnt[N*31];
 9 void Insert( int x ){
10     int p = 0 ;
11     for(int i=30;~i;i--){
12         int t = x >> i & 1 ;
13         if( !Son[p][t] ){
14             Son[p][t] = ++idx;
15         }
16         p = Son[p][t];
17         Cnt[p] ++ ;
18     }
19 }
20 void Delete( int x ){
21     int p = 0 , tmp ;
22     for(int i=30;~i;i--){
23         int t = x >> i & 1 ;
24         if( !Son[p][t] ) break;
25         tmp = p ;
26         p = Son[tmp][t] ;
27         Cnt[Son[tmp][t]] --;
28     }
29 }
30 int Query(int x ){
31     int res = 0 , p = 0 ;
32     for(int i=30;~i;i--){
33         int t = x >> i & 1 ;
34         if( Son[p][t^1] && Cnt[Son[p][t^1]]){
35             res += 1 << i;
36             p = Son[p][t^1];
37         }else if( Son[p][t] && Cnt[Son[p][t]] ){
38             p = Son[p][t] ;
39         }else{
40             break;
41         }
42     }
43     return res ;
44 }
45 void Init(){
46     idx = 0 ;
47     memset( Son , 0 ,sizeof Son );
48     memset( Cnt , 0 ,sizeof Cnt );
49 }
50 int main()
51 {
52     int T,n;
53     scanf("%d",&T);
54     while(T--){
55         Init();
56         scanf("%d",&n);
57         for(int i=1;i<=n;i++){
58             scanf("%d",&a[i]);
59             Insert(a[i]);
60         }
61         int tmp,res=0;
62         for(int i=1;i<=n;i++){
63             for(int j=i+1;j<=n;j++){
64                 tmp = a[i] + a[j] ;
65                 Delete(a[i]);
66                 Delete(a[j]);
67                 res = max( res , Query(tmp) );
68                 Insert(a[i]);
69                 Insert(a[j]);
70             }
71         }
72         printf("%d
",res);
73     }
74     return 0;
75 }

View Code