题解：P12420 【MX-X12-T3】「ALFR Round 5」变换

_hud · 2025-05-05 18:51:24 · 题解

题解：P12420 【MX-X12-T3】「ALFR Round 5」变换

题目大意

给定非负整数序列 a 以及参数 m 和 k。每次操作选择一个非负整数 x 满足 x \ \& \ m = x 和一个下标 i，将 a_i \gets a_i \ | \ x。之后可以选择将 m 减去 x 或花费 k 代价使得 m 不变。求操作后数组的异或和减去总代价的最大值。

思路分析

由题意，本题的核心目标： 通过操作改变 a 的异或和，最大化 (\oplus_{i=1}^{n} a_i) - s。

显然地，我们可以对这两部分分别进行分析。

异或和

根据异或的定义，不难得出以下性质： 某二进制位异或和的结果由对应 a 中该位 1 个数的奇偶性决定。若该位 1 个数是奇数，该位异或和的结果为 1；反之为 0。

再次审题，注意到条件 x \ \& \ m = x。假设每次操作后都会选择 m \gets m - x，将上述公式转化为通俗一点的语言，即：

在 m 中取出任意为 1 的数位，并添加到 a_i 的对应数位上。

进一步的，由上述性质可知，若 a_i 的数位改变，相当于改变了 a 中该位 1 个数的奇偶性。如果改变后为奇数，且原来为偶数，那么这一位就成功对答案造成了贡献。分析到这里，不难想到这是贪心。具体来说：

从高位到低位遍历：

• 若 m 的当前位 b 为 1（允许操作该位）：
  • 检查初始异或结果第 b 位是否为 0。
  • 检查是否存在 a_i 第 b 位为 0（即是否存在 0 可以更改，如果全是 1 ，操作后 a_i 的数位并不会发生改变）。
• 若以上两个条件均满足，则操作该位一次，即将异或结果的 b 位翻转，答案增加 2^b。

总代价

直接给出结论：最优选择下，总代价恒等于 0。

这个结论是显然的。根据上述性质，最后要进行异或运算时，只关注每个 a 在每一位上 1 出现次数的奇偶性，而不是次数（即不是次数越多越好）。所以每次操作总会选择 m \gets m - x。那么总代价自然也恒等于 0。

那么，这道题就迎刃而解了。实现可以看代码。

代码

#include <bits/stdc++.h>
using namespace std;
// #define DEBUG 1
struct IO { // 快读快写模板
#define MAXSIZE (1 << 20)
#define isdigit(x) (x >= '0' && x <= '9')
    char buf[MAXSIZE], *p1, *p2;
    char pbuf[MAXSIZE], *pp;
#if DEBUG
#else
    IO() : p1(buf), p2(buf), pp(pbuf) {}
    ~IO() { fwrite(pbuf, 1, pp - pbuf, stdout); }
#endif
    inline char gc() {
#if DEBUG
      return getchar();
#endif
      if (p1 == p2) p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin);
      return p1 == p2 ? ' ' : *p1++;
    }
    inline bool blank(char ch) {
        return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t';
    }
    template <class T>
    inline T read(T &x) {
        double tmp = 1; bool sign = 0;
        x = 0;
        char ch = gc();
        for(; !isdigit(ch); ch = gc())
            if (ch == '-') sign = 1;
        for(; isdigit(ch); ch = gc()) x = x * 10 + (ch & 15);
        if(ch == '.')
            for(ch = gc(); isdigit(ch); ch = gc())
                tmp /= 10.0, x += tmp * (ch - '0');
        if(sign) x = -x;
        return x;
    }
    inline void read(char *s) {
        char ch = gc();
        for(; blank(ch); ch = gc());
        for(; !blank(ch); ch = gc()) *s++ = ch;
        *s = 0;
    }
    inline void read(char &c) { for(c = gc(); blank(c); c = gc()); }
    inline void push(const char &c) {
#if DEBUG
        putchar(c);
#else
        if(pp - pbuf == MAXSIZE) fwrite(pbuf, 1, MAXSIZE, stdout), pp = pbuf;
        *pp++ = c;
#endif
    }
    template <class T>
    inline void write(T x) {
        if (x < 0) x = -x, push('-');
        static T sta[35];
        T top = 0;
        do {
            sta[top++] = x % 10, x /= 10;
        } while(x);
        while(top) push(sta[--top] + '0');
    }
    template <class T>
    inline void write(T x, char lastChar) {
        write(x), push(lastChar);
    }
} io;
int a[1000010], z[32];
inline void solve() {
    memset(z, 0, sizeof z); // 多测要清空
    int n, m, k, tmp = 0, res;
    io.read(n), io.read(m), io.read(k);
    for(int i = 1; i <= n; i++) 
        io.read(a[i]), tmp ^= a[i];
    // 统计每个位 '0' 的个数
    for(int b = 0; b <= 31; b++)
        for(int i = 1; i <= n; i++)
            z[b] += (!(a[i] & (1 << b)));
    res = tmp; // tmp 为原数组初始异或和
    for(int b = 0; b <= 31; b++) {
        if(!(m & (1 << b))) continue;
        if(!(tmp & (1 << b)) && z[b] >= 1) // 当前位可以对答案造成贡献且存在可操作数
            res += (1 << b);
    }
    io.write(res, '\n');
}
signed main() {
    int T; io.read(T);
    while(T--) solve();
    return 0;
}

进一步优化

注：本部分思路由同机房巨佬 @blm_xxc 提出。

根据原代码，不难观察到最耗时的部分是分别统计 a 每位上的 0 个数。故我们可以反方向思考：有没有更快捷的方法判断出是否存在某些位，而所有 a_i 在这些位上均为 1 呢？我们可以定义一个常量 p，将其每一二进制位上均设置为 1，每次输入进行 a_i \ \operatorname{and} \ p，即可判断在哪些位上所有 a_i 均为 1。

综上，可得公式：