P10218 [省选联考 2024] 魔法手杖 题解

· · 题解

退役三年选手回来做了下～

这题直观感觉很吓人，其实看到异或就可以往 Trie 树上思考了。

这题有两个未知量 S 和 x，其中 S\subseteq [n]，x\in[0,2^k)\cap\Z，状态过于复杂，肯定不能枚举，从答案的角度考虑。首先直观感受是有点像二分，其实我们可以从高位往低位确定答案 ans。

分析一下得出结论：ans 的二进制长度最长为 k+1 位（注意这里是个特殊情况），当且仅当 \sum b_i\le m，这个时候根据贪心，取 x=2^k-1 即可，此时 ans=\min\{b_i\}+x。

否则，ans 最长为 k 位，我们可以从高往低确定 ans。假设当前正在讨论第 d 位，根据贪心，我们需要判断第 d 位是否可以为 1。假如我们把所有的 a_i 插入一棵 Trie 树，对于 val(S,x)=\min(\min \limits_{i \in S}(a_i+x),\min \limits_{i \in U \backslash S}(a_i \oplus x))，我们称由 + 部分和 \oplus 部分组成。如果希望结果越大，也就是两个部分必须超过 ans 才可以。

这个时候，我们需要先确定 x 的第 d 位的取值，我们分 x=0 和 x=1 两种情况。在此基础上，S 的决策会影响 ans 的第 d 位。我们需要仔细分析一下，看一看能不能变成一个判定性问题。

假设此时在 Trie 树上的节点 u，如果左右孩子都存在，当 x 取 0 时，左子树的所有值在 \oplus 部分会贡献出 ans=0，右子树的所有值在 \oplus 部分会贡献出 ans=1，此时我们可以考虑将左子树移到 + 部分，尝试一下 ans 变成 1。考虑下影响：S 中的最小值更新了，这里用 y 表示，那么需要满足两个条件：1、左子树的 b 的和不超过剩余值（初始值位 m）；2、+ 部分必须超过当前的 ans（ans 未确定部分全部置成 0，x 未确定部分全部置成 1，极端情况的考虑）。只有这两个条件满足了，才能确定 ans 的第 d 位可以为 1，那么递归右子树，继续确定 d-1 位。x 取 1 时刚好对称。

所以得到了一个 贪心+dfs 的思路。先判断 ans 是否可以为 1，如果可以需要递归两种情况（合法时才递归），否则 ans 为 0，此时 x 取 0 时右子树可以忽略，递归左子树，反之亦然。也是两种情况。注意一下边界（d=-1 或者 u 是空节点）。

利用 Trie 维护 a 的 \min 和 b 的和，最终时间复杂度 {\rm O}(\sum nk)，空间复杂度 {\rm O}(nk)。代码想清楚的话很好写。

由于官方数据还没出来，大样例和民间数据都过了，先占个位置。代码有问题回头再修改。

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

void read(__int128 &x){
    // read a __int128 variable
    char c; bool f = 0;
    while (((c = getchar()) < '0' || c > '9') && c != '-');
    if (c == '-') { f = 1; c = getchar(); }
    x = c - '0';
    while ((c = getchar()) >= '0' && c <= '9') x = x * 10 + c - '0';
    if (f) x = -x;
}
void write(__int128 x){
    // print a __int128 variable
    if (x < 0) { putchar('-'); x = -x; }
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}

typedef long long ll;
const int N = 1e5 + 5, K = 120 + 5;
int T, c, n, m, k, ch[N * K][2], cnt;
int b[N]; ll sumb[N * K];
__int128 a[N], mina[N * K], ans;
int nnode() {
    cnt++;
    ch[cnt][0] = ch[cnt][1] = 0;
    mina[cnt] = (__int128)1 << k;
    sumb[cnt] = 0;
    return cnt;
}
void solve(int o, int d, int t, __int128 x, __int128 y, __int128 z) {
    if (d == -1) {
        ans = max(ans, z);
        return;
    }
    __int128 bit = (__int128)1 << d, mask = bit - 1;
    if (!o) {
        ans = max(ans, y + (x | mask | bit));
        return;
    }
    int lc = ch[o][0], rc = ch[o][1];
    bool flag = false;
    if (sumb[lc] <= t && (x | mask) + min(y, mina[lc]) >= (z | bit))
        solve(rc, d - 1, t - sumb[lc], x, min(y, mina[lc]), z | bit), flag = true;
    if (sumb[rc] <= t && (x | mask | bit) + min(y, mina[rc]) >= (z | bit))
        solve(lc, d - 1, t - sumb[rc], x | bit, min(y, mina[rc]), z | bit), flag = true;
    if (flag) return;
    solve(lc, d - 1, t, x, y, z);
    solve(rc, d - 1, t, x | bit, y, z);
}
int main() {
    freopen("xor.in", "r", stdin);
    freopen("xor.out", "w", stdout);
    scanf("%d%d", &c, &T);
    while (T--) {
        scanf("%d%d%d", &n, &m, &k);
        for (int i = 1; i <= n; i++) read(a[i]);
        for (int i = 1; i <= n; i++) scanf("%d", &b[i]);
        cnt = 0; nnode();
        __int128 MAX = (__int128)1 << k;
        mina[0] = MAX;
        for (int i = 1; i <= n; i++) {
            int u = 1;
            sumb[u] += b[i];
            mina[u] = min(mina[u], a[i]);
            for (int j = k - 1; ~j; j--) {
                int x = a[i] >> j & 1;
                if (!ch[u][x]) ch[u][x] = nnode();
                u = ch[u][x];
                mina[u] = min(mina[u], a[i]);
                sumb[u] += b[i];
            }
        }
        ans = 0;
        if (sumb[1] <= m)
            ans = mina[1] + MAX - 1;
        else
            solve(1, k - 1, m, 0, MAX, 0);
        write(ans); putchar('\n');
    }
    return 0;
}