Hdu 4825

從高位到地位建立字典樹，貪心查詢。

#include <bits/stdc++.h>using namespace std; const int maxn = 100000+5; typedef long long ll; ll bin[35]; int n,m; ll a[maxn],x;struct trie{int cnt;int ch[maxn*35][2];ll val[maxn*35];void init(){cnt=1;memset(ch[0],0,sizeof ch[0]);}void insert(ll a){int u=0;for(int i=32;i>=0;i--){ll t=a&bin[i];t>>=i;if(!ch[u][t]){memset(ch[cnt],0,sizeof ch[cnt]);val[cnt]=0;ch[u][t]=cnt++;}u=ch[u][t];}val[u]=a;}ll query(ll a){int u=0;for(int i=32;i>=0;i--){ll t=a&bin[i];t>>=i;if(ch[u][t^1]) u=ch[u][t^1];else u=ch[u][t];}return val[u];} }Trie;int main(){//freopen("in.txt","r",stdin);bin[0]=1;for(ll i=1;i<=35;i++) bin[i]=bin[i-1]*2ll;int T,cas=1;for(cin>>T,cas=1;cas<=T;cas++){scanf("%d%d",&n,&m);Trie.init();for(int i=1;i<=n;i++){scanf("%lld",&x);Trie.insert(x);}printf("Case #%d:\n",cas);for(int i=1;i<=m;i++){scanf("%lld",&x);printf("%lld\n",Trie.query(x));}}return 0; }

Hdu 5536

要求$(S_i+S_j) xor S_k$最大。
枚舉$S_i$和$S_j$將其從Trie中刪除，然后貪心查詢。
復雜度$O(n^2\log n)$.

#include <bits/stdc++.h>using namespace std; const int maxn = 10000+5; typedef long long ll; ll bin[35]; int n,m; ll a[maxn],x;template<typename T> inline void read(T &x){ x=0;T f=1;char ch;do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');do x=x*10+ch-'0',ch=getchar();while(ch<='9'&&ch>='0');x*=f; } template<typename A,typename B> inline void read(A&x,B&y){read(x);read(y);} template<typename A,typename B,typename C> inline void read(A&x,B&y,C&z){read(x);read(y);read(z);} template<typename A,typename B,typename C,typename D> inline void read(A&x,B&y,C&z,D&w){read(x);read(y);read(z);read(w);}struct trie{int cnt;int ch[maxn*35][2];ll val[maxn*35];int ts[maxn*35];inline void init(){cnt=1;memset(ch[0],0,sizeof ch[0]);ts[0]=0;//memset(ts,0,sizeof ts);}inline void insert(ll a){int u=0;for(int i=32;i>=0;i--){ll t=a&bin[i];t>>=i;if(!ch[u][t]){memset(ch[cnt],0,sizeof ch[cnt]);val[cnt]=0;ts[cnt]=0;ch[u][t]=cnt++;}u=ch[u][t];ts[u]++;}val[u]=a;}inline void del(ll a){int u=0;for(int i=32;i>=0;i--){ll t=a&bin[i];t>>=i;u=ch[u][t];ts[u]--;}}inline ll query(ll a){int u=0;for(int i=32;i>=0;i--){ll t=a&bin[i];t>>=i;if(ch[u][t^1]&&ts[ch[u][t^1]]) u=ch[u][t^1];else u=ch[u][t];}return val[u]^a;} }Trie;int main(){//freopen("in.txt","r",stdin);bin[0]=1;for(ll i=1;i<=35;i++) bin[i]=bin[i-1]*2ll;int T,cas=1;for(cin>>T,cas=1;cas<=T;cas++){scanf("%d",&n);Trie.init();for(int i=1;i<=n;i++){read(a[i]);Trie.insert(a[i]);}ll mx=0;for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++){Trie.del(a[i]);Trie.del(a[j]);mx=max(mx,Trie.query(a[i]+a[j]));Trie.insert(a[i]);Trie.insert(a[j]);}printf("%lld\n",mx);}return 0; }

Bzoj 4260

正做一遍dp，倒著做一遍dp。類似合唱隊型。

#include <bits/stdc++.h>using namespace std; const int maxn = 400000+5; typedef long long ll; int bin[31]; int n,m; int a[maxn],x; int dp[maxn],df[maxn];template<typename T> inline void read(T &x){ x=0;T f=1;char ch;do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');do x=x*10+ch-'0',ch=getchar();while(ch<='9'&&ch>='0');x*=f; }template<typename A,typename B> inline void read(A&x,B&y){read(x);read(y);} template<typename A,typename B,typename C> inline void read(A&x,B&y,C&z){read(x);read(y);read(z);} template<typename A,typename B,typename C,typename D> inline void read(A&x,B&y,C&z,D&w){read(x);read(y);read(z);read(w);}struct trie{int cnt;int ch[maxn*31][2];int val[maxn*31];void init(){cnt=1;memset(ch[0],0,sizeof ch[0]);}void insert(int a){int u=0;for(int i=32;i>=0;i--){int t=a&bin[i];t>>=i;if(!ch[u][t]){memset(ch[cnt],0,sizeof ch[cnt]);val[cnt]=0;ch[u][t]=cnt++;}u=ch[u][t];}val[u]=a;}int query(int a){int u=0;for(int i=32;i>=0;i--){int t=a&bin[i];t>>=i;if(ch[u][t^1]) u=ch[u][t^1];else u=ch[u][t];}return val[u]^a;} }Trie;int main(){//freopen("in.txt","r",stdin);bin[0]=1;for(int i=1;i<=35;i++) bin[i]=bin[i-1]*2;read(n);for(int i=1;i<=n;i++)read(a[i]);Trie.init();Trie.insert(0);x=0;for(int i=1;i<=n;i++){x=x^a[i];dp[i]=Trie.query(x);Trie.insert(x);}Trie.init();Trie.insert(0);x=0;for(int i=n;i>=1;i--){x^=a[i];df[i]=Trie.query(x);Trie.insert(x);}ll mx=0;ll res=0;for(int i=1;i<=n;i++){mx=max(mx,(ll)dp[i]);res=max(res,mx+df[i+1]);}cout<<res<<endl;return 0; }

codeforces 842 D

建好trie樹后，建好1-3e5的字典樹，插入修改標記。貪心查詢。

對于修改，只需要按位看需不需要倒置就行。

#include<bits/stdc++.h>#define lc (tire[id][0]) #define rc (tire[id][1])using namespace std;template<typename T> inline void read(T &x){ x=0;T f=1;char ch;do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');do x=x*10+ch-'0',ch=getchar();while(ch<='9'&&ch>='0');x*=f; }template<typename A,typename B> inline void read(A&x,B&y){read(x);read(y);} template<typename A,typename B,typename C> inline void read(A&x,B&y,C&z){read(x);read(y);read(z);}const int maxn = 6001000; const int maxdep = 19;bool rev[maxn]; int cnt[maxn]; int tire[maxn][2]; int rt,tot; int build(int dep){int now=tot++;if(dep>=0){tire[now][0]=build(dep-1);tire[now][1]=build(dep-1);}return now; } int push_UP(int id){cnt[id]=min(cnt[lc],cnt[rc]); } int update(int id,int dep,int x){if(dep==-1){cnt[id]++;return 0;}int t=(x>>dep&1);update(tire[id][t],dep-1,x);push_UP(id); } void solve(){int ans=0;int now=rt;for(int i=maxdep;i>=0;i--){if(rev[i]){if(cnt[tire[now][1]]==0){now=tire[now][1];} else {now=tire[now][0];ans+=(1<<i);}} else {if(cnt[tire[now][0]]==0){now=tire[now][0];} else {now=tire[now][1];ans+=(1<<i);}}}printf("%d\n",ans); } int n,m; int main(){int x; rt=build(maxdep);read(n,m); for(int i=1;i<=n;i++){read(x);update(rt,maxdep,x);}for(int ii=1;ii<=m;ii++){read(x);for(int i=maxdep;i>=0;i--){if(x>>i&1){rev[i]^=1;}}solve();}return 0; }

轉載于:https://www.cnblogs.com/foreignbill/p/7858039.html

總結

以上是生活随笔為你收集整理的01字典树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。