首页 > 代码库 > 双剑合并
双剑合并
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 }
双剑合并
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。