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\n", num);
printf("%d", path[0]);
for(int i = 1; i < num; i++)
printf(" %d", path[i]);
puts("");
}
else
puts("-1");
return 0;
}