首页 > 代码库 > Codeforces Round #250 (Div. 2)——The Child and Set

Codeforces Round #250 (Div. 2)——The Child and Set

题目链接

  • 题意:
    给定goal和limit,求1-limit中的若干个数,每一个数最多出现一次,且这些数的lowbit()值之和等于goal,假设存在这种一些数,输出个数和每一个数;否则-1
  • 分析:
    先考虑一下比較普通的情况,给一些数,和一个goal,问时候能达到。(最好还是设这些数已经从大到小排序)
    考虑能否够贪心,对于当前的数x:
    1、之后的数的和能等于x,那么假设x<=goal,显然必须选x;
    2、之后的数的和能等于x-1,那么同上(这个情况就是二进制的情况)
    3、之后的数的和不包含上述两个情况,那么不能贪心(推測)

    再分析这个题,是符合第一个情况的。对于第i + 1位,当第i位出现两个1时候,之后才会在i + 1位出现一个1,所以符合第一个情况,能够贪心

lowbit()函数事实上就是一个数的二进制最低位的1代表的十进制数值

const int MAXN = 25;

int lowbit(int n)
{
    return n & -n;
}

int bin(int n)
{
    int ret = 0;
    while (n)
    {
        n >>= 1;
        ret++;
    }
    return ret - 1;
}
vector<int> G[MAXN];

int main()
{
//    freopen("in.txt", "r", stdin);
    int sum, limit;
    while (~RII(sum, limit))
    {
        REP(i, MAXN) G[i].clear();
        vector<int> ans;
        int s = 0;
        FE(i, 1, limit)
        {
            int t = bin(lowbit(i));
            G[t].push_back(i);
            s += lowbit(i);
        }
        if (s < sum)
            puts("-1");
        else
        {
            FED(i, 22, 0)
            {
                int val = (1 << i);
                int ct = min((int)G[i].size(), sum / val);
                REP(j, ct)
                    ans.push_back(G[i][j]);
                sum -= ct * val;
            }
            WI(ans.size());
            REP(i, ans.size())
                cout << ans[i] << ' ';
            puts("");
        }
    }
    return 0;
}