2019杭電夏休み多校第5回B:three arrays(01辞書樹)

1426 ワード

【問題解】
題意:2つの配列aとbが与えられ、配列を並べ替えて得られる配列c[i]=a[i]^b[i]の辞書順が最小になる.
問題解:2つの配列について、上位から下位に2つの01辞書ツリーを構築し、上位から下位に移動します.最も小さな異や値が要求されるため、次の2つが同じであれば同じです.最後に順番に出力すればいいです.
先行知識:ディクショナリツリーと01ディクショナリツリーの詳細
【コード】
#include 
using namespace std;
const int maxn=1e5+10;
struct node{
	int nex[2];
	int val;
}t[2][maxn*32];
int ans[maxn],pos[3];
void add(int x,int k) //  01   
{
	int p=0;
	for(int i=29;i>=0;i--){
		int op=(1&(x>>i)); //   i 
		if(!t[k][p].nex[op]){
			t[k][p].nex[op]=++pos[k];
			t[k][pos[k]].nex[0]=t[k][pos[k]].nex[1]=t[k][pos[k]].val=0;
		}
		p=t[k][p].nex[op];
		t[k][p].val++; //    +1
	}
}
int query()
{
	int p0=0,p1=0; //      
	int x=0;
	for(int i=29;i>=0;i--){ //30     
		if(t[0][t[0][p0].nex[0]].val&&t[1][t[1][p1].nex[0]].val){
			p0=t[0][p0].nex[0];
			t[0][p0].val--;
			p1=t[1][p1].nex[0];
			t[1][p1].val--;
		}
		else if(t[0][t[0][p0].nex[1]].val&&t[1][t[1][p1].nex[1]].val){
			p0=t[0][p0].nex[1];
			t[0][p0].val--;
			p1=t[1][p1].nex[1];
			t[1][p1].val--;
		} 
		else if(t[0][t[0][p0].nex[1]].val&&t[1][t[1][p1].nex[0]].val){
			p0=t[0][p0].nex[1];
			t[0][p0].val--;
			p1=t[1][p1].nex[0];
			t[1][p1].val--;
			x+=(1<