嘘~ 正在从服务器偷取页面 . . .

CF1446C Xor Tree 题解

发布日期: 2024-01-11

更新日期: 2024-01-11

文章字数: 517

CF1446C Xor Tree 题解

题意：

给定长为 $n(n \le 2\times 10^5)$ 的非负整数序列 $a$，保证其中每个数两两不同且 $a_i \le 10^9$ 。

对于每个 $a _ i$，它会向 $j \ne i$ 且 $a_i\oplus a_j$（$\oplus$ 代表异或）最小的 $a _ j$ 连双向边。

如果 $a _ j$ 也向 $a _ i$ 连了边，只算一条边。

现在要让你删去序列中的一些数，使得最后形成的图是一颗树，输出最少需要删除几个数。

输入格式：

第一行 $n$ ，第二行 $a_i$ 。

输出格式：

只有一行，即答案。

首先把问题中的最小删除多少个看作最多可以保留多少个。

考虑建 01 trie，然后递归地考虑每个子树能保留多少个点，记为 $f_u$ 。

对于点 $u$ ，如果它只有一棵子树，则 $f_u$ 为那棵子树的大小，否则为左右子树中最大的那一棵 $+1$ 。

前者很好理解，后者解释一下：例如右子树较大，我们就保留左子树的一个点，可以发现这样完美解决了问题

时间复杂度 $\mathcal{O}(n\log V)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(2e5 + 15))
#define ls(x) ch[x][0]
#define rs(x) ch[x][1]

int n,cnt = 1,a[N],ch[N << 4][2];
void insert(int v)
{
    int u = 1;
    for(int i = 30; ~i; i--)
    {
        int c = (v >> i) & 1;
        if(!ch[u][c]) ch[u][c] = ++cnt;
        u = ch[u][c];
    }
}
int dfs(int at)
{
    if(!ls(at) && !rs(at)) return 1;
    if(!ls(at)) return dfs(rs(at));
    if(!rs(at)) return dfs(ls(at));
    return max(dfs(ls(at)), dfs(rs(at))) + 1;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i = 1; i <= n; i++) { cin >> a[i], insert(a[i]); }
    cout << (n - dfs(1)) << '\n';
    return 0;
}