HDU 6625 three arrays
题意： 给两个数组，求两个数组两两异或后最小字典序。
题解： 求字典序最小，也就是求值最小，如果是求一个数和另一个数组里面的一个值异或最小，很显然就是字典树，就是在字典树上优先取同位相同，没有再取同位相反。求两个数组异或之后字典序最小，其实也可以按照同样的方法求解。对两个数组分别做成一颗字典树，求两颗线段树异或之后字典序最小，就是两颗树异或值尽可能小。一开始我想到这个写法的时候，队友说如果0 0，和1 1 异或都等于0 先选哪一个，仔细思考一下，其实没有什么影响，统计一下两颗树当前节点下方，0 1 的个数，优先把 0 0 1 1 匹配掉，然后再把0 1 1 0两种匹配掉。有点像在字典树上贪心.
复杂度两颗树最多有n*31个节点，最差就是每个树都跑一次，所以复杂度是$O(nlog(n))$1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int, int> P;
const LL mod = (LL) 1e9 + 7;
const int maxn = (int) 1e6 + 5;
const int INF = 0x7fffffff;
const LL inf = 0x3f3f3f3f;
const double eps = 1e-8;
clock_t prostart = clock();
void f() {
freopen("../data.in", "r", stdin);
}
int n;
inline int getpos(int x, int pos) {
return ((x >> pos) & 1);
}
struct tree {
int a[maxn * 10][3];
int num[maxn * 10][3];
int root = 0;
int cnt = 1;
void init() {
cnt = 1;
}
void insert(int x) {
int p = root, dep = 30;
while (dep >= 0) {
int nx = getpos(x, dep);
if (num[p][nx] == 0) {
a[p][nx] = cnt++;
num[p][nx] = 1;
} else {
num[p][nx]++;
}
p = a[p][nx];
dep--;
}
}
} t1, t2;
vector<int> v;
template<class T>
inline T min(T t1, T t2, T t3) {
return min(t1, min(t2, t3));
}
void dfs(int now1, int now2, int num, int val, int dep) {
if (dep == -1) {
for (int i = 0; i < num; i++)
v.emplace_back(val);
return;
}
if (t1.num[now1][0] > 0 && t2.num[now2][0] > 0 && num > 0) {
int ct = min(t2.num[now2][0], t1.num[now1][0], num);
dfs(t1.a[now1][0], t2.a[now2][0], ct, val, dep - 1);
t1.num[now1][0] -= ct;
t2.num[now2][0] -= ct;
num -= ct;
}
if (t1.num[now1][1] > 0 && t2.num[now2][1] > 0 && num > 0) {
int ct = min(t1.num[now1][1], t2.num[now2][1], num);
dfs(t1.a[now1][1], t2.a[now2][1], ct, val, dep - 1);
t1.num[now1][1] -= ct;
t2.num[now2][1] -= ct;
num -= ct;
}
if (t1.num[now1][0] > 0 && t2.num[now2][1] > 0 && num > 0) {
int ct = min(t2.num[now2][1], t1.num[now1][0], num);
dfs(t1.a[now1][0], t2.a[now2][1], ct, val | (1 << dep), dep - 1);
t1.num[now1][0] -= ct;
t2.num[now2][1] -= ct;
num -= ct;
}
if (t1.num[now1][1] > 0 && t2.num[now2][0] > 0 && num > 0) {
int ct = min(t1.num[now1][1], t2.num[now2][0], num);
dfs(t1.a[now1][1], t2.a[now2][0], ct, val | (1 << dep), dep - 1);
t1.num[now1][1] -= ct;
t2.num[now2][0] -= ct;
num -= ct;
}
}
int main() {
f();
int T;
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
t1.init();
t2.init();
for (int i = 0; i < n; i++) {
int a;
scanf("%d", &a);
t1.insert(a);
}
for (int j = 0; j < n; j++) {
int a;
scanf("%d", &a);
t2.insert(a);
}
v.clear();
// debug(t2.num[29][1]);
dfs(0, 0, n, 0, 30);
sort(v.begin(), v.end());
for (int i = 0; i < n; i++) {
printf("%d%c", v[i], i == n - 1 ? '\n' : ' ');
}
}
cout << "运行时间:" << 1.0 * (clock() - prostart) / CLOCKS_PER_SEC << endl;
return 0;
}