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;
}