一道字典树异或的题，但是数据比较水，被大家用暴力给干掉了！
以前写过一个类似的题，叫做the longest xor in tree；
两个差不多吧！
好久没写字典树了，复习一下！
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 100010
using namespace std;
int n,v[maxn],node,next[maxn][],end[maxn]; void add(int cur,int k)
{
memset(next[node],,sizeof(next[node]));
end[node]=;
next[cur][k]=node++;
} int cal(int x)
{
int i,k,cur=;
for(i=;i>=;i--)
{
k=((<<i)&x)?:;
if(next[cur][k]) cur=next[cur][k];
else cur=next[cur][-k];
}
return (x^end[cur]);
} int main()
{
int k,x,cur,ans,cp;
while(!scanf("%d%d",&n,&cp)!=EOF)
{
node=,ans=;
memset(next[],,sizeof(next[]));
for(int i=;i<n;i++)
{
scanf("%d",&x);
v[i]=x;
cur=;
for(int j=;j>=;j--)
{
k=((<<j)&x)?:;
if(next[cur][k]==) add(cur,k);
cur=next[cur][k];
}
end[cur]=x;
}
for(int i=;i<n;i++)ans=max(ans,cal(v[i]));
if(ans>cp)puts("YES");
else puts("NO");
}
return ;
}
另一种写法：
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 100005
using namespace std; struct node
{
node *p[];
} no[maxn];
int w[],nocount; node *newnode()
{
node *v=no+nocount++;
for(int i=;i<;i++)v->p[i]=NULL;
return v;
} void insert()
{
node *nono=no;
for(int i=;i>=;i--)
{
if(nono->p[w[i]]==NULL)
nono->p[w[i]]=newnode();
nono=nono->p[w[i]];
}
} int cal()
{
int ans=;
node *nono=no;
for(int i=;i>=;i--)
{
if(nono->p[-w[i]]!=NULL){ans+=(<<i);nono=nono->p[-w[i]];}
else if(nono->p[w[i]]!=NULL){nono=nono->p[w[i]];}
}
return ans;
} int main()
{
int n,m,x;
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(no,,sizeof no);
nocount=;
int mm=;
for(int i=; i<n; i++)
{
scanf("%d",&x);
for(int i=;i<;i++){w[i]=x%,x>>=;}
if(i!=)mm=max(mm,cal());
insert();
}
if(mm>m)puts("YES");
else puts("NO");
}
return ;
}