cf842D 01字典树|线段树 模板见hdu4825

一般异或问题都可以转换成字典树的问题,,我一开始的想法有点小问题,改一下就好了

下面的代码是逆向建树的,数据量大就不行

/*3
01字典树
根据异或性质,a1!=a2 ==> a1^x1^..^xn != a2^x1^..an
把修改转换成不同的询问
先把初始集合里没有的数建立成字典树
每次询问找的是字典树里异或x最小的值
*/
#include<bits/stdc++.h>
using namespace std;
#define maxn 300005
int buf[maxn];
void getbuf(int a){
for(int i=;i<=;i++)
buf[i]=a%,a/=;
for(int i=,j=; i<=j; i++,j--)
swap(buf[i],buf[j]);
} struct Trie{
int root,L;
int nxt[maxn*][],end[maxn*];
int newnode(){
nxt[L][]=nxt[L][]=-;
return L++;
}
void init(){
L=;root=newnode();
}
void insert(int a){
getbuf(a);
//for(int i=1;i<=20;i++)printf("%d ",buf[i]);
int now=root;
for(int i=;i<=;i++){
if(nxt[now][buf[i]]==-)
nxt[now][buf[i]]=newnode();
now=nxt[now][buf[i]];
}
end[now]=a;
}
int query(int a){//要找和a异或最小的数,就是碰到1时就往1走,碰到0时就往0走
getbuf(a);
//for(int i=1;i<=20;i++)printf("%d ",buf[i]);
int now=root;
for(int i=;i<=;i++){
if(nxt[now][buf[i]]==-)
now=nxt[now][buf[i]^];
else now=nxt[now][buf[i]];
}
return end[now];
}
}tr;
int n,m,flag[maxn],a,Max,x;
vector<int>v;
int main(){
tr.init();
cin>>n>>m;
for(int i=;i<=n;i++){
cin>>a;flag[a]=,Max=max(a,Max);
}
for(int i=;i<=;i++)
if(flag[i]==)v.push_back(i);
for(int i=;i<v.size();i++)
tr.insert(v[i]); m--,cin>>x;
printf("%d\n",tr.query(x)^x);
while(m--){
cin>>a;
x^=a;
printf("%d\n",tr.query(x)^x);
}
}

如果是把集合中存在的元素进行建树,就不会出现字典树大小无法确定的问题,但是每次查询要改一下,即如果第i位是1,那就往字典树的0子树找,反之往1子树找,并且如果先找的子树已经满了,即mex的结果不可能再这棵子树中找到,那么就往另一颗子树找即可

#include <stdio.h>
#include <string.h>
#include<iostream>
#define MAX(a,b) ((a)>(b)?(a):(b))
#define NODE 3200010
#define N 300010
using namespace std;
int n;
int v[N];
int node;
int next[NODE][];
int end[NODE];
int num[NODE][];
bool vis[NODE];
void add(int cur,int k)
{
memset(next[node],,sizeof(next[node]));
end[node]=;
next[cur][k]=node++;
}
int cal(int x)
{
int i,k,cur=,t1;
int res=;
for(i=;i>=;i--)
{
k=((<<i)&x)?:;
if(num[cur][k]>=<<(i)){
res+=<<i;
cur=next[cur][-k];
}else{
cur=next[cur][k];
}
if(cur==)break; //这里是为了当进入到一个个数为0的分支,可以直接break
}
//return (x^end[cur]); 如果是求最大值
return res;
}
int main()
{
int i,j,k,x,cur;
int ans,m;
//freopen("in.txt","r",stdin);
while(~scanf("%d %d",&n,&m))
{
node=;
memset(next[],,sizeof(next[]));
for(i=;i<n;i++)
{
scanf("%d",&x);
if(vis[x])continue;
vis[x]=;
v[i]=x;
cur=;
for(j=;j>=;j--)
{
k=((<<j)&x)?:;
if(next[cur][k]==)add(cur,k);
num[cur][k]++;
cur=next[cur][k];
}
end[cur]=x;
}
int t1,t2;
t1=;
for(ans=i=;i<m;i++){ //求最大值是max(ans,cal(v[i]))
cin >> t2;
t1^=t2;
cout << cal(t1) << endl;
}
}
return ;
}

另外这题用线段树解也可以,即建600000个结点,每个叶子结点维护的就是元素中的集合,然后每次查询还是按01字典树找最小异或值那一套方法就行了

上一篇:MySQL学习笔记_10_MySQL高级操作(下)


下一篇:Go Revel - Modules(模块)