CF1446C Xor Tree

对于每个点\(i\)，找到\(j\neq i\)且\(a_j \ xor \ a_i\)最小，连边\((i,j)\)。

如果连边之后形成一棵树，那么称\(\{a_i\}\)为合法的。

给出\(\{a_i\}\)，求至少删掉多少个点才合法。

\(n\le 2*10^5\)

\(a_i\)互不相同

这题搞得可真是惊心动魄……搞了三个做法，最后一个终于对了……

干了1.5h。

假设连有向边\(i\to j\)，那么建出的图是个基环树森林。并且每棵基环树的环长为\(2\)。

如果合法，那么必须满足：只存在一对\((i,j)\)，满足对于各自而言，\(a_i\ xor \ a_j\)都是最小的。

自然这也会是全局最小异或值。之前有个结论，对于一堆朴素的\(\{a_i\}\)，其中最小的\(a_i \ xor \ a_j\)一定是排序之后相邻的。

于是最终如何保留树才合法呢？建出Trie，发现长这样：

这样dfs找一下就好了。

using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 200005
#define INF (1<<30)
int n;
int a[N];
struct Node{
	Node *c[2];
	int siz;
} d[N*40],*rt;
int cnt;
void insert(int x,int c=1){
	Node *t=rt;
	for (int i=29;i>=0;--i){
		t->siz+=c;
		if (!t->c[x>>i&1]){
			t->c[x>>i&1]=&d[++cnt];
			d[cnt]={NULL,NULL};
		}
		t=t->c[x>>i&1];
	}
	t->siz+=c;
}
int ans;
void dfs(Node *t,int s){
	if (t->c[0] && t->c[0]->siz==1 && t->c[1] && t->c[1]->siz==1)
		ans=max(ans,2+s);
	if (t->c[0]) dfs(t->c[0],s+(t->c[1]?1:0));
	if (t->c[1]) dfs(t->c[1],s+(t->c[0]?1:0));
}
int main(){
//	freopen("in.txt","r",stdin);
	rt=&d[cnt=1];
	scanf("%d",&n);
	for (int i=1;i<=n;++i){
		scanf("%d",&a[i]);
		insert(a[i]);
	}
	ans=2;
	dfs(rt,0);
	printf("%d\n",n-ans);
	return 0;
}

CF1446C Xor Tree

原文：https://www.cnblogs.com/jz-597/p/13986661.html