首先显然二分答案,问题转化为求 \(a_x \oplus a_y \ge m\) 的最大匹配。
考虑类似 CF1616H Keep XOR Low 地,设 \(f_u\) 为在 \(u\) 子树中选点满足条件的匹配最大值,\(g_{u, v}\) 为在 \(u\) 子树和 \(v\) 子树中选点满足条件的匹配最大值。转移就按位分类讨论贪心即可。
考虑递归实现。因为每个点只会被遍历到一次,所以总时间复杂度是 \(O(n \log^2 V)\) 的。
code
// Problem: G - Max of Medians
// Contest: AtCoder - Tokio Marine & Nichido Fire Insurance Programming Contest 2023(AtCoder Beginner Contest 304)
// URL: https://atcoder.jp/contests/abc304/tasks/abc304_g
// Memory Limit: 1024 MB
// Time Limit: 5000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 3100100;
int n, ch[maxn][2], ntot, sz[maxn], m;
inline void insert(int x) {
int p = 0;
for (int i = 29; ~i; --i) {
int t = ((x >> i) & 1);
if (!ch[p][t]) {
ch[p][t] = ++ntot;
}
p = ch[p][t];
++sz[p];
}
}
int dfs(int d, int u, int v) {
if (!u || !v) {
return 0;
}
if (d == -1) {
return min(sz[u], sz[v]);
}
if (m & (1 << d)) {
return dfs(d - 1, ch[u][0], ch[v][1]) + dfs(d - 1, ch[u][1], ch[v][0]);
} else {
int x = sz[ch[u][0]], y = sz[ch[u][1]], z = sz[ch[v][0]], w = sz[ch[v][1]];
if (x > w && z > y) {
return w + y + min({x - w, z - y, dfs(d - 1, ch[u][0], ch[v][0])});
} else if (w > x && y > z) {
return x + z + min({w - x, y - z, dfs(d - 1, ch[u][1], ch[v][1])});
} else {
return min(x, w) + min(y, z);
}
}
}
int dfs(int d, int u) {
if (d == -1 || (d < 29 && u == 0)) {
return 0;
}
if (m & (1 << d)) {
return dfs(d - 1, ch[u][0], ch[u][1]);
} else if (sz[ch[u][0]] < sz[ch[u][1]]) {
return min((sz[ch[u][1]] - sz[ch[u][0]]) / 2, dfs(d - 1, ch[u][1])) + sz[ch[u][0]];
} else {
return min((sz[ch[u][0]] - sz[ch[u][1]]) / 2, dfs(d - 1, ch[u][0])) + sz[ch[u][1]];
}
}
void solve() {
scanf("%d", &n);
for (int i = 0, x; i < n * 2; ++i) {
scanf("%d", &x);
insert(x);
}
int l = 1, r = (1 << 30) - 1, ans = 0;
while (l <= r) {
m = (l + r) >> 1;
if (dfs(29, 0) >= (n + 1) / 2) {
ans = m;
l = m + 1;
} else {
r = m - 1;
}
}
printf("%d\n", ans);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
- Beginner AtCoder Contest Medians 304beginner atcoder contest 304 beginner atcoder contest medians atcoder regular contest medians contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 332 beginner atcoder contest 328