题解：CF437B The Child and Set

檀溪的小窝 / 2024-09-27 / 原文

CF437B The Child and Set 题解

这题目就一个问题。

啥是 $\operatorname {lowbit}$？

$\operatorname {lowbit}(x)$ 是指 $x$ 的二进制表示中最低位的 $1$ 所表示的值。

例如 $(14)_{10} = (1110)_2$，其中最低位的 $1$ 在第二位，表示 $(2)_{10}$，即 $\operatorname {lowbit}(14) = 2$。

接下来考虑如何选取。

一个贪心策略是按照 $\operatorname {lowbit}$ 从大到小选取，如果当前的数的 $\operatorname {lowbit}$ 小于剩余的 $n$，那么就选到这个数，并让 $n$ 减去当前数的 $\operatorname {lowbit}$。

显而易见这样取出来的总和最大。

如果取到最后还不能取完，那么就输出 -1。

有点类似于倍增。

至于怎么求 $\operatorname {lowbit}$，先人给我们找好了方法：

\[\operatorname {lowbit}(x) = x\; \& \;(-x) \]

这是利用计算机补码性质完成的，其中的符号 $\&$ 代表按位与。

最终代码如下：

#include<bits/stdc++.h>
#define MAXM 100010
using namespace std;
struct node{
    int num, bit;
};
bool operator < (node a, node b){ return a.bit < b.bit; }
bool operator > (node a, node b){ return a.bit > b.bit; }
node a[MAXM];
int n, m;
vector<int> ans;
int main(){
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= m; i++) a[i] = (node){i, i & (-i)};
    sort(a + 1, a + m + 1, greater<node>());
    for(int i = 1; i <= m && n >= 0; i++){
        if(n >= a[i].bit){
            n -= a[i].bit;
            ans.push_back(a[i].num);
        }
    }
    if(n != 0) printf("-1\n");
    else{
        printf("%ld\n",ans.size());
        for(int i = 0; i < ans.size(); i++) printf("%d ",ans[i]);
        printf("\n");
    }
    return 0;
}