生活随笔
收集整理的這篇文章主要介紹了
nyoj - 947（Max Xor）字典树
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
題目鏈接：http://acm.nyist.net/JudgeOnline/problem.php?pid=947
/**你可以把所有的數(shù)字變成等長的二進制，當成字符串然后建字典樹,再枚舉每個數(shù)把這個數(shù)的每一位取反去匹配匹配的時候能匹配就盡量匹配，不能就走不同的分支這樣求出來的就是這個數(shù)能搞出來的最大的
**/#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
typedef long long LL;
LL a[100005],c[55];
struct node
{int sum;node *next[2];
};
struct node *root;
struct node *build()
{struct node *p;p=(struct node *)malloc(sizeof(struct node));for(int i=0; i<2; i++){p->next[i]=NULL;}return p;
}
void solve(LL s)
{memset(c,0,sizeof(c));int num = 50;while(s){c[num--] = s%2;s/=2;}
}
void insert(LL s)
{solve(s);struct node *p;p=root;for(int i=0; i<=50; i++){if(p->next[c[i]]==NULL)p->next[c[i]]=build();p=p->next[c[i]];}
}
LL find(LL s)
{solve(s);struct node *p;p=root;LL sum = 0;for(int i=0; i<=50; i++){if(p->next[!c[i]]==NULL)//盡量使高位為1，所以取反 {sum = sum * 2;p=p->next[c[i]];}else{sum = sum * 2 + 1;p=p->next[!c[i]];}}return sum;
}
int main()
{int n,i;while(scanf("%d",&n)!=EOF){root=build();LL ans = 0;for(i=0; i<n; i++){scanf("%lld",&a[i]);insert(a[i]);}for(i = 0; i < n; i++)ans = max(find(a[i]),ans);printf("%lld\n",ans);}return 0;
}
總結
以上是生活随笔為你收集整理的nyoj - 947（Max Xor）字典树的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。
