백준13505 두 수 XOR

작성일 | In

문제 링크

  • http://icpc.me/13505

사용 알고리즘

  • Trie

풀이

두 수를 xor해서 큰 결과가 나오게 하려면 서로 다른 비트가 많아야 합니다.

먼저 모든 숫자를 이진수로 변환해 트라이에 넣어줍니다.
큰 수를 만들어야 하므로 뒤에서부터 자신과 다른 비트를 따라가도록 탐색을 해주면 됩니다.

전체 코드

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
#include <bits/stdc++.h>
using namespace std;

vector<int> v;
char s[33];

struct Node{
	Node *child[2];
	Node(){
		child[0] = child[1] = 0;
	}
	~Node(){
		if(child[0]) delete child[0];
		if(child[1]) delete child[1];
	}
	void insert(char *s){
		if(*s == 0) return;
		int t = *s - '0';
		if(!child[t]) child[t] = new Node;
		child[t]->insert(s+1);
	}
	void query(char *s){
		if(*s == 0) return;
		int t = *s - '0'; t ^= 1;
		if(child[t]){
			*s = '1';
			child[t]->query(s+1);
		}else{
			*s = '0';
			child[t^1]->query(s+1);
		}
	}
};

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin >> n; v.resize(n);
	Node *root = new Node;
	for(auto &i : v) cin >> i;
	for(auto i : v){
		for(int j=31; j>=0; j--){
			if(i & 1) s[j] = '1';
			else s[j] = '0';
			i >>= 1;
		}
		s[32] = 0;
		root->insert(s);
	}
	int ans = -1;
	for(auto i : v){
		for(int j=31; j>=0; j--){
			if(i & 1) s[j] = '1';
			else s[j] = '0';
			i >>= 1;
		}
		s[32] = 0;
		root->query(s);
		int now = 0;
		int tmp = 1;
		for(int i=31; i>=0; i--){
			if(s[i] == '1') now |= tmp;
			tmp <<= 1;
		}
		ans = max(ans, now);
	}
	cout << ans;
}