ACdream 1063 字典树
ACdream 1063 字典树
平衡树
神奇的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)。
以下 N 行,每行一个字符串一个数字,分别代表:
insert X ,加入数 X
qmax X ,求第2种操作的答案
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)
Source
buaads
Manager
题目名相当不厚道,很显然求xor最大最小值使用01 tree才对。
01字典树,同字典树,只是将数字当做01串进行处理,那么对于一个数,求最大xor就往方向走,求最小xor就往同方向走就好
#include<queue>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define ll long long
#define inf 1000000000
#define mod 1000000007
using namespace std;
int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
const int N=320000;
const int sigma=2;
int ch[N][sigma];
int var[N],sz;
void clear(){
sz=1;
memset(ch[0],0,sizeof(ch[0]));
}
void insert(int x){
int u=0;
for(int i=31;i>=0;i--){
int c=(x>>i)&1;
if(!ch[u][c]){
memset(ch[sz],0,sizeof(ch[sz]));
ch[u][c]=sz;
var[sz++]=0;
}
u=ch[u][c];
}
var[u]=x;
}
int search(int x){
int u=0;
for(int i=31;i>=0;i--){
int c=(x>>i)&1;
if(ch[u][c^1]) u=ch[u][c^1];
else u=ch[u][c];
}
return var[u];
}
int search2(int x){
int u=0;
for(int i=31;i>=0;i--){
int c=(x>>i)&1;
if(ch[u][c]) u=ch[u][c];
else u=ch[u][c^1];
}
return var[u];
}
int main(){
int T=read();
while(T--)
{
int n;
n=read();
clear();
char op[30];
int x;
ll tmp;
for(int i=0; i<n; i++)
{
scanf("%s",op);x=read();
if(strcmp(op,"insert")==0) insert(x);
else if(strcmp(op,"qmax")==0)
{
tmp=search(x);
printf("%lld\n",tmp^x);
}
else
{
tmp=search2(x);
printf("%lld\n",tmp^x);
}
}
}
return 0;
}
最新文章
- 【asp.net】Linux 部署 asp.net core 项目
- SqlServer按时间自动生成生成单据编号
- Android之设置横屏竖屏
- Docker实践(3)—浅析device mapper的thin provision
- THE ARCHITECTURE OF COMPLEXITY HERBERT A. SIMON* Professor of Administration, Carnegie Institute of Technology (Read April 26, 1962)
- C++开发必看 四种强制类型转换的总结 [转]
- 绑定线程到特定CPU处理器
- mount nfs的可选参数
- 关于css中的align-content属性详解
- codevs 1281 Xn数列 (矩阵乘法)
- mysql 权限分配及创建新用户
- 上传本地项目到Github
- 前端学习总结(一)——常见数据结构的javascript实现
- 【Leecode】两数相加
- java的线程
- Apache Solr入门教程(初学者之旅)
- wordpress学习(二)
- 添加/删除-HTML DOM 常用对象 -BOM-打开和关闭窗口- history-location
- Delphi实现DBGrid全选和反选功能
- nginx: [emerg] getpwnam(“www”) failed错误