首页 > 代码库 > CSU 1214 找最大异或值
CSU 1214 找最大异或值
题目大意:
给定一堆数,从中找2个数异或得到的最大值
直接暴力会超时,我们要考虑对于每一个数去匹配找到异或的最大值,我们希望2进制越前面的数尽可能都为1
所以我们用 0-1 字典树保存这些数,因为一个int型的正整数最多2进制到第30位,所以我们用31层高的字典树保存,第一层为root节点
每次查询操作都是对于当前数的2进制位查找,如果与之相反的方向有点,就往与之相反的方向向下找,这样异或才为1,没有,就顺着当前相同方向向下找,那样异或值为0
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 using namespace std; 5 6 int ans; 7 struct Node{ 8 int num; 9 Node *next[2];10 Node(){11 num = 0;12 next[0] = NULL;13 next[1] = NULL;14 }15 };16 17 Node *root = new Node();18 19 void add_node(int x)20 {21 int k = (x&(1<<30)) == 0?0:1;22 Node *q;23 if(!root->next[k]){24 root->next[k] = new Node();25 }26 q = root->next[k];27 for(int i = 29 ; i >= 0 ; i--){28 k = (x&(1<<i)) == 0?0:1;29 if(!q->next[k])30 q->next[k] = new Node();31 q = q->next[k];32 }33 q->num = x;34 }35 36 void query(int x)37 {38 int k = (x&(1<<30)) == 0?0:1;39 Node *q;40 if(!root->next[k^1]){41 q = root->next[k];42 }43 else q = root->next[k^1];44 for(int i = 29 ; i >= 0 ; i--){45 k = (x&(1<<i)) == 0?0:1;46 if(!q->next[k^1])47 q = q->next[k];48 else49 q = q->next[k^1];50 }51 // cout<<" get num : "<<q->num<<endl;52 ans = max(ans , q->num ^ x);53 54 }55 56 int main()57 {58 //freopen("test.in","rb",stdin);59 int n,a;60 while(~scanf("%d",&n)){61 root = new Node();62 ans = 0;63 for(int i=0;i<n;i++){64 scanf("%d",&a);65 add_node(a);66 query(a);67 //cout<<" jsd: "<<i<<" "<<ans;68 }69 70 printf("%d\n",ans);71 }72 return 0;73 }
CSU 1214 找最大异或值
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。