Codeforces 437B The Child and Set

题目链接：Codeforces 437B The Child and Set

開始是想到了这样的情况，比方lowbit之后从大到小排序后有这么几个数，200。100，60。50。S = 210。那先选了200肯定就不行了，所以写了个DFS。果断TLE。后来想了想lowbit之后的值都是最高位是1。其余位都是0的二进制数，所以上边的情况是不会出现的，至于原因我感觉我说不清楚。。

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;

const int MAX_N = 100000 + 100;

struct Node
{
    int val, i;
};
Node arr[MAX_N];

int cmp(Node a, Node b)
{
    return a.val > b.val;
}
int lowbit(int x)
{
    return x & (-x);
}
int s, limit,sum = 0;
int path[MAX_N], num;

int main()
{
    scanf("%d%d", &s, &limit);
    for(int i = limit; i >= 1; i--)
    {
        arr[i].val = lowbit(i);
        arr[i].i = i;
    }
    sort(arr + 1, arr + 1 + limit, cmp);
    int sum = 0;
    for(int i = 1; i <= limit; i++)
    {
        if(arr[i].val + sum > s)
            continue;
        sum += arr[i].val;
        path[num++] = arr[i].i;
        if(sum == s)
            break;
    }
    if(sum == s)
    {
        printf("%d
", num);
        printf("%d", path[0]);
        for(int i = 1; i < num; i++)
            printf(" %d", path[i]);
        puts("");
    }
    else
        puts("-1");
    return 0;
}