[CF1446C] Xor Tree

[题目链接]

https://codeforces.com/contest/1446/problem/C

[题解]

将 "删去最少" 转化为 "保留最多" 会易于处理一些。

题目中的限制相当于是这些数之间只有一组满足 (pos_{i} = j , pos_{j} = i)。

按二进制位建立字典树。 不妨设 (f_{i}) 表示以 (i) 为根的子树中保留最多的个数。

(i) 没有左右儿子 ， 或者是叶子的情况是很好处理的。

若 (i) 有左右儿子 ， 则 (f_{i} = max{f_{lc_{i}} , f_{rc_{i}}} + 1) (左边或右边取出一个最多的 ， 再在另一个儿子中再取一个)

时间复杂度 ： (O(N))

[代码]

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

#define rep(i , l , r) for (int i = (l); i < (r); ++i)

const int MN = 2e5 + 5;

int rt = 1 , tot = 1 , A[MN] , N , ch[MN * 31][2];

inline void insert(int val) {
	int cur = rt;
	for (int i = 30; i >= 0; --i) {
		bool c = val >> i & 1;
		if (!ch[cur][c]) ch[cur][c] = ++tot;
		cur = ch[cur][c]; 
	}
}
inline int solve(int now) {
	if (!ch[now][0] && !ch[now][1]) return 1;
	if (!ch[now][0]) return solve(ch[now][1]);
	if (!ch[now][1]) return solve(ch[now][0]);
	return max(solve(ch[now][0]) , solve(ch[now][1])) + 1;
}

int main() {
	 
 	 scanf("%d" , &N);
 	 for (int i = 1; i <= N; ++i) {
 	 	 scanf("%d" , &A[i]);
 	 	 insert(A[i]);
	 }
	 printf("%d
" , N - solve(rt));
     return 0;
}