自动搬运

查看原文

来自洛谷，原作者为

	LoongPig 人生中最大的遗憾，不是努力了没有成功，而是从未尝试过努力||发接龙拉黑

搬运于2025-08-24 22:46:49，当前版本为作者最后更新于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;//完结撒花！
}

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