2019 Multi-University Training Contest 5 1002 three arrays Trie树+思维题
Trie   发布于 2019-08-06   389人围观  0条评论
Trie   发表于 2019-08-06   389人围观  0条评论

## 代码

```#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
int get_num(){
int num = 0;
char c;
bool flag = false;
while((c = getchar()) == ' ' || c == '\r' || c == '\n');
if(c == '-')
flag = true;
else num = c - '0';
while(isdigit(c = getchar()))
num = (num<<3) + (num<<1) + c - '0';
return (flag ? -1 : 1) * num;
}
const int maxn = 1e5+10;
int ch[maxn*32][2],cnt[maxn*32][2];
int n,T;
int v,c[maxn];
int tot = 0;
int id;
int t;
int maxl = 29;
void build(int x,int ty){
int now = 0;
for(int i = maxl;i >= 0;--i){
t = (x>>i) & 1;
if(!ch[now][t]){
ch[now][t] = ++id;
cnt[ch[now][t]][ty] = 0;
}
now = ch[now][t];
cnt[now][ty]++;
}
return;
}
int ret = 0;
int find(int ty){
int now = 0;
ret = 0;
for(int i = maxl;i >= 0;--i){
if(ch[now][0] && cnt[ch[now][0]][ty]){
now = ch[now][0];
}
else{
now = ch[now][1];
ret |= (1 << i);
}
}
return ret;
}
void del(int x,int ty){
int now = 0;
for(int i = maxl;i >= 0;--i){
t = (x >> i) & 1;
now = ch[now][t];
cnt[now][ty] -= 1;
}
return;
}
int find_near(int x,int now,int ty){
ret = 0;
for(int i = maxl;i >= 0;--i){
int t = (x>>i) & 1;
if(ch[now][t] && cnt[ch[now][t]][ty^1]){
now = ch[now][t];
ret |= (t<<i);
}
else{
now = ch[now][t^1];
ret |= ((t^1)<<i);
}
}
return ret;
}
int y;
int st[maxn<<1];
int top = 0;
void find_pair(int now,int ty,int last){
top++;
st[top] = now;
while(top > 0){
y = find_near(now,0,ty);
if(y == last){
c[++tot] = y ^ now;
del(now,ty);
top--;
del(y,ty^1);
top--;
if(top == 0)break;
else if(top == 1){
last = -1;
now = st[top];
}
else{
last = st[top-1];
now = st[top];
}
}
else{
last = st[top];
st[++top] = y;
now = y;
ty ^= 1;
}
}
return;
}
int main(){
T = get_num();
while(T--){
tot = 0;
for(int i = 0;i <= id;++i){
ch[i][1] = ch[i][0] = 0;
cnt[i][0] = cnt[i][1] = 0;
}
id = 0;
n = get_num();
for(int i = 1;i <= n;++i)
st[i] = 0;
for(int i = 1;i <= n;++i){
v = get_num();
build(v,0);
}
for(int i = 1;i <= n;++i){
v = get_num();
build(v,1);
}
while(tot < n){
int x = find(0);
find_pair(x,0,-1);
top = 0;
}
sort(c+1,c+n+1);
printf("%d",c[1]);
int cnt = 1;
for(int i = 2;i <= n;++i){
printf(" %d",c[i]);
}
printf("\n");
}
return 0;
}```

0 条评论