2019杭電夏休み多校第5回B:three arrays(01辞書樹)
1426 ワード
【問題解】
題意:2つの配列aとbが与えられ、配列を並べ替えて得られる配列c[i]=a[i]^b[i]の辞書順が最小になる.
問題解:2つの配列について、上位から下位に2つの01辞書ツリーを構築し、上位から下位に移動します.最も小さな異や値が要求されるため、次の2つが同じであれば同じです.最後に順番に出力すればいいです.
先行知識:ディクショナリツリーと01ディクショナリツリーの詳細
【コード】
題意: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<