중남대학 교 COJ 1216: 이 또는 최대 치 (데이터 구조)

1298 단어 데이터 구조ACM
중남대학 교 COJ 1216: 이 또는 최대 치 (데이터 구조)ACM
제목: COJ 1216
제목:  중국어 문제, 주 의 는 여러 조 의 사례 이다.
분석:  01Trie 로 만 들 었 어 요.
코드:
/*
*  Author:      illuz <iilluzen[at]gmail.com>
*  File:        coj1216.cpp
*  Create Date: 2014-07-27 14:18:44
*  Descripton:  trie
*/

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N = 100000<<5;

struct Trie {
	int a[2];
	int num;
} f[N];

int cnt, ans;

// insert x into the root which id is u, the deep is num
void insert(int x, int u, int num) {
	bool k;
	for (int i = num; i >= 0; i--) {
		k = (1<<i)&x;
		if (f[u].a[k] == -1)
			f[u].a[k] = ++cnt;
		u = f[u].a[k];
	}
	f[u].num = x;
}

// query xor
void query(int x, int u, int num) {
	bool k;
	for (int i = num; i >= 0; i--) {
		k = (1<<i)&x;
		if (f[u].a[!k] != -1)
			u = f[u].a[!k];
		else
			u = f[u].a[k];
	}
	ans = max(ans, f[u].num^x);
}

int main() {
	int n, t;
	while (~scanf("%d", &n)) {
		memset(f, -1, sizeof(Trie) * N);
		cnt = 0;
		ans = 0;
		while (n--) {
			scanf("%d", &t);
			insert(t, 0, 31);
			query(t, 0, 31);
		}
		printf("%d
", ans); } return 0; }

좋은 웹페이지 즐겨찾기