C - 秋实大哥与快餐店
Time Limit: 1 Sec Memory Limit: 256 MB
题目连接
http://acm.uestc.edu.cn/#/contest/show/59
Description
朝为田舍郎，暮登天子堂。秋实大哥从小就怀抱有远大的理想，所以他开了一家快餐店。
秋实大哥根据菜的口感，给每一道菜一个唯一的CID，同时对于前来的客人，根据他们的口味喜好，秋实大哥会给每一个客人一个PID。
对于一个标号为PID的客人，他对标号为CID的菜的喜爱程度为PID∧CID(∧表示按位异或），该值越大表示越喜欢。
秋实大哥实在太忙了，现在他需要你来帮忙照看一下他的店铺。
Input
第一行包含一个整数n，表示秋实大哥的餐馆内现在有n道菜。
接下来一行包含n个整数，分别表示每一道菜的CID。
接下来一行包含一个整数m，表示接下来发生了m件事。
接下来的m行，每一行为以下两种事件之一：
0 c : 表示秋实大哥最新研制出一道标号为c的菜
1 p : 表示来了一位标号为p的客人，请你在已有的菜中找出一道他最喜爱的菜
1≤n，m≤100000，0≤PID，CID≤1000000。
Output
对于每一个1 p事件输出一个整数，表示该客人最喜欢的菜的标号
Sample Input
1
1
3
1 1
0 2
1 1
1
3
1 1
0 2
1 1
Sample Output
1
2
2
HINT
题意
题解：
字典树，因为是int范围，所以每个数拆成2进制 ，然后最多32位，然后直接插进去就好了，每次跑线段树的时候，都往反方向去跑就好了
代码：
#include <iostream>
#include <string.h>
#include <stdio.h> using namespace std;
typedef long long LL; class Trie
{
public:
Trie *next[];
Trie()
{
memset(next,NULL,sizeof(next));
}
}; Trie *root; void Insert(LL n)
{
Trie *p = root;
for(int i=;i>=;i--)
{
int id = (n >> i) & ;
if(p->next[id] == NULL)
p->next[id] = new Trie();
p = p->next[id];
}
} void Delete(Trie *T)
{
if(T == NULL) return;
for(int i=;i<;i++)
if(T->next[i] != NULL)
Delete(T->next[i]);
} LL Match(LL m)
{
m = ~m;
LL ans = ;
Trie *p = root;
for(int i=;i>=;i--)
{
ans <<= ;
int bit = (m >> i) & ;
if(bit)
{
if(p->next[])
{
p = p->next[];
ans++;
}
else
{
p = p->next[];
}
}
else
{
if(p->next[])
{
p = p->next[];
}
else
{
p = p->next[];
ans++;
}
}
}
return ans;
} int main()
{
int n,m;
root = new Trie();
scanf("%d",&n);
for(int i=;i<n;i++)
{
LL val;
scanf("%lld",&val);
Insert(val);
}
scanf("%d",&m);
while(m--)
{
int a;
scanf("%d",&a);
if(a==)
{
LL val;
scanf("%lld",&val);
Insert(val);
}
else
{
LL val;
scanf("%lld",&val);
printf("%lld\n",Match(val));
}
}
return ;
}