CF1285 D Dr. Evil Underscores

CF1285 D Dr. Evil Underscores

CF1285 D Dr. Evil Underscores

题意

给出$n$个数字,现在要求出一个$X$,使得$X$与$n$个数字单独异或之后的最大值最小

思路

数字的范围是$(0 \leq a_i \leq 2^{30})$

也就是用树的层级来模拟幂级,然后读入$a_i$一位位二进制插入

最后$dfs$找的时候看这一位的左右儿子

如果这一位$0$和$1$同时存在,也就是$X$这一位不管是什么,最后的答案的这一位也得是$1$

如果这一位只有一个,$X$这一位就取反,最后答案这一位就是$0$

题解代码

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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int inf = 0x3f3f3f3f;
const int N = 1e5 + 100;
int trie[N * 32][2], cnt = 0;
void insert(int x)
{
int pos = 0;
for (int i = 31; i >= 0; i--)
{
int to = (x >> i) & 1;
if (!trie[pos][to])
trie[pos][to] = ++cnt;
pos = trie[pos][to];
//cout << i << ":" << pos << " " << to << " " << pos << endl;
}
}

int dfs(int step, int pos)
{
if (step == -1)
return 0;
if (!trie[pos][0])
return dfs(step - 1, trie[pos][1]);
if (!trie[pos][1])
return dfs(step - 1, trie[pos][0]);
//cout << (1 << step) << endl;
return min(dfs(step - 1, trie[pos][0]), dfs(step - 1, trie[pos][1])) | (1 << step);
}

int main()
{
int n;
scanf("%d", &n);
while (n--)
{
int num;
scanf("%d", &num);
insert(num);
}
printf("%d\n", dfs(31, 0));
getchar();
getchar();
return 0;
}

重点解析

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
142
143
/*
字典树上述博客讲的很清楚了
这里我们看看怎么dfs的
*/
int dfs(int step, int pos)
{
if (step == -1)//到底了都没搜到0和1都有的就直接输出0
return 0;
if (!trie[pos][0])//没0走1
return dfs(step - 1, trie[pos][1]);
if (!trie[pos][1])//没1走0
return dfs(step - 1, trie[pos][0]);
return min(dfs(step - 1, trie[pos][0]), dfs(step - 1, trie[pos][1])) | (1 << step);
//如果这一位0和1都有,那么这一位直接输出1乘上目前的权值,然后继续往下搜索
//往下走有两条路,选择最后结果少的那个
}
/*
画图比较好理解
用样例:
3
1 2 3
*/
void insert(int x)
{
int pos = 0;
for (int i = 31; i >= 0; i--)
{
int to = (x >> i) & 1;
if (!trie[pos][to])
trie[pos][to] = ++cnt;
pos = trie[pos][to];
cout << i << ":" << pos << " " << to << " " << pos << endl;
}
}
/*
1,2,3在字典树中的存储就很简单了
31:1 0 1
30:2 0 2
29:3 0 3
28:4 0 4
27:5 0 5
26:6 0 6
25:7 0 7
24:8 0 8
23:9 0 9
22:10 0 10
21:11 0 11
20:12 0 12
19:13 0 13
18:14 0 14
17:15 0 15
16:16 0 16
15:17 0 17
14:18 0 18
13:19 0 19
12:20 0 20
11:21 0 21
10:22 0 22
9:23 0 23
8:24 0 24
7:25 0 25
6:26 0 26
5:27 0 27
4:28 0 28
3:29 0 29
2:30 0 30
1:31 0 31
0:32 1 32 //看到了1
31:1 0 1
30:2 0 2
29:3 0 3
28:4 0 4
27:5 0 5
26:6 0 6
25:7 0 7
24:8 0 8
23:9 0 9
22:10 0 10
21:11 0 11
20:12 0 12
19:13 0 13
18:14 0 14
17:15 0 15
16:16 0 16
15:17 0 17
14:18 0 18
13:19 0 19
12:20 0 20
11:21 0 21
10:22 0 22
9:23 0 23
8:24 0 24
7:25 0 25
6:26 0 26
5:27 0 27
4:28 0 28
3:29 0 29
2:30 0 30
1:33 1 33 //二进制下的2
0:34 0 34 //二进制下的2
31:1 0 1
30:2 0 2
29:3 0 3
28:4 0 4
27:5 0 5
26:6 0 6
25:7 0 7
24:8 0 8
23:9 0 9
22:10 0 10
21:11 0 11
20:12 0 12
19:13 0 13
18:14 0 14
17:15 0 15
16:16 0 16
15:17 0 17
14:18 0 18
13:19 0 19
12:20 0 20
11:21 0 21
10:22 0 22
9:23 0 23
8:24 0 24
7:25 0 25
6:26 0 26
5:27 0 27
4:28 0 28
3:29 0 29
2:30 0 30
1:33 1 33 //二进制下的3
0:35 1 35 //二进制下的3
然后缩减一下就是
0
0 1
* 1 0 1
//第一层的儿子有0和1,这一位直接return min(dfs) |(1<<step)
//这一位的层数是31也就是这一位有个1<<1也就是2
//左边的0下去就是1,再下去就是step==-1,输出0
//右边的1有两个孩子输出直接输出1
//所以上一层的min选左边的0
最后输出2+0=0
*/