这个题目和上一个基本是一样的,就是统计经过节点的次数,查询的时候没经过一次,就把计数-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; }