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

原始题目

Xor Sum

  • Time Limit: 2000/1000 MS (Java/Others)
  • Memory Limit: 132768/132768 K (Java/Others)
  • Total Submission(s): 4756
  • Accepted Submission(s): 2076

Problem Description

Zeus 和 Prometheus 做了一个游戏，Prometheus 给 Zeus 一个集合，集合中包含了\(N\)个正整数，随后 Prometheus 将向 Zeus 发起\(M\)次询问，每次询问中包含一个正整数 \(S\) ，之后 Zeus 需要在集合当中找出一个正整数 \(K\) ，使得 \(K\) 与 \(S\) 的异或结果最大。Prometheus 为了让 Zeus 看到人类的伟大，随即同意 Zeus 可以向人类求助。你能证明人类的智慧么？

Input

输入包含若干组测试数据，每组测试数据包含若干行。

输入的第一行是一个整数$ T(T < 10)\(，表示共有\)T$组数据。

每组数据的第一行输入两个正整数\(N,M( 1 <\le N,M \le 100000)\)，接下来一行，包含\(N\)个正整数，代表 Zeus 的获得的集合，之后\(M\)行，每行一个正整数\(S\)，代表 Prometheus 询问的正整数。所有正整数均不超过\(2^{32}\)。

Output

对于每组数据，首先需要输出单独一行”Case #?:”，其中问号处应填入当前的数据组数，组数从1开始计算。

对于每个询问，输出一个正整数K，使得K与S异或值最大。

Sample Input

2
3 2
3 4 5
1
5
4 1
4 6 5 6
3

Sample Output

Case #1:
4
3
Case #2:
4

Source

2014年百度之星程序设计大赛 - 资格赛

Recommend

liuyiding

题目大意

如题 # 解题思路 - 直接找的话复杂度O（m*n），会T（本题显然不可能这么简单啊） - 正解： - 每个数用二进制数表示，用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
130
131
132
133
134
135
#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 debugin freopen("in.txt","r",stdin)
#define debugout freopen("out.txt","w",stdout)
#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; 
}

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,t,m;

int main()
{
	ios::sync_with_stdio(false);
//	debugin;
//	debugout;
	cin>>t;
	rep(l,1,t+1){
		cout<<"Case #"<<l<<":"<<endl;
		cin>>n>>m; //n树m询问
		iniTrie(); 
		rep(i,0,n){
			cin>>a[i];
			creTrie(a[i]);
		}
		rep(i,0,m){
			cin>>a[i];
			cout<<findTrie(a[i])<<endl;
		}
		delTrie(root);
	}
	
}

收获与反思

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