Codeforces Round #470 (rated, Div. 2, based on VK Cup 2018 Round 1) D. Perfect Security

题目链接


题意：给定两个数组a和b，对于a数组的每一个元素，他都可以找b中的一个元素进行异或，求异或后字典序最小的方案。
思路：对b数组建01字典树，然后对于每个a【i】，我们要想字典树最小的话肯定贪心的选和自己的那一位01相同的，实在没有了只能走另外一条了，当b数组的一个元素配对好后，记得要在字典树上把它删掉。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=3e5+1;
int n,tree[31*maxn][2],cnt=0;
ll sum[maxn<<6],a[maxn],b[maxn];
void insert(ll x)
{
	int u=0;
	for(int i=31;i>=0;--i)
	{
		int t=(((1LL<<i)&x)?1:0);
		if(!tree[u][t])	tree[u][t]=++cnt;
		sum[tree[u][t]]++;
		u=tree[u][t];
	}
}
ll query(ll x)
{
	ll ans=0;
	int u=0;
	for(int i=31;i>=0;--i)
	{
		int t=(((1LL<<i)&x)?1:0);
		if(!sum[tree[u][t]]) ans+=(1LL<<i),t^=1;//最优的方案就是走和自己相同的t，实在没有了只能走另一条路了 
		sum[tree[u][t]]--;
		u=tree[u][t];
	}
	return ans;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i) scanf("%lld",&a[i]);
	
	for(int i=1;i<=n;++i) scanf("%lld",&b[i]),insert(b[i]);
	for(int i=1;i<=n;++i) printf("%lld ",query(a[i]));
}