每日一题 01trie专题 总结
The XOR Largest
Pair 奶牛异或
这前两道题比较简单，而且 我们直接运用01trie上查找最优值就可以，代码就不给了。
主要讲一下底下的几道题吧
Vitya and Strange Lesson
这道题我们首先要发现一个性质，就是其实我们每次xor上一个数的时候都是整体xor上，因此所有数之间相对的关系是不变的，所以我们只要记录这个xor上的值，剩下我们要查询的这个东西在trie上是可以二分的，于是我们在trie上二分这个mex就可以了，具体的我们如果这以为是t，那么因为我们首先是要求的是mex，那么要从0~1这样的一个过程，我们就让当前节点的t的这个儿子看看可以走满吗？如果可以那么就走否则我们t^1，并且加上当前的答案，大概就是一个这样的过程，这个做法还是比较清奇的，感觉这个思路也不错，这题的收获还是挺大的。
然后我们剩下就需要一个unique的过程，建立trie树的过程还是同上！
代码：
#include<bits/stdc++.h>
#define fgx cerr<<"-----------------------"<<endl
#define LL long long
#define DB double
#define pb push_back
using namespace std;
inline int read(){
int nm=0,fh=1; char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') fh=-1;
for(;isdigit(c);c=getchar()) nm=nm*10+c-'0';
return nm*fh;
}
#define M 300020
int n,m,a[M],xr,son[M<<5][2],siz[M<<5],tot;
inline void ins(int x){
int nw=0;
for(int i=20;~i;i--){
int t=(x&(1<<i))>0;
if(!son[nw][t]) son[nw][t]=++tot;
nw=son[nw][t],siz[nw]++;
}
}
inline int qry(int x){
int nw=0,ret=0;
for(int i=20;~i;i--){
int t=(x&(1<<i))>0;
if(siz[son[nw][t]]==(1<<i)) ret+=(1<<i),nw=son[nw][t^1];
else nw=son[nw][t];
if(!nw) return ret;
} return ret;
}
int main(){
n=read(),m=read();
for(int i=1;i<=n;i++) a[i]=read();
sort(a+1,a+n+1),n=unique(a+1,a+n+1)-a-1;
for(int i=1;i<=n;i++) ins(a[i]);
while(m--){
int x=read(); xr^=x;
printf("%d\n",qry(xr));
}
return 0;
}
Perfect Security
这道题相比上一道题就简单好多了，我们只需要考虑这个字典序的过程贪心，在trie树上查询带修就可以了
代码：
#include<bits/stdc++.h>
#define fgx cerr<<"-----------------------"<<endl
#define LL long long
#define DB double
#define pb push_back
using namespace std;
inline int read(){
int nm=0,fh=1; char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') fh=-1;
for(;isdigit(c);c=getchar()) nm=nm*10+c-'0';
return nm*fh;
}
#define M 300020
int n,a[M],b[M],son[M<<5][2],tot,sz[M<<5],ed[M<<5];
inline void ins(int x){
int nw=0;
for(int i=30;~i;i--){
int t=(x&(1<<i))>0;
if(!son[nw][t]) son[nw][t]=++tot;
nw=son[nw][t],sz[nw]++;
} ed[nw]=x;
}
inline int qry(int x){
int nw=0,ret=0;
for(int i=30;~i;i--){
int t=(x&(1<<i))>0;
if(sz[son[nw][t]]) nw=son[nw][t],sz[nw]--; else nw=son[nw][t^1];
} return ed[nw];
}
int main(){
n=read();
for(int i=1;i<=n;i++) a[i]=read();
for(int i=1;i<=n;i++) b[i]=read(),ins(b[i]);
for(int i=1;i<=n;i++) printf("%d ",a[i]^qry(a[i]));
puts(""); return 0;
}
Xor-MST
题意非常简单，但是乍一看没有任何想法
于是我们转换一下思路，我们考虑最小生成树的过程，我们按照边权排序然后能练就连
于是我们发现这题是要求异或的结果，那么我们也建一个trie树，于是我们考虑在一个trie上怎么考虑有关边权的相关。
首先有一个贪心的策略，我们考虑两个点u和v他们合并一定会在u和v的lca处合并，不可能在更上方，这样的边权一定是最优的，因此我们就可以分治在trie树上的每一个有两个儿子的几点上加速这个过程就可以了，
考虑到我们的深度是一个log的加上我们trie树的一个log，总复杂度是两个log的
代码：
#include<bits/stdc++.h>
#define fgx cerr<<"-----------------------"<<endl
#define LL long long
#define DB double
#define pb push_back
using namespace std;
inline int read(){
int nm=0,fh=1; char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') fh=-1;
for(;isdigit(c);c=getchar()) nm=nm*10+c-'0';
return nm*fh;
}
#define M 200020
#define INF 2000000000
int n,a[M],son[M<<5][2],tot=1,pl[M<<5],pr[M<<5];
inline void ins(int x,int p){
int nw=1;
for(int i=30;~i;i--){
int t=(x&(1<<i))>0;
if(!son[nw][t]) son[nw][t]=++tot;
nw=son[nw][t];
if(!pl[nw]) pl[nw]=p; pr[nw]=p;
}
}
inline int qry(int nw,int dep,int x){
int ret=0;
for(int i=dep;~i;i--){
int t=(x&(1<<i))>0;
if(son[nw][t]) nw=son[nw][t];
else nw=son[nw][t^1],ret+=(1<<i);
} return ret;
}
#define LS son[nw][0]
#define RS son[nw][1]
inline LL solve(int nw,int dep){
if(dep<0) return 0;
if(pl[LS]&&pl[RS]){
int ret=INF;
for(int i=pl[LS];i<=pr[LS];i++) ret=min(ret,qry(RS,dep-1,a[i]));
return solve(LS,dep-1)+solve(RS,dep-1)+(LL)ret+(1LL<<dep);
}
if(pl[LS]) return solve(LS,dep-1);
if(pl[RS]) return solve(RS,dep-1);
return 0;
}
int main(){
n=read();
for(int i=1;i<=n;i++) a[i]=read();
sort(a+1,a+n+1);
for(int i=1;i<=n;i++) ins(a[i],i);
printf("%lld\n",solve(1,30));
return 0;
}最大异或和
这道挺水的，就是忘了copy节点了，调了好长时间，要注意一下！！！
具体就是直接套路可持久化就可以了，可以强制在线，但是作者认为离线更好写就离线了。
代码：
#include<bits/stdc++.h>
#define fgx cerr<<"-----------------------"<<endl
#define LL long long
#define DB double
#define pb push_back
using namespace std;
inline int read(){
int nm=0,fh=1; char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') fh=-1;
for(;isdigit(c);c=getchar()) nm=nm*10+c-'0';
return nm*fh;
}
#define M 600020
#define INF 2000000000
int n,m,a[M],p[M],rt[M],son[M<<5][2],sz[M<<5],tot=1;
int typ[M],pl[M],pr[M],pn[M],X[M];
inline void ins(int nw,int pnw,int x){
for(int i=25;~i;i--){
int t=((x&(1<<i))>0); son[nw][t^1]=son[pnw][t^1];
son[nw][t]=++tot,nw=son[nw][t],pnw=son[pnw][t],sz[nw]=sz[pnw]+1;
}
}
inline int qry(int nw,int pnw,int x){
int ret=0;
for(int i=25;~i;i--){
int t=((x&(1<<i))>0);
if(sz[son[nw][t^1]]-sz[son[pnw][t^1]]>0) nw=son[nw][t^1],pnw=son[pnw][t^1],ret+=(1<<i);
else nw=son[nw][t],pnw=son[pnw][t];
} return ret;
}
int main(){
n=read(),m=read();
for(int i=1;i<=n;i++) a[i]=read(),p[i]=p[i-1]^a[i];
for(int i=1;i<=m;i++){
char ch[15]; scanf("%s",ch);
if(ch[0]=='A'){int x=read(); typ[i]=1,n++,p[n]=p[n-1]^x;}
else typ[i]=2,pn[i]=n,pl[i]=read(),pr[i]=read(),X[i]=read();
}
rt[0]=1; for(int i=1;i<n;i++) ins(rt[i]=++tot,rt[i-1],p[i]);
for(int i=1;i<=m;i++) if(typ[i]==2){
int x=X[i]^p[pn[i]],ret;
if(pl[i]==1) ret=x; else ret=x^p[pl[i]-1];
if(pl[i]<pr[i]) ret=max(ret,qry(rt[pr[i]-1],rt[pl[i]-1],x));
printf("%d\n",ret);
} return 0;
}
字节跳动成长空间 537人发布