这个题目和上一个基本是一样的,就是统计经过节点的次数,查询的时候没经过一次,就把计数-1,直到减不了了或者不存在这条边可以走,我们就走另一条边就好了!
#include<iostream>
#include<cstdio>
using namespace std;
const int N=3e5+10;
int curcnt=1;
int endge[32*N][2];
int value[32*N][2];
int data[N];
void treeinsert(int num)
{
int cur=0;
for(int i=30;i>=0;i--)
{
//cout<<cur<<endl;
int digit=(num>>i)&1;
if(!endge[cur][digit])
{
endge[cur][digit]=curcnt++;
}
value[cur][digit]++;
cur=endge[cur][digit];
}
}
int findnum(int num)
{
int cur=0;
int ans=0;
for(int i=30;i>=0;i--)
{
int digit=(num>>i)&1;
if(endge[cur][digit]&&value[cur][digit])
{
value[cur][digit]--;
cur=endge[cur][digit];
}
else
{
value[cur][digit^1]--;
ans+=(1<<i);
cur=endge[cur][digit^1];
}
}
//cout<<endl;
return ans;
}
int main ()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin>>n;
int x;
for(int i=1;i<=n;i++)
{
cin>>data[i];
}
for(int i=1;i<=n;i++)
{
cin>>x;
treeinsert(x);
}
for(int i=1;i<=n;i++)
{
cout<<findnum(data[i])<<' ';
}
return 0;
}



京公网安备 11010502036488号