#C241021A. 异或

标签（Label）

Trie树
二进制

前言（Front talk）

$\qquad$又是因为想到了一个思路，然后以为不行，就直接放弃，最后没做出来。。。

网址（Website）

题目详情 - 异或 - Super

题解 - 异或 - Super

题解（Solution）

$\qquad$发现出现了异或操作，又发现和二进制有关，便联系到 $\mathrm{Trie}$ 树，然后我就一直想怎么在一棵树上操作，最后发现如果建两棵树的话就非常好处理。

$\qquad$考虑从两棵树根节点双管齐下往下 $\mathrm{dfs}$ ，先尽量走相同的儿子，直到不能走之后再走不同的儿子即可，很明显，深度越深，异或值越小。

$\qquad$最后在把得出来的数组排序，输出即可。

出题者题解

算法分析

算法 1

使用 $n!$ 暴力枚举 $a$。
$b$ 不变，计算出 $c$ 之后对 $c$ 排序。

复杂度：$O(n!\log(n!))$。期望得分 10。

算法 2

考虑预处理出 $a[i] \text{ xor } b[j]$，从小到大贪心选取，用过的不再选。
当有 $a[i] \text{ xor } b[j] = a[k] \text{ xor } b[t]$ 时，选取顺序无所谓；当有 $a[i] \text{ xor } b[j] = a[i] \text{ xor } b[t]$ 时，那么 $b[j] = b[t]$，选取顺序也无所谓。所以贪心的正确性可证。

复杂度：$O(n^2 \log(n^2))$，期望得分 30。

算法 3

由于 $a_i, b_i$ 范围很小，在算法 2 的基础上，考虑对于相同的 $(a_i, b_j)$ 一起计算处理。
结合算法 2，期望得分 50。

算法 4

对于 $a$ 和 $b$ 分别建一颗字典树，一起进行 $\text{dfs}$ 使得每个 $a_i$ 和一个 $b_j$ 相消。
考虑将 $a$ 字典树上的子树 $A$ 和 $b$ 字典树上的子树 $B$ 尽量合并相消，先合并 $(lson[A], lson[B])$、$(rson[A], rson[B])$，再合并 $(lson[A], rson[B])$、$(rson[A], lson[B])$。
为保证复杂度正确，当某棵子树已经消完时，直接返回即可。
最后需要对 $c$ 重新排序。

复杂度：$O(n\log(2^{30}))$，期望得分 100。

代码（Code）

#include<bits/stdc++.h>
#include<vector>
#include<queue>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int> 
#define x first
#define y second
inline int rd(){
	char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
	while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}const int inf = 0x3f3f3f3f;
const int N = 201234;
bool ST;

int n,a[N],b[N];

int sum[N*60],vst[N*60];
int t[N*60][2],idx=2;
void ins(int x, int p){
	vst[p]++;
	Rof(i,30,0){
		int c = ((x>>i)&1);
		if(!t[p][c]) t[p][c]=++idx;
		p = t[p][c], vst[p]++;
	}
	sum[p] = x;
}

#define l1 t[p1][0]
#define l2 t[p2][0]
#define r1 t[p1][1]
#define r2 t[p2][1]
int c[N],cnt;
void dfs(int p1,int p2,int dep){
	if(dep==-1){
		while(vst[p1]&&vst[p2]){
			c[++cnt] = sum[p1]^sum[p2];
			vst[p1]--, vst[p2]--;
		}return;
	}
	if(vst[l1] && vst[l2]) dfs(l1,l2,dep-1),vst[p1]=(vst[l1]+vst[r1]),vst[p2]=(vst[l2]+vst[r2]);
	if(vst[r1] && vst[r2]) dfs(r1,r2,dep-1),vst[p1]=(vst[l1]+vst[r1]),vst[p2]=(vst[l2]+vst[r2]);
	if(vst[l1] && vst[r2]) dfs(l1,r2,dep-1),vst[p1]=(vst[l1]+vst[r1]),vst[p2]=(vst[l2]+vst[r2]);
	if(vst[l2] && vst[r1]) dfs(r1,l2,dep-1),vst[p1]=(vst[l1]+vst[r1]),vst[p2]=(vst[l2]+vst[r2]);
}

void Solve(){
	n = rd();vst[0] = false;
	For(i,1,n) a[i] = rd(), ins(a[i],1);
	For(i,1,n) b[i] = rd(), ins(b[i],2);
	dfs(1,2,30);
	sort(c+1,c+cnt+1);
	For(i,1,cnt) printf("%d%c",c[i]," \n"[i==n]);
	cerr<<cnt<<endl;
}

bool ED;
signed main(){
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	freopen("xor.in","r",stdin);
	freopen("xor.out","w",stdout);
	int T = 1, Tim = clock();
	while(T--) Solve();
	return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
}