http://codeforces.com/contest/1446
C. Xor Tree
题意：给定一个n个数都不相同的数列，每个数和另一个数相连无向边，满足它与另一个数的异或值小于它与其它数的异或值，两个数互相连边算作连一次。要求删去最少的数，使得得到一棵树。
字典树
试一下就能发现不会成环，所以要形成树只要满足只有一对点互相连边。
把所有数都插进Trie里，对于节点 u，它的左子树里的所有节点必定只会与左子树中点相连，所以如果左子树中选择了大于等于2个点，则这两个点必定会形成一条互相的连边。而如果左子树只选一个点，则这个点不会形成互相的连边。
Trie上dp
ans[u]=max(ans[lson(u)]+1,ans[rson(u)]+1)。
如果只有左子树或只有右子树，则 ans[u]=ans[lson(u)]。
如果是叶子，则返回1.
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
| #include <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
const int N = 2e7 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
int n, ans;
int a[N];
int ch[N][2], tot;
void ins(int x) {
int rt = 0;
for (int i = 30; i >= 0; i--) {
int bt = (x >> i & 1);
if (!ch[rt][bt])ch[rt][bt] = ++tot;
rt = ch[rt][bt];
}
}
int dfs(int u) {
if (ch[u][0] && ch[u][1]) {
return max(dfs(ch[u][0]) + 1, dfs(ch[u][1]) + 1);
}
else if (ch[u][0])return dfs(ch[u][0]);
else if (ch[u][1])return dfs(ch[u][1]);
else {
return 1;
}
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++)scanf("%d", &a[i]);
for (int i = 1; i <= n; i++)ins(a[i]);
printf("%d\n", n - dfs(0));
return 0;
}
|
