题解：P17416 「IXOI R3」我才不玩原神呢

TQjc · 2026-09-06 17:41:09 · 题解

题目大意

定义一个序列 b 的权值为 \sum (b_i \oplus \max(b))，给定序列 a，求所有长度为 k 的子序列中权值的最大值。

思路

设子序列的最大值为 m。由于最大值一定是子序列中的某个元素，我们可以枚举这个元素作为最大值。将 a 排序后，若 a_i 作为最大值，则其余 k-1 个数必须从 a_1 \sim a_{i-1} 中选取。

问题转化为：从 a_1 \sim a_{i-1} 中选 k-1 个数，使得它们与 a_i 的异或和最大。这可以用可持久化 Trie 解决。

可持久化 Trie 维护每个前缀的二进制 Trie，支持查询某个前缀中与给定数异或和最大的若干个数之和。按位贪心选择：若当前位异或为 1 的数量足够，则优先选这些数；否则只能选异或为 0 的。

时间复杂度 O(n \log V)，空间复杂度 O(n \log V)。

代码

#include <bits/stdc++.h>
using namespace std;

const int lim = 100005;
const int limm = lim * 31 + 5;
const int limb = 30;

int n, k, a[lim], rt[lim];
int ch[limm][2], sz[limm], tot;
int cnt[limm * limb];

inline void ins(int &u, int v, int x) {
    u = ++tot;
    int p = u;
    sz[p] = sz[v] + 1;
    for (int j = 0; j < limb; ++j)
        cnt[p * limb + j] = cnt[v * limb + j] + ((x >> j) & 1);
    for (int i = limb - 1; i >= 0; --i) {
        int bit = (x >> i) & 1;
        ch[p][bit] = ++tot;
        ch[p][bit ^ 1] = ch[v][bit ^ 1];
        p = ch[p][bit];
        v = ch[v][bit];
        sz[p] = sz[v] + 1;
        for (int j = 0; j < limb; ++j)
            cnt[p * limb + j] = cnt[v * limb + j] + ((x >> j) & 1);
    }
}

inline long long calc_low(int u, int x, int max_bit) {
    long long res = 0;
    for (int bit = 0; bit <= max_bit; ++bit) {
        int ones = cnt[u * limb + bit];
        int total = sz[u];
        if ((x >> bit) & 1)
            res += 1LL * (total - ones) << bit;
        else
            res += 1LL * ones << bit;
    }
    return res;
}

inline long long qry(int root, int x, int need) {
    long long ans = 0;
    int p = root;
    for (int bit = limb - 1; bit >= 0; --bit) {
        if (need == 0) break;
        int xb = (x >> bit) & 1;
        int good = ch[p][xb ^ 1];
        int bad = ch[p][xb];
        int sg = sz[good];
        if (sg >= need) {
            ans += 1LL * need << bit;
            p = good;
        } else {
            if (sg) {
                ans += 1LL * sg << bit;
                ans += calc_low(good, x, bit - 1);
            }
            need -= sg;
            p = bad;
        }
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; ++i) ins(rt[i], rt[i - 1], a[i]);
    long long ans = 0;
    for (int i = n; i >= k; --i) {
        long long cur = qry(rt[i - 1], a[i], k - 1);
        if (cur > ans) ans = cur;
    }
    cout << ans;
    return 0;
}