CF2118C Make It Beautiful

比较搞人的一道题目。

考虑比 $a$ 大的且二进制中 $1$ 的数目比 $a$ 的多的最小的数字 $b$。通过尝试可以发现，$b$ 的二进制中比 $a$ 多出来的那个 $1$ 恰好落在 $a$ 的二进制中最低位的 $0$ 所在的位置。

于是有一个很直接的思路：考虑每次能让 $a_i$ 的漂亮值（二进制中 $1$ 的个数）变大 $1$ 的操作次数。枚举找到最小的操作次数后更新，直至 $k$ 次操作被用完或无法再让某一个 $a_i$ 的漂亮值增加 $1$。

然而发现在第 $10$ 个点 T 了。

这里想了有一会儿：不妨改变一下枚举顺序。先按照二进制数位枚举，这样的话可以顺势更新值，再枚举数字。因为前面的一种方法会造成对最小值的重复计算，所以会 T。

#include <bits/stdc++.h>
#define MAXN 5005
using namespace std;
long long a[MAXN];
int count(long long x)
{
    int ans=0;
    while (x>0)
    {
        if (x&1)
        {
            ans++;
        }
        x>>=1;
    }
    return ans;
}
int main()
{
    long long T,n,k;
    cin>>T;
    while (T)
    {
        cin>>n>>k;
        long long cnt=0,ans=0;
        for (int i=1;i<=n;i++)
        {
            cin>>a[i];
            ans+=count(a[i]);
        }
        for (int i=0;i<=60;i++)
        {
            long long p=(1ll<<i);
            for (int j=1;j<=n;j++)
            {
                if (!(a[j]&p)&&(cnt+p<=k))
                {
                    cnt+=p;
                    ans++;
                }
            }
        }
        cout<<ans<<"\n";
        T--;
    }
    return 0;
}