Moe's CF Life

喵~ 主人，欢迎来到我的题解小屋！今天我们要一起解决的是一道关于位运算的题目哦，叫做 "Maximal AND"。别担心，只要跟着我的思路，再难的题目也会变得像撸猫一样简单又愉快，喵~

H. Maximal AND

题目大意

这道题是说呀，我们有一个由 n 个整数组成的数组 a，还有一个非负整数 k，代表我们最多可以进行 k 次操作，喵。

每次操作是什么呢？我们可以选择数组里的任意一个数 a[i]，再选择一个从 0 到 30 的整数 j，然后把 a[i] 的第 j 个二进制位设置成 1。这个操作等价于 a[i] = a[i] OR 2^j。

我们的最终目标是，在进行了最多 k 次操作之后，让整个数组所有元素的按位与（a[1] AND a[2] AND ... AND a[n]）的结果尽可能大。我们要输出的，就是这个可能的最大值，喵~

解题思路

一看到要让结果“最大”，本能的反应就是要优先考虑二进制的高位，对不对呀？就像小猫总是先扑向最大的那条鱼干一样！

一个数的大小，主要取决于它的高位。比如，1000 (二进制) 就比 0111 (二进制) 要大，哪怕后者有更多的 1。2^j 的值比从 2^0 到 2^(j-1) 所有值的总和还要大呢 (2^j > 2^j - 1)。所以，能让高位变成 1，就绝对不要错过！

这启发我们使用一种贪心的策略：

从高位到低位遍历：我们从最重要、价值最高的第 30 位开始，一直检查到第 0 位。
判断是否能点亮当前位：对于当前检查的第 j 位，我们问自己：“我们能不能让最终 AND 结果的第 j 位变成 1 呢？”
计算代价：要让最终 AND 结果的第 j 位是 1，一个都不能少，数组里每一个数字的第 j 位都必须是 1 才行。我们可以先统计一下，原始数组中有多少个数的第 j 位本来就是 0。要把这些 0 全都变成 1，需要的操作次数就是这些 0 的个数。
做出决策：
- 如果咱们手里剩下的操作次数 k 足够支付这个代价，那当然要支付啦！这是让结果变大的最好机会！我们用掉所需的操作次数（k 减去代价），然后把我们最终答案的第 j 位也点亮（设置为 1）。
- 如果 k 不够了，那只好忍痛放弃这一位了，喵呜... 毕竟巧妇难为无米之炊嘛。我们保留着 k，去看看下一位（更低一位）还有没有机会。

就这样，从第 30 位到第 0 位，一步步做出当前最优的选择，最后组合起来的，就是我们能得到的最大 AND 值啦！

题解代码

下面是解题的 C++ 代码，我已经加上了可爱的注释，方便主人理解哦~

cpp

#include <iostream>
#include <vector>
#include <numeric>

// 这个函数用来解决单个测试用例，喵~
void solve() {
    int n;
    long long k;
    std::cin >> n >> k;

    // 我们需要一个小本本（数组），来记录每个比特位（0到30）上，有多少个数字拥有这个位。
    // 大小是31，因为我们关心的是 0 到 30 位。
    std::vector<int> bit_counts(31, 0);

    // 我们不需要真的把数组 a 存下来，可以一边读一边处理，这样更省空间~
    // 当然，存下来也完全没问题。
    for (int i = 0; i < n; ++i) {
        int val;
        std::cin >> val;
        for (int j = 0; j < 31; ++j) {
            // 检查 val 的第 j 位是不是 1
            if ((val >> j) & 1) {
                // 如果是，就在我们的小本本上给第 j 位记上一笔
                bit_counts[j]++;
            }
        }
    }

    // 这个变量用来存放我们能构造出的最大 AND 结果
    int ans = 0;

    // 这就是我们的贪心策略啦！从最高位（30）开始，像小猫一样小心翼翼地往下试探~
    // 总是优先尝试点亮高位，因为 2^j 比所有更低的 2^i (i < j) 的总和还要大。
    for (int j = 30; j >= 0; --j) {
        // 要想让最终 AND 结果的第 j 位是 1，
        // 数组里每个数的第 j 位都必须是 1。
        // 所以，需要的操作次数就是那些第 j 位是 0 的数的数量。
        int needed_ops = n - bit_counts[j];

        // 看看我们的操作次数 k 够不够呀？
        if (k >= needed_ops) {
            // 够的话，就果断用掉！
            k -= needed_ops;
            // 然后把我们最终答案 ans 的这一位也点亮！喵~
            ans |= (1 << j);
        }
    }

    std::cout << ans << "\n";
}

int main() {
    // 这两行是为了让输入输出快一点，在比赛里很有用哦！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

知识点小课堂

这道题背后藏着一些有趣的计算机知识呢，我们一起来看看吧，喵~

位运算 (Bitwise Operations)
- 按位与 (AND, &): 只有当两个操作数的对应位都为 1 时，结果的对应位才为 1。就像两只小猫都想要小鱼干，才能一起分享一样！1 & 1 = 1, 1 & 0 = 0, 0 & 0 = 0。在这道题里，要让所有数字的 AND 结果在某一位上是 1，就意味着所有数字在这一位上都必须是 1。
- 按位或 (OR, |): 只要两个操作数的对应位中有一个为 1，结果的对应位就为 1。就像只要有一个人给小猫吃的，小猫就开心了~ 1 | 1 = 1, 1 | 0 = 1, 0 | 0 = 0。题目中的操作 a[i] OR 2^j 就是利用这个性质，强制把 a[i] 的第 j 位变成 1。
- 右移 (>>) 和左移 (<<):
  - val >> j 是将 val 的二进制表示向右移动 j 位。 (val >> j) & 1 是一个常用技巧，用来获取 val 的第 j 位是 0 还是 1。
  - 1 << j 是将 1 的二进制表示向左移动 j 位，这是一种快速计算 2 的 j 次方（2^j）的好方法，喵！
贪心算法 (Greedy Algorithm)
- 贪心算法是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法。
- 它不从整体最优上加以考虑，它所作出的仅是在某种意义上的局部最优解。但对于很多问题，贪心算法能产生全局最优解，比如这道题。
- 我们选择优先满足高位，就是因为高位的“价值”远大于所有低位的总和，所以满足高位是“当前看起来最好的选择”，并且这个选择不会影响我们对更低位的决策（除了消耗 k），所以它是正确的，喵~

好啦，这次的题解就到这里结束啦！希望主人能够喜欢，并且对位运算和贪心算法有了更深的理解。如果还有其他问题，随时可以再来找我哦，喵~ ❤

H. Maximal AND ​

题目大意 ​

解题思路 ​

题解代码 ​

知识点小课堂 ​

H. Maximal AND

题目大意

解题思路

题解代码

知识点小课堂