题目类型：位运算

传送门：><

题意：给出\(sum和limit\)，求一个集合\(S\)，其中的元素互不相同且不超过\(limit\)，他们的\(lowbit\)之和等于\(sum\)

解题思路

首先我们求出\(limit\)范围内每个数的\(lowbit\)，并从大到小排序。要选出一些数使其和等同于\(sum\)，根据我们已有的二进制知识，肯定是先选大的，再选小的。

为什么？考虑所有的\(lowbit\)都是2的幂，也就相当于我们将\(sum\)转为二进制以后，每一个1是一个\(lowbit\)。然而由于可能大的不存在，需要由小的\(lowbit\)叠加而产生。我们不知道小的应该叠加几个，然而如果有大的肯定大的直接上就好了，把小的留给别人去叠加。如果大的全部上了小的还不够，那么肯定无法完成

反思

贪心思想。感觉好像贪心的题大多有排序。贪心其实只需要证明自己的这种做法是正确的就好了

Code

/*By DennyQi 2018*/#include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;typedef long long ll;const int MAXN = 10010;const int MAXM = 20010;const int INF = 1061109567;inline int Max(const int a, const int b){ return (a > b) ? a : b; }inline int Min(const int a, const int b){ return (a < b) ? a : b; }inline int read(){    int x = 0; int w = 1; register char c = getchar();    for(; c ^ '-' && (c < '0' || c > '9'); c = getchar());    if(c == '-') w = -1, c = getchar();    for(; c >= '0' && c <= '9'; c = getchar()) x = (x<<3) + (x<<1) + c - '0'; return x * w;}struct Num{    int l_b,val;}a[100010];int sum,limit,tot;int ans[100010],top;inline bool cmp(const Num& a, const Num& b){    if(a.val != b.val) return a.l_b > b.l_b;    return a.val < b.val;}int main(){    sum = read(), limit = read();    for(int i = 1; i <= limit; ++i){        a[i].l_b = i & (-i);        a[i].val = i;    }    sort(a+1, a+limit+1, cmp);    for(int i = 1; i <= limit; ++i){        if(tot + a[i].l_b <= sum){            ans[++top] = a[i].val;            tot += a[i].l_b;        }    }    if(tot < sum){        printf("-1");        return 0;    }    printf("%d\n", top);    while(top--)printf("%d ", ans[top+1]);    return 0;}