codeforces 437B. The Child and Set 解题报告

题目链接：http://codeforces.com/contest/437/problem/B

题目意思：给出两个整数 sum 和 limit，问能否从1 ～ limit 这些数中选出一些数（注意：这些数最多只能取一次！），使得它们的lowbit 之和 等于 sum。不能则输出 -1。

      这题总的来说比较直接。一开始犯了个比较傻的错误，以为除了2的幂以外，其他的 lowbit 都是1。还有一点需要注意的是，代码中 if (sum - t >= 0)  很重要！因为偶数的lowbit参差不齐，有可能sum-t 变为负数的！总后往前贪（limit ---->  1)，能保证每次贪的数是最大的！这样也能尽快结束循环，防止超时。

      

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

const int maxn = 1e5 + 5;
int ans[maxn];

int main()
{
    int sum, limit;
    while (cin >> sum >> limit)
    {
        memset(ans, 0, sizeof(ans));
        int t, cnt = 0, tot = 0;
        for (int i = limit; i >= 1; i--)   // 从大到小开始贪心
        {
            if (i % 2 == 0)
            {
                int count = 0;
                for (int j = i; !(j & 1); j >>= 1)   // 从右往左看，1第一次出现的位置
                    count++;
                t = pow(2.0, count);  // 求出该偶数的lowbit
                if (sum - t >= 0)    // 该数的lowbit能组成sum的条件
                {
                    sum -= t;
                    ans[i] = 1;
                    tot++;
                }
            }
            else
            {
                sum--;     // 奇数的lowbit是1
                ans[i] = 1;
                tot++;
            }
            if (!sum)
                break;
        }
        if (sum)
            printf("-1
");
        else
        {
            printf("%d
", tot);
            for (int i = 1; i <= limit; i++)
            {
                if (ans[i])
                    printf("%d ", i);
            }
            printf("
");
        }
    }
    return 0;
}