Three arrays
赛场上想了半年都没有一点思路。。。看了题解发现原来是我学过的东东。。。(标题我瞎编的名字)
题意:给了一个大小为 1e5的 a数组和一个大小为 1e5的 b数组,请你对 a,b数组元素任意排序,使得到的 c数组( ci=ai Xor bi)字典序最小(其实不太准确)。
思路:
- 看到 1e5 × 1e5,明显是要寻找一个能快速匹配的算法,但赛场上并没有想到,即使它很经典!
- 整体思路:对 ai在 b数组中寻找最优的 bj(对 ai来说异或后最小);然后检查对于 bj来说, ai在 a数组中是否是最优的,若也是最优的,那很显然,两情相悦;经过 N次的两情相悦后,对他们得到的 c数组排个序,就是答案了
- 那么如何在另一个数组中寻找对当前数最优的数呢?并且要对所有数都适用。
- 我们可以利用 Trie树,先将所有的 ai,bi都插入 Trie树中(从二进制高位到低位),然后在寻找某一个数的最优匹配时,只需要尽可能沿着这个数在 Trie树上的路径移动,这样异或出来的答案就会尽可能小
- 但由于 ai对 bj来说可能还不是最优的,所以还需要询问一下 ai对 bj是否是最优的,这样 bj会找到一个 ak,只需要看看 ak是否就是 ai;若是,那么就称他们为两情相悦,并且把他们从 Trie树中删去(这样可以避免其他数对他们的痴心妄想);否则,用递归的思想再去判定 bj对刚刚找到的 ak是否是最优的,若是。。。否则。。。若。。。否。。。。。。
- 最后终于使 N对数都匹配上了,然后只需要对他们的异或排个序输出就完事啦!
Three arrays
Time Limit: 3000/2500 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 557 Accepted Submission(s): 145
Problem Description
There are three integer arrays a,b,c. The lengths of them are all N. You are given the full contents of a and b. And the elements in c is produced by following equation: c[i]=a[i] XOR b[i] where XOR is the bitwise exclusive or operation.
Now you can rearrange the order of elements in arrays a and b independently before generating the array c. We ask you to produce the lexicographically smallest possible array c after reordering a and b. Please output the resulting array c.
Input
The first line contains an integer T indicating there are T tests.
Each test consists of three lines. The first line contains one positive integer N denoting the length of arrays a,b,c. The second line describes the array a. The third line describes the array b.
-
T≤1000
-
1≤N≤105
-
integers in arrays a and b are in the range of [0,230).
-
at most 6 tests with N>100
Output
For each test, output a line containing N integers, representing the lexicographically smallest resulting array c.
Sample Input
1
3
3 2 1
4 5 6
Sample Output
4 4 7
#pragma comment(linker, "/STACK:102400000,102400000")
#include "bits/stdc++.h"
#define pb push_back
#define ls l,m,now<<1
#define rs m+1,r,now<<1|1
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {int x=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x;}
const int maxn = 5e6+10;
const int mod = 1e9+7;
const double eps = 1e-9;
int N;
int nxt[maxn][2], cnt[maxn][2], sz, pair_cnt;
int c[maxn];
void add(int x, int f) { //按二进制插入Trie树中
int now=0;
for(int i=29; i>=0; --i) {
int s=x>>i&1;
if(!nxt[now][s]) nxt[now][s]=++sz;
now=nxt[now][s];
cnt[now][f]++;
}
}
int choose(int f) { //随便写,能找到一个还没匹配的f(a或b)数组的数就行了
int res=0, now=0;
for(int i=29; i>=0; --i) {
if(nxt[now][0]&&cnt[nxt[now][0]][f]) now=nxt[now][0];
else res|=1<<i, now=nxt[now][1];
}
return res;
}
int choose_near(int x, int f) { //找另一个数组中最优的数
int res=0, now=0;
for(int i=29; i>=0; --i) {
int s=x>>i&1;
if(nxt[now][s]&&cnt[nxt[now][s]][!f]) {
if(s) res|=1<<i;
now=nxt[now][s];
}
else {
if(!s) res|=1<<i;
now=nxt[now][!s];
}
}
return res;
}
void cut(int x, int f) { //删数
int now=0;
for(int i=29; i>=0; --i) {
int s=x>>i&1;
cnt[now=nxt[now][s]][f]--;
}
}
bool choose_pair(int x, int f, int y) { //这里面的while(1)以及两个不同的return比较关键
while(1) {
int res=choose_near(x,f); //另一个数组中最自己最优的数
if(res==y) { //两情相悦
cut(x,f); //两个都删掉
cut(y,!f);
c[pair_cnt++]=x^y; //保存答案到c数组中
return 1;
}
if(choose_pair(res,!f,x)) return 0;
}
}
void init() {
for(int i=0; i<=sz; ++i) cnt[i][0]=cnt[i][1]=nxt[i][0]=nxt[i][1]=0; //初始化多了要T哟
sz=pair_cnt=0;
}
int main() {
//ios::sync_with_stdio(false);
int T=read();
while(T--) {
N=read();
for(int i=0; i<N; ++i) add(read(),0); //按二进制插入Trie树中
for(int i=0; i<N; ++i) add(read(),1);
while(pair_cnt<N) {
int x=choose(0); //这里随便找一个数就行了
choose_pair(x,0,-1);
}
sort(c,c+N); //排个序输出答案咯
for(int i=0; i<N; ++i) printf("%d%c", c[i], " \n"[i==N-1]);
init();
}
}