A.HDU 4825

你需要寫(xiě)一種數(shù)據(jù)結(jié)構(gòu)：

• 往其中加入一個(gè)正整數(shù)；
• 找出一個(gè)正整數(shù)，使得該數(shù)與詢問(wèn)數(shù)的異或結(jié)果最大。

\(n\le 10^5\) 。

解

將數(shù)按二進(jìn)制從高位到低位插入字典樹(shù)。
查詢時(shí)從高位往低位貪心。

Code

#include<cstdio> using namespace std; const int maxn=100003,maxlog=33; int t[maxn*maxlog][2],cnt; void insert(long long x){int p=1;for(int i=32;i>=0;i--){int nxt=(x>>i)&1;if(!t[p][nxt])t[p][nxt]=++cnt;p=t[p][nxt];} } long long query(long long x){int p=1;long long ret=0;for(int i=32;i>=0;i--){int nxt=!((x>>i)&1);if(t[p][nxt])p=t[p][nxt],ret|=(long long)nxt<<i;else p=t[p][!nxt],ret|=(long long)(!nxt)<<i;}return ret; } int n,m; int main(){int T;scanf("%d",&T);for(int TT=1;TT<=T;TT++){scanf("%d%d",&n,&m);cnt=1;for(int i=0;i<=n*maxlog;i++)t[i][0]=t[i][1]=0;for(int i=1;i<=n;i++){long long x;scanf("%lld",&x);insert(x);}printf("Case #%d:\n",TT);while(m--){long long x;scanf("%lld",&x);printf("%lld\n",query(x));}}return 0; }

B. HDU 5536

有一個(gè)序列 \(s\) ，求 \(\max_{i,j,k,i≠j≠k} (s_i+s_j) \oplus s_k\) 。
\(1≤T≤1000\)
\(3≤n≤1000\)
\(0≤si≤10^9\)
There are at most \(10\) testcases with \(n>100\)
\(\text{Time Limit=9s}\)

解

直接 \(O(n^2\log n)\) 暴力插字典樹(shù)。

C. BZOJ 4260

有一個(gè)序列 \(A\) ，求 \(\max ((A[l_1] \oplus A[l_1+1] \oplus \dots \oplus A[r_1])+(A[l_2] \oplus A[l_2+1] \oplus \dots \oplus A[r_2]))(1\le l_1\le r_1<l_2\le r_2\le n)\)
\(n\le 4*10^5\) 。

解

處理出：
\(pre[i]=a[1] \oplus a[2] \oplus \dots \oplus a[i]\)
\(suf[i]=a[i] \oplus a[i+1] \oplus \dots \oplus a[n]\)
\(B[i]=\max(\max_{j\le i}pre[i] \oplus pre[j-1],B[i-1])\)
\(C[i]=\max(\max_{j≥i}suf[i] \oplus suf[j+1],C[i+1])\)
答案 \(=\max_{i\in [1,n-1]}(B[i]+C[i+1])\)

D. POJ 3764

有一棵樹(shù)，有邊權(quán)，求異或和最大的路徑的異或和。

解

設(shè) \(dp[i]\) 為從1到 \(i\) 的路徑的異或和，答案 \(=\max_{i,j}(dp[i] \oplus dp[j])\) 。
請(qǐng)自己證明。

E. HDU 4757

一棵樹(shù)， \(Q\) 次詢問(wèn)節(jié)點(diǎn) \(x\) 到節(jié)點(diǎn) \(y\) 的路徑上點(diǎn)權(quán)與 \(x\) 的異或的最大值。

解

可持久化trie

F. HDU 5661

求 \(\max_{a\le x\le b,c\le y\le d}(x \oplus y)(a,b,c,d\le 10^{18})\) 。

解

從高位往低位貪心。

Code

#include<cstdio> using namespace std; const int maxlog=60; bool valid(long long ans,int i,long long bit,long long l,long long r){bit=ans|(bit<<i);return (bit|((1ll<<i)-1))>=l&&bit<=r; } int main(){int T;scanf("%d",&T);for(int TT=1;TT<=T;TT++){long long a,b,c,d,ans1=0,ans2=0;scanf("%lld%lld%lld%lld",&a,&b,&c,&d);for(int i=59;i>=0;i--){bool v10=valid(ans1,i,0,a,b),v11=valid(ans1,i,1,a,b),v20=valid(ans2,i,0,c,d),v21=valid(ans2,i,1,c,d);if(v10&&v21)ans2|=1ll<<i;else if(v11&&v20)ans1|=1ll<<i;else if(v11&&v21)ans1|=1ll<<i,ans2|=1ll<<i;}printf("%lld\n",ans1^ans2);}return 0; }

G. BZOJ 4245

給定一個(gè)長(zhǎng)度為 \(n\) 的序列 \(a[1],a[2],\dots ,a[n]\)，請(qǐng)將它劃分為 \(m\) 段連續(xù)的區(qū)間，設(shè)第 \(i\) 段的費(fèi)用 \(c[i]\) 為該段內(nèi)所有數(shù)字的異或和，則總費(fèi)用為 \(c[1] | c[2] | \dots | c[m]\) 。請(qǐng)求出總費(fèi)用的最小值。

解

記錄一下前綴異或和，然后枚舉一個(gè)高位，如果存在一個(gè)高位使得至少 \(m\) 個(gè)異或和為 \(0\) 且總異或和 \((prev[n])\) 為 \(0\) ，那么即可劃分，此時(shí)這一位對(duì)答案的貢獻(xiàn)為 \(0\) ，否則該位對(duì)答案的貢獻(xiàn)為一個(gè) \(2\) 的冪。

I. J. 字典樹(shù)在字符串上的應(yīng)用，略

K. HDU 4099

\(T=50000\) 組詢問(wèn)，每次給出一個(gè)長(zhǎng)度不超過(guò)40的數(shù)，求最小的斐波那契數(shù)，使得給定的數(shù)是這個(gè)數(shù)的前綴。如果前100000個(gè)數(shù)中沒(méi)有符合條件的，輸出-1。

解

高精計(jì)算前100000個(gè)斐波那契數(shù)，只需存儲(chǔ)前50位（類似double），然后全部插到字典樹(shù)里。

轉(zhuǎn)載于:https://www.cnblogs.com/BlogOfchc1234567890/p/10885610.html

總結(jié)

以上是生活随笔為你收集整理的字典树andXOR*的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。