题解：P9256 [PA 2022] Muzyka pop 2

LoongPig · 2025-03-07 13:32:16 · 题解

题意解释

题目主要意思是让你构造一个严格递减的序列使它满足 \sum \text{popcount}=n。

题目思路

先把 n 范围以内的数的二进制位下 1 的个数加起来。

然后用贪心的思维倒序枚举并去掉每个可以去掉的数。

最后把序列输出出来就好了。

题目标程

#include<bits/stdc++.h>
using namespace std;
inline int popcnt(int x) {
//计算 x 这个数在二进制下有多少个 1
    int cnt = 0;
    while (x) {
        cnt += x & 1;
        x >>= 1; //x /= 2
    }
    return cnt;
}
int n, m, sum = 0;
vector<int> DragonPig;
int main() {
    scanf("%d", &n);
    m = n;
    while (m--) {
        sum += popcnt(m + 1);//计算 1 ~ n 每个数在二进制下 1 的个数的和
    }
    for (int i = n; i >= 1; i--) {
        if (sum - popcnt(i) >= n) {//判断能不能去掉
            sum -= popcnt(i);
        } else {
            DragonPig.push_back(i);//不能去掉就把它加入序列
        }
    }
    printf("%d\n", (int)DragonPig.size());
    for (auto dragonpig : DragonPig) {
        printf("%d ", dragonpig);
    }
    /*
    用不了 auto 的可以这么写：
    for (int i = 0; i < (int)DragonPig.size(); i++) {
        printf("%d ", DragonPig[i]);
    }
    */

    return 0;//完结撒花！
}

这是本蒟蒻的第一篇题解，求过求过。