【CSU-1216】解题报告（01字典树，异或最大值）

原始题目

1216: 异或最大值

  • Time Limit: 2 Sec
  • Memory Limit: 128 Mb
  • Submitted: 1282
  • Solved: 460

Description

给定一些数，求这些数中两个数的异或值最大的那个值

Input

多组数据。第一行为数字个数\(n (1 \le n \le 10 ^ 5)\)。接下来\(n\)行每行一个32位有符号非负整数。

Output

任意两数最大异或值

Sample Input

3
3
7
9

Sample Output

14

Hint

Source

CSGrandeur的数据结构习题

题目大意

如题 # 解题思路 - 和HDU-4825都是求异或最大值，裸的01字典树 - 正解： - 每个数用二进制数表示，用32位的0、1数组（高位在前）储存到01字典树中。 - 对于每次询问q，将q也表示成01串，从高位到低位每次贪心的顺着字典树向下找相反的结点（0找1，1找0）， 因为这样可以保证让两个数的异或值尽可能地大（所以一定要从高位向下找）。

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cstdlib>
#include <set>
#include <string>
#include <cstring>
#include <stack>
#define rep(i,a,n) for(int i=a;i<n;i++)
#define per(i,a,n) for(int i=n-1;i>=a;i--)
#define ms(x,a) memset((x),(a),sizeof(a))
#define L 32
using namespace std;
const int maxn=1e5+5;
const int maxl=2;

typedef long long ll;
typedef struct Trie
{
	int v;
	Trie* next[maxl];
}Trie;
 
Trie *root;
void iniTrie()
{
	root=(Trie*)malloc(sizeof(Trie));
	for(int i=0;i<maxl;i++)
		root->next[i]=NULL;
	root->v=-1;
}

void creTrie(int a)
{
	int temp[35];
	int id=L-1;
	while(a){
		temp[id--]=(a&1);
		a/=2;
	}
	rep(i,0,id+1) temp[i]=0;
//	rep(i,0,L) cout<<temp[i];
//	cout<<endl<<endl;
	
	int l=L;
	Trie *p=root,*q;
	for(int i=0;i<l;i++)
	{
		int id=temp[i];
		//并非前缀不能有相同，而是不能在相同的分支上。 
		if(p->next[id]!=NULL) {
			p=p->next[id];
//			p->v++;
		}
		else{
			q=(Trie*)malloc(sizeof(Trie));
			q->v=1;
			for(int j=0;j<maxl;j++) q->next[j]=NULL;
			p->next[id]=q;
			p=p->next[id];
		}

	}
}

int findTrie(int a)
{
	int aa=a;
	int temp[35];
	int id=L-1;
	while(a){
		temp[id--]=(a&1);
		a/=2;
	}
//	cout<<"#"<<a<<endl;
	rep(i,0,id+1) temp[i]=0;
	
	int aans=0;
	Trie *p=root;
	int l=L;
	for(int i=0;i<l;i++){
		int index=!temp[i];
//		cout<<"index="<<index<<endl;
		if(p->next[index]!=NULL){
			aans=(aans<<1)+index;
			p=p->next[index];
		}
		else{
			aans=(aans<<1)+temp[i];
			p=p->next[temp[i]];
		}
	}
	return aans^aa;
}

void delTrie(Trie *p)  
{  
    int i;  
    for(i=0;i<maxl;i++)  
    {  
        if(p->next[i] != NULL)  
            delTrie(p->next[i]);  
    }  
    free(p);
//    printf("1");
	p==NULL;  
	return ;
}  

int a[maxn],n;

int main()
{
	ios::sync_with_stdio(false);
	while(cin>>n){
		iniTrie();
			rep(i,0,n){
			cin>>a[i];
			creTrie(a[i]);
		}
		int fans=0;
		rep(i,0,n){
			fans=max(fans,findTrie(a[i]));
		}
		cout<<fans<<endl;
		delTrie(root); 
	}
	
}

收获与反思

  • 异或最大值可以考虑01字典树。