浙江财经大学
信息管理与工程学院

ACDream 1063 平衡树

本文由 Ocrosoft 于 2016-08-18 14:12:47 发表

平衡树

Time Limit: 4000/2000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Problem Description

神奇的cxlove有一颗平衡树,其树之神奇无法用语言来描述 OrzOrz。 这棵树支持3种操作: 1、加入一个数到树中,维护平衡树的合法性; 2、给一个数X,用O(1)的时间求出来树中的数Y使得 Y ^ X 最大(异或操作, Pascal 写作 xor , 0 ^ 0 = 0 , 1 ^ 1 = 0 , 0 ^ 1 = 1 , 1 ^ 0 = 1 , 2 ^ 3 = 1) 3、给一个数X,用O(1)的时间求出来树中的数Y使得 Y ^ X 最小(异或操作, Pascal 写作 xor , 0 ^ 0 = 0 , 1 ^ 1 = 0 , 0 ^ 1 = 1 , 1 ^ 0 = 1 , 2 ^ 3 = 1) 请你帮忙实现这颗树。 cxlove由于过于牛,有些事情是无法做到的,你能在1s以内通过就好了。 最后补充一句,cxlove是世界冠军!

Input

第一行是数据组数T (T ≤ 100)

对于每组数据,第一行是操作数N (N ≤ 10000)

以下 行,每行一个字符串一个数字,分别代表:

  1. insert X ,加入数 X
  2. qmax X ,求第2种操作的答案
  3. qmin X ,求第3种操作的答案

输入保证不存在空树Query的情况 (1 ≤ X ≤ 1e9)

Output

对于操作 2 , 3 输出相应的答案。

Sample Input

1
4
insert 1
insert 2
qmin 1
qmax 1

Sample Output

0
3

Hint

Huge input and output. Please do not use: 1. cin ans cout of C++ 2. scanner of Java(Maybe BufferedReader is quicker)

Solution

字典树,转换成二进制放入,转回十进制取出…

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <stack>
#include <queue>
#include <ctime>
#include <string>
#include <cstdio>
#include <vector>
#include <cctype>
#include <climits>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
#define ms(a) memset(a,0,sizeof(a))
typedef long long ll;
const int INF = INT_MAX;
const int MAXN = 50000 + 10;
using namespace std;
struct Trie
{
	int ch[MAXN][3];
	int num;
	void insert(int x)
	{
		int u = 0;
		for (int i = 30; i >= 0; i--)
		{
			int s = ((1 << i)&x);//获取x的二进制表示的第i位
			if (s)
			{
				if (!ch[u][1])
				{
					num++;
					ch[u][1] = num;
				}
				u = ch[u][1];
			}
			else
			{
				if (!ch[u][0])
				{
					num++;
					ch[u][0] = num;
				}
				u = ch[u][0];
			}
		}
		return;
	}
	int qmin(int x)
	{
		int u = 0;
		int ret = 0;
		for (int i = 30; i >= 0; i--)
		{
			int s = ((1 << i)&x);
			if (s)
			{
				if (ch[u][1])
				{
					u = ch[u][1];
					ret += (1 << i);//转回10进制
				}
				else u = ch[u][0];
			}
			else
			{
				if (ch[u][0])u = ch[u][0];
				else
				{
					u = ch[u][1];
					ret += (1 << i);
				}
			}
		}
		return ret;
	}
	int qmax(int x)
	{
		int u = 0;
		int ret = 0;
		for (int i = 30; i >= 0; i--)
		{
			int s = ((1 << i)&x);
			if (s)
			{
				if (ch[u][0])
					u = ch[u][0];
				else
				{
					u = ch[u][1];
					ret += (1 << i);
				}
			}
			else
			{
				if (ch[u][1])
				{
					u = ch[u][1];
					ret += (1 << i);
				}
				else u = ch[u][0];
			}
		}
		return ret;
	}
}trie;
int main()
{
	int T;
	cin >> T;
	while (T--)
	{
		ms(trie.ch);
		trie.num = 0;
		int n;
		cin >> n;
		char s[10];
		for (int i = 1; i <= n; i++)
		{
			int x;
			scanf("%s%d", s, &x);
			if (!strcmp(s, "insert"))trie.insert(x);
			else if (!strcmp(s, "qmax"))printf("%d\n", trie.qmax(x)^x);
			else if (!strcmp(s, "qmin"))printf("%d\n", trie.qmin(x)^x);
		}
	}
	return 0;
}

欢迎转载,请保留出处与链接。Ocrosoft » ACDream 1063 平衡树

点赞 (0)or拍砖 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址