喵~ 主人，你好呀！今天我们来解决一道关于位运算的有趣问题，就像在数字的海洋里寻找闪闪发光的宝石一样，嘿嘿。这道题是 Codeforces 上的 2118C - Make It Beautiful，就让本喵来带你一步步解开它的谜底吧！

题目大意

这道题给了我们一个由 n 个整数组成的数组 a，还有一个整数 k，代表我们最多可以执行的操作次数，喵。

首先，题目定义了一个概念叫做“美丽度” (beauty)。

• 一个数字的美丽度，就是它二进制表示中 1 的个数。比如，数字 7 的二进制是 111，所以它的美丽度是 3。数字 4 的二进制是 100，美丽度就是 1。
• 一个数组的美丽度，就是数组里所有数字的美丽度之和。

我们有一种操作：可以选择数组中的任意一个元素 a[i]，然后把它加一（a[i] = a[i] + 1）。这个操作最多可以执行 k 次。

我们的目标是：在最多 k 次操作之内，让整个数组的美丽度总和达到最大。你能帮帮我吗，喵？

解题思路

一看到要“最大化”某个值，我们的小脑袋瓜里就应该闪过“贪心”或者“动态规划”这些词，对吧？这道题呀，用贪心的思路来解决是再合适不过了，喵~

核心思想：找到最便宜的“美丽度+1”操作

我们的目标是最大化美丽度总和。每一次操作，我们都希望它能尽可能地增加美丽度。最理想的情况是，每次操作都能让总美丽度 +1。

那么，怎样才能让一个数 x 的美丽度 +1 呢？最直接的方法就是把它二进制表示中的一个 0 变成 1，而且不影响其他位。

举个例子，比如数字 x = 6，它的二进制是 0110。

• 如果我们想把它最低位的 0（第 0 位）变成 1，我们需要给它加上 2^0 = 1。6 + 1 = 7，二进制变成 0111。美丽度从 2 增加到 3，净增 1。这次操作的成本是 1。
• 如果我们想把它第 3 位的 0 变成 1，我们需要给它加上 2^3 = 8。6 + 8 = 14，二进制变成 1110。美丽度从 2 增加到 3，也净增 1。但这次操作的成本是 8。

很明显，为了花最小的代价获得 +1 的美丽度，我们应该总是选择翻转一个数最低位的那个 0。

为什么呢？因为如果你要翻转第 p 位的 0，你需要加上的数至少是 2^p。如果你选择的 p 是最低的那个 0 所在的位置，那么 x 的 p-1 到 0 位就全是 1（如果 p>0 的话），或者根本没有比 p 更低的位。不对不对，本喵说错了！应该是，如果 p 是最低的 0 位，那么 0 到 p-1 位可以是任意的。当我们给 x 加上 2^p 时，由于第 p 位是 0，所以不会有进位影响到比 p 更高的位，同时 0 到 p-1 位也不会被改变。所以，x 加上 2^p 恰好只会把第 p 位的 0 变成 1，其他位都不变，美丽度就正好 +1 啦！

所以，对于任何一个数 x，让它的美丽度 +1 的最小成本就是 2^p，其中 p 是 x 二进制表示中最低的那个 0 的位置。

贪心策略

现在问题就转化成：我们有很多种可以增加 1 点美丽度的“升级”机会，每种机会都有一个成本（2^0, 2^1, 2^2, ...）。我们有一个总预算 k，要买尽可能多的“升级”。

这不就是最经典的贪心问题嘛！当然是每次都买最便宜的那个啦！喵~

我们的策略就清晰了：

1. 我们从最低的比特位开始考虑，也就是从 p = 0 开始。此时的升级成本是 2^0 = 1。
2. 我们检查数组 a 中的每一个数，看看哪些数的最低 0 位恰好在第 p 位。
3. 对于所有符合条件的数，只要我们的预算 k 还够（k >= 2^p），我们就对它进行升级！也就是把这个数加上 2^p，然后从 k 中减去成本。
4. 当 p=0 的所有升级机会都被我们买完（或者买不起了），我们就去考虑 p = 1 的情况，成本是 2^1 = 2。然后是 p = 2，成本是 2^2 = 4，以此类推。
5. 我们一直重复这个过程，直到我们的预算 k 连当前最便宜的升级都买不起了，就可以停下来了。

因为我们总是优先选择成本最低的升级（p 值小的），所以这个贪心策略可以保证我们用有限的 k 获得了最多的美丽度增长，喵呜~

如何找到最低的 0 位？

这里有一个很酷的位运算小技巧哦！ 要找一个数 x 的最低 0 位，我们可以先对 x 按位取反，得到 ~x。这样 x 原来的 0 位在 ~x 中就变成了 1 位。于是问题就变成了找 ~x 的最低 1 位。

而找一个数 y 的最低 1 位，有一个经典的 lowbit 操作：lowbit(y) = y & -y。这个操作会返回一个只有最低 1 位是 1，其他位都是 0 的数。比如 lowbit(12)，12 是 1100，-12（补码）是 0100，1100 & 0100 = 0100，也就是 4。

所以，要检查 a[j] 的最低 0 位是不是在第 p 位，我们只需要检查 lowbit(~a[j]) 是不是等于 2^p 就行啦！

题解代码

下面就是带有本喵注释的 C++ 代码啦，希望能帮助主人更好地理解！

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

// 在某些编译器（比如 MSVC）上需要这个头文件来使用 __popcnt64
#if defined(_MSC_VER)
#include <intrin.h>
#define __builtin_popcountll __popcnt64
#endif

// lowbit 函数，一个神奇的位运算魔法，喵~
// 它的作用是找出 x 的二进制表示中，最低位的 1 所代表的值。
// 比如 lowbit(12) -> lowbit(1100_2) -> 返回 4 (0100_2)
long long lowbit(long long x) {
    // x & -x 在补码表示下可以巧妙地分离出最低位的 1
    return x & -x;
}

void solve() {
    int n;
    long long k;
    std::cin >> n >> k;
    std::vector<long long> a(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }

    // 我们的贪心策略！从成本最低的升级开始~
    // i 代表比特位的位置，从 0 到 62 (因为 long long 最多 63 位)
    for (int i = 0; i < 63; ++i) {
        long long cost = 1LL << i; // 当前位的升级成本是 2^i
        
        // 遍历数组里的每个数字，看看有没有便宜的升级机会
        for (int j = 0; j < n; ++j) {
            // 检查 a[j] 的最低 0 位是不是在第 i 位
            // 也就是检查 ~a[j] 的最低 1 位是不是 2^i
            if (lowbit(~a[j]) == cost) {
                if (k >= cost) { // 如果我们的预算还够
                    k -= cost;         // 花掉成本
                    a[j] += cost;      // 进行升级！美丽度+1，耶！
                } else {
                    // 如果连这个都买不起了，那更贵的也肯定买不起了
                    // 直接结束所有循环，收工回家吃小鱼干~
                    goto end_loops; 
                }
            }
        }
    }

end_loops:; // 一个简单的跳出多重循环的方法

    // 所有能做的操作都做完啦，现在来数一数我们有多少颗美丽的宝石！
    long long total_beauty = 0;
    for (long long val : a) {
        // __builtin_popcountll 是一个 GCC/Clang 内置函数，专门用来数 1 的个数，超快的！
        total_beauty += __builtin_popcountll(val);
    }
    std::cout << total_beauty << std::endl;
}

int main() {
    // 加速输入输出，让程序跑得像猫一样快！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

知识点介绍

这道题里藏着一些非常有用的知识点哦，掌握了它们，以后遇到类似的位运算问题就能迎刃而解啦！

1. 贪心算法 (Greedy Algorithm)

   • 核心思想：在每一步选择中，都采取当前状态下最好或最优的选择，从而希望能导致结果是全局最好或最优的。
   • 在本题的应用：我们的目标是用有限的预算 k 换取最多的美丽度。每次美丽度 +1 的收益是固定的，所以我们自然要选择成本最低的操作。我们从成本 2^0 开始，然后是 2^1, 2^2... 这样从小到大依次考虑，保证了每花一分钱都是在当前最划算的地方，这就是贪心！

2. 位运算 (Bitwise Operations) 位运算是直接对整数在内存中的二进制位进行操作，速度非常快，是算法竞赛中的一大神器，喵！

   • __builtin_popcountll: 这个是 GCC/Clang 的一个内建函数，全称是 "population count"，用来计算一个 long long 类型的整数的二进制表示中有多少个 1。非常方便！
   • ~ (按位取反): 把一个数的所有二进制位反转，0 变 1，1 变 0。我们用它来把“找最低的 0”问题转换成“找最低的 1”。
   • & (按位与): 只有当两个操作数的对应位都是 1 时，结果的对应位才是 1，否则为 0。
   • lowbit(x) 操作 (x & -x): 这是一个非常经典的技巧。在计算机中，负数通常用补码表示。-x 的补码等于 ~x + 1。这个操作 x & (~x + 1) 的结果就是只保留 x 中最低位的 1，其余位都清零。例如，x = 12 (..001100)，~x = (..110011)，~x+1 = (..110100)，x & (~x+1) = (..000100)，结果是 4。这个技巧在树状数组等数据结构中也经常用到哦！

希望本喵的讲解对主人有帮助！如果还有不明白的地方，随时可以再来问我哦，喵~ >w<