有趣異或

發(fā)布時間: 2017年7月4日 23:59?? 最后更新: 2017年7月5日 14:56?? 時間限制: 1500ms?? 內(nèi)存限制: 512M

描述

給定n個非負整數(shù)，保證這些數(shù)兩兩不相同。現(xiàn)給定x，請從中選2個不同的數(shù)a,b，使得a^b^x最大。

輸入

包含多組測試數(shù)據(jù)。
每組測試數(shù)據(jù)第一行有1個正整數(shù)和1個非負整數(shù)，分別為n和x。
接下來一行有n個正整數(shù)。
所有數(shù)據(jù)滿足n≤106，所有非負整數(shù)以及x小于等于109。
總數(shù)據(jù)量∑n≤106。

輸出

對每組數(shù)據(jù)輸出一行1個整數(shù)，表示a^b^x的最大值是多少。

樣例輸入1?復制 3 0 1 2 3 樣例輸出1 3

首先，我們把所有的整數(shù)對應的二進制前面補0，補成30位的二進制數(shù)，然后把這串二進制數(shù)當成字符串，存入Trie樹中。

其次，我們遍歷所有的數(shù)a，然后我們尋找b，使得a^b^x最大

我們這樣分析，當a和x確定時候a^x也就確定了設a^x = t

那么欲使t^b最大，那么t與b的相同的位上，值應該盡可能的不同，所以，我們依據(jù)t的位，在Trie中尋找b。。。

這里有一個坑點，那就只注意a和b不能相同，如果數(shù)據(jù)是x = (1111111....)b的話，那么樸素的求會找到與a相等的b，這顯然是錯誤的

因此，可以用一個標記，代表當前搜索到的Trie樹位置是否可能得到與a相等的b，搜索時候注意就好了。

代碼：

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAX = 1e6+7; int n,x; int a[MAX]; struct trie {int count;trie* child[2]; }; trie* root; void build(int num){trie* p = root;for(int i = 29;i >= 0;i--){int key = (num>>i) & 1;if(!p -> child[key]){trie* nt = new trie;nt -> count = 1;nt -> child[0] = nt -> child[1] = 0;p -> child[key] = nt;p = nt;}else{p = p -> child[key];p -> count ++;}} } int find(int a){int res = 0;trie* p = root;int able = 1;for(int i = 29;i >= 0;i--){int f = (x>>i) & 1;if(f){int key = (a>>i) & 1;if(!p->child[key]) {//沒有相同位 able = 0;key ^= 1; }else{//有相同位 if(!able){//已經(jīng)不可能.直接選 res |= (1<<i); }else{//還可能 if(p->child[key]->count-1 == 0){//不能選able = 0;key ^= 1; }else{//可以選// todo res |= (1<<i); }}}p = p -> child[key];}else{//最好不同 int key = (a>>i) & 1 ^ 1;//key 為理想 if(p->child[key]){//有不同位 able = 0;res |= (1<<i);}else{//只有相同位 key ^= 1;}p = p -> child[key];}}return res; } int main(){while(~scanf("%d%d",&n,&x)){int ma = 0;root = new trie;root -> count = 0; root -> child[0] = root -> child[1] = 0;for(int i = 0;i < n;i++){scanf("%d",&a[i]);build(a[i]);}for(int i = 0;i < n;i++){ma = max(ma,find(a[i]));}printf("%d\n",ma);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的2017西安交大ACM小学期 有趣异或[Trie树]的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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