说人话的01Trie（内有CF842D - Vitya and Strange Lesson题解）

68 阅读 0 评论 45 点赞

我是靠谱客的博主俏皮世界，最近开发中收集的这篇文章主要介绍说人话的01Trie（内有CF842D - Vitya and Strange Lesson题解），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

引言：

学习完trie树之后，我们知道可以快速处理一堆字符串，一堆数字呢？

认识01Trie

既然trie树比较与字符串亲近，我们就想方设法地把数字转成字符串

没错！就是二进制！

看图，是不是瞬间秒懂了呢？

01Trie的应用

给出一个集合，多次询问，每次给出一个数，求这个数和集合中的数的异或的最大值。

根据位运算的性质，高位越大越好。

按照数字的二进制建立 Trie，对于一个询问，从上往下走，贪心的选异或起来更大的方向走，直到走到叶子。

具体实现：

#include<bits/stdc++.h>
#define Rep(a,b,c) for(register int a=b;a<=c;a++)
#define Mem(d,e) memset(d,e,sizeof(d))
using namespace std;
int bits[25],a[300007],cnt=0,opt=0;
inline int in(){
int W=1,X=0;
char Ch=0;
while(!isdigit(Ch)){
if(Ch=='-') W=-1;
Ch=getchar();
}
while(isdigit(Ch))
X=(X<<3)+(X<<1)+(Ch^'0'),Ch=getchar();
return X*W;
}
inline void out(int M,char *s){
if(M<0) putchar('-'),M=-M;
if(M>9) out(M/10,"");
putchar(M%10+'0');
printf(s);
return;
}
inline void getbits(){
bits[0]=1;
Rep(i,1,19)
bits[i]=bits[i-1]<<1;
return;
}
struct Node{
int son[2],id;
};
struct Trie{
Node s[1<<24];
inline void build(){
Mem(s,0),getbits();
}
inline void add(int cur,int dep,int x){
if(dep<0) {
s[cur].id=x;
return;
}
bool tmp=bits[dep]&x;
add(s[cur].son[tmp]=++cnt,dep-1,x);
}
inline int query(int cur,int dep){
if(dep<0) return s[cur].id;
bool tmp=bits[dep]&opt;
if(s[cur].son[tmp^1]);
return query(s[cur].son[tmp^1],dep-1);
return query(s[cur].son[tmp],dep-1);
}
}A;
int main(){
int n,q;
n=in(),q=in();
A.build();
Rep(i,1,n)
a[i]=in();
sort(a+1,a+n+1);
n=unique(a+1,a+n+1)-a-1;
while(n)
A.add(0,19,a[n--]);
while(q--){
opt=in();
out(A.query(0,19),"n");
}
}

友情提醒：一定要去重！！！！！

特殊的01Trie（满血状态）

下面来看这道题（我是传送门）

题意简述:

维护一个长度为?的序列，每次给出一个? ，请进行如下操作：

1．把序列中的所有数和 ?异或

2．查询这个序列的 mex（最小的没有出现过的非负整数）

题目可以等价为：

给出一个集合，多次查询，每次查询给出一个 ?，问集合中所有数异或上?之后的 mex

建出 0/1 Trie，从上往下走。如果左儿子满了，就递归到右儿子，否则递归到左儿子，直到叶子即为答案。

一些巧妙地构想：

这道题所查询的答案可能是给出序列以外的，

所以我们要把这棵01trie插满，

于是它就变成了一棵满二叉树，

可以仿照线段树（静态开点）的方法，提高运行效率。

代码大放送：

#include<bits/stdc++.h>
#define Rep(a,b,c) for(register int a=b;a<=c;a++)
#define Mem(d,e) memset(d,e,sizeof(d))
using namespace std;
int bits[25],a[300007],cnt=0,opt=0;
inline int in(){
int W=1,X=0;
char Ch=0;
while(!isdigit(Ch)){
if(Ch=='-') W=-1;
Ch=getchar();
}
while(isdigit(Ch))
X=(X<<3)+(X<<1)+(Ch^'0'),Ch=getchar();
return X*W;
}
inline void out(int M,char *s){
if(M<0) putchar('-'),M=-M;
if(M>9) out(M/10,"");
putchar(M%10+'0');
printf(s);
return;
}
inline void getbits(){
bits[0]=1;
Rep(i,1,19)
bits[i]=bits[i-1]<<1;
return;
}
struct Trie{
int s[1<<24];
inline void build(){
Mem(s,0);
opt=0;
getbits();
}
inline void add(int cur,int dep,int x){
if(dep<0) {
s[cur]=1;
return;
}
bool tmp=bits[dep]&x;
int Nxt=(cur<<1)|tmp;
add(Nxt,dep-1,x);
s[cur]=s[Nxt]+s[Nxt^1];
}
inline int query(int cur,int dep,int num){
if(dep<0) return num;
bool tmp=bits[dep]&opt;
int Nxt=(cur<<1)|tmp;
if(s[Nxt]<bits[dep])
return query(Nxt,dep-1,num);
return query((Nxt^1),dep-1,num+bits[dep]);
}
}A;
int main(){
int n,q;
n=in(),q=in();
A.build();
Rep(i,1,n)
a[i]=in();
sort(a+1,a+n+1);
n=unique(a+1,a+n+1)-a-1;
while(n)
A.add(1,19,a[n--]);
while(q--){
opt^=in();
out(A.query(1,19,0),"n");
}
}