首页 > 代码库 > 双剑合并

双剑合并

技术分享

1.建一颗字典树,然后依次查找

2.要delete,因为new的关系。

3.可以先把这道题做了:Xor Sum HDU - 4825

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<bitset>
 6 using namespace std;
 7 
 8 const int N=33;
 9 
10 struct node{
11     int num;
12     node* next[2];
13     node(){
14         num=0;
15         memset(next,0,sizeof(next));
16     }
17 };
18 
19 node* root=NULL;
20 
21 void build(int n){
22     bitset<N> bit=n;
23     node* rt=root;
24     for(int i=32;i>=0;i--){
25         int id=bit[i];
26         if(!rt->next[id]){
27             node* tem=new node();
28             rt->next[id]=tem;
29             rt=tem;
30         }
31         else rt=rt->next[id];
32     }
33     rt->num=n;
34 }
35 
36 int query(int m){
37     bitset<N> bit=m;
38     node* rt=root;
39     for(int i=32;i>=0;i--){
40         int id=bit[i];
41         if(rt->next[id^1]) rt=rt->next[id^1];
42         else rt=rt->next[id];
43     }
44     return rt->num;
45 }
46 
47 void del(node* root){
48     for(int i=0;i<2;i++){
49         if(root->next[i])
50            del(root->next[i]);
51     }
52     delete (root);
53 }
54 
55 int main()
56 {   int n;scanf("%d",&n);
57     while(n--){
58         int x,y;
59         scanf("%d%d",&x,&y);
60         root=new node();
61         for(int i=0;i<x;i++){
62             int tem;scanf("%d",&tem);
63             build(tem);
64         }
65         int ans=0;
66         for(int i=0;i<y;i++){
67             int sum;scanf("%d",&sum);    
68             ans=max(ans,sum^(query(sum)));    
69         }
70         printf("%d\n",ans);
71         del(root);
72     }
73 }

 

双剑合并