題目鏈接：點擊查看

題目大意：給出n個數(shù)組成的數(shù)組，再給出m個詢問，每次詢問給出一個x，要求從數(shù)組中選出一個k，使得k^x的值最大

題目分析：字典樹求異或值最大的模板題，對于n個數(shù)直接insert到字典樹中，然后對于每個查詢直接貪心從樹上找就是答案了，不太一樣的地方是這個題目要求輸出的不是答案而是原數(shù)，那么我們對于每個節(jié)點多維護(hù)一下其原來的數(shù)，也就是映射一下，最后查詢的時候直接返回這個映射就是答案了

或者還有一種辦法，因為異或運(yùn)算的特殊性，k^x=ans，同樣可以有ans^x=k，所以我們只需要對于求出來的答案再對x異或一下就是我們所要求得k了，兩者等價

代碼：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<set> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e5+100;int trie[N*35][2],cnt;LL val[N*35];int newnode() {cnt++;trie[cnt][0]=trie[cnt][1]=0;return cnt; }void insert(LL num) {int pos=0;for(int i=32;i>=0;i--){int to=(num>>i)&1;if(!trie[pos][to])trie[pos][to]=newnode();pos=trie[pos][to];}val[pos]=num; }LL search(LL num) {int pos=0;for(int i=32;i>=0;i--){int to=(num>>i)&1;if(trie[pos][!to])pos=trie[pos][!to];elsepos=trie[pos][to];}return val[pos]; }void init() {trie[0][0]=trie[0][1]=0;cnt=0; }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int w;cin>>w;int kase=0;while(w--){init();int n,m;scanf("%d%d",&n,&m);while(n--){LL num;scanf("%lld",&num);insert(num);}printf("Case #%d:\n",++kase);while(m--){LL x;scanf("%lld",&x);printf("%lld\n",search(x));}}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的HDU - 4825 Xor Sum(字典树)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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