• 周四. 5月 30th, 2024

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

CF 1447E Xor Tree

admin

11月 28, 2021

题目描述

若有 $k$ 个点,第 $i$ 个点的权值为 $b_i$ ,点权互不相同,那么 $i$ 会和 $j$ 连边当与 $b_i$ 异或值最小的值为 $b_j$ 。
现在有 $n$ 个点,求删掉最少的点使得最终的图,去掉重边后是棵树。

数据范围

$n le 2 imes 10^5,a_i le 10^9$

题解

一张图有 $n$ 条边,其中肯定会有最小值的数对,也就是最多有 $n-1$ 条边,若要删点说明这张图没有联通。

这张图什么时候没有联通?我们考虑最高有效位,若 $0$ 的个数和 $1$ 的个数都 $ge 2$ ,则这张图不会联通,因为 $0$ 的内部会自己连, $1$ 的内部会自己连,因此要让一边的个数降至最多一个,另一边接着往下删点,这可以递归实现。

效率 $O(nlogMax(a_i))$

代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,a[N];
int solve(int k,int l,int r){
    if (k==1) return 0;
    int mid=l;
    for (;mid<=r;mid++)
        if (k&a[mid]) break;
    if (mid==l || mid>r) return solve(k>>1,l,r);
    if (mid==l+1) return solve(k>>1,l+1,r);
    if (mid==r) return solve(k>>1,l,r-1);
    return min(solve(k>>1,l,mid-1)+r-mid,solve(k>>1,mid,r)+mid-1-l);
}
int main(){
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    printf("%d
",solve(1<<30,1,n));
    return 0;
}

《CF 1447E Xor Tree》有一个想法
  1. O e – Mail não é seguro e pode haver links fracos no processo de envio, transmissão e recebimento de e – Mails.Se as brechas forem exploradas, a conta pode ser facilmente quebrada.

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注