Description

题目链接

题目大意：给定 $\{a_n\}$ 和 $k$，要求选择一个 $x$，求 $\max \sum \limits_{i = 1}^n [a_i \oplus x \le k]$。

Solution

想了半天字典树上做 DP，结果能暴力过...

由于 $a_i \le 10^6$，那么 $x$ 最大不超过 $2 \times 10^6$。

将所有 $a_i$ 插入到字典树中，然后从 $0$ 到 $2 \times 10^6$ 枚举 $x$，然后在字典树上查询就可以了。

时间复杂度 $O(n \log n)$（一个数的位数是 $\log$ 级别的）。

Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

template <class T>
inline void read(T &x) {
    x = 0;
    int f = 0;
    char ch = getchar();
    while (!isdigit(ch))    { f |= ch == '-'; ch = getchar(); }
    while (isdigit(ch))     { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
    x = f ? -x : x;
    return ;
}

typedef unsigned long long uLL;
typedef long long LL;

int tr[20000010][2];
int a[1000010], siz[20000010];
int n, k, ans, tot;

void insert(int s) {
    int x = 0;
    for (int i = 21; i >= 0; --i) {
        if (!tr[x][(s >> i) & 1])    tr[x][(s >> i) & 1] = ++tot;
        x = tr[x][(s >> i) & 1];
        ++siz[x];
    }
    return ;
}

int query(int s) {
    int x = 0, cnt = 0;
    for (int i = 21; i >= 0; --i) {
        int u = (s >> i) & 1, v = (k >> i) & 1;
        if (v)    cnt += siz[tr[x][1 - (u ^ v)]];
        if (!tr[x][u ^ v])    break;
        x = tr[x][u ^ v];
    }
    return cnt;
}

int main() {
    read(n), read(k);
    for (int i = 1; i <= n; ++i)    read(a[i]), insert(a[i]);
    for (int i = 0; i <= 2000000; ++i)    ans = std::max(ans, query(i));
    printf("%d\n", ans);
    return 0;
}