题解：CF2118C Make It Beautiful

首先只有把一个数二进制表示下某一位的 $0$ 补成 $1$ 才对答案有贡献。假设这一位是第 $i$ 位（钦定最低位是第 $0$ 位），那么要把这一位补成 $1$，$k$ 需要减掉 $2^i$。 我们贪心地考虑，肯定是先让从低位向高位看，第一个有 $0$ 的位置最低的这个数进行操作才是更优的。根据这个建立一个优先队列，按照每个数最低位的 $0$ 的所在位子升序排序。

考场上看到要求每个数最低位的 $0$ 的所在位子，突然有了一个非常睿智的想法。这不就跟树状数组里的 $lowbit(x)$ 非常像嘛！

但是 $lowbit(x)$ 是求每个数最低位的 $1$ 所对应的值诶，怎么办？

~~把 $x$ 取反就可以了。~~
# CODE

```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 5e+3 + 3;
int T, n, k, ans;
int lowbit(int x)
{
    x = ~x;
    return x & -x;
}
struct node
{
    int w;
    friend bool operator < (const node &x, const node &y)
    {
        return lowbit(x.w) > lowbit(y.w);
    }
};
priority_queue<node> q;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> T;
    while (T--)
    {
        while (q.size())
        {
            q.pop();
        }
        cin >> n >> k;
        ans = 0;
        for (int i = 1; i <= n; i++)
        {
            int x;
            cin >> x;
            ans += __popcount(x);
            q.push({x});
        }
        while (k)
        {
            int now = q.top().w;
            q.pop();
            int nd = lowbit(now);
            if (k < nd)
            {
                break;
            }
            k -= nd;
            ans++;
            now += nd;
            q.push({now});
        }
        cout << ans << '\n';
    }
    return 0;
}
```

正在渲染内容...