网硕互联帮助中心P9256 [PA 2022] Muzyka pop 2
题目描述
题目译自 PA 2022 Runda 2 Muzyka pop 2
你可能还记得，Matthew 喜欢流行音乐。他刚刚编好一首新歌，就差给这首歌谱一个结尾了。
Matthew 想让这个结尾包含一些非空的音符，这些音符用其响度表示，响度是一个正整数。Matthew 可以使用任何响度的音符，但结尾的任务是逐渐淡出整首歌——出于这个原因，结尾的音符响度必须形成一个严格递减的序列。
你可能知道或记得，流行音乐中好的节拍是很重要的。这次 Matthew 发现响度为
x
x
x 的音符的节拍值为
x
x
x 的二进制形式中
1
1
1 的个数。考虑这首歌的剩余部分，他想让这个结尾所有音符的节拍值之和恰好为
n
n
n。
帮他找到这个正确的音符响度序列。可以证明总存在至少一个满足条件的序列，因此你的任务是输出字典序最小的序列。
注：如果对于两个数字序列
A
A
A 和
B
B
B，在两序列第一个不同的位置，
A
A
A 序列中这个位置包含的整数比
B
B
B 序列的小，我们称数字序列
A
A
A 的字典序比
B
B
B 的字典序小。如果不存在这个位置，则称更短的那个数字序列字典序更小。例如，序列
[
1
,
10000000
]
[1, 10000000]
[1,10000000] 的字典序小于序列
[
2
,
2
]
[2,2]
[2,2]，序列
[
4
,
2
,
20
,
30
,
40
]
[4, 2, 20, 30, 40]
[4,2,20,30,40] 的字典序小于
[
4
,
2
,
100
,
1
]
[4, 2, 100, 1]
[4,2,100,1]，并且序列
[
5
,
4
,
3
,
2
]
[5,4,3,2]
[5,4,3,2] 的字典序小于序列
[
5
,
4
,
3
,
2
,
1
]
[5,4,3,2,1]
[5,4,3,2,1]。
输入格式
输入一行一个整数
n
n
n，表示要求的序列中音符的节拍值之和。
输出格式
输出第一行包含一个整数
k
k
k，表示找到的这个序列的长度。
第二行包含
k
k
k 个正整数，表示找到的这个序列。这个序列应该是字典序最小且严格递减的，并且这些正整数的二进制表示中
1
1
1 的个数和应恰好是
n
n
n。
输入输出样例 #1
输入 #1
3
输出 #1
2
3 1
输入输出样例 #2
输入 #2
10
输出 #2
6
7 5 4 3 2 1
说明/提示
对于
100
%
100\\%
100% 的数据，满足：
1
≤
n
≤
1
0
6
1\\le n\\le 10 ^ 6
1≤n≤106。
C++实现
#include<bits/stdc++.h>
using namespace std;
inline int popcnt(int x) {
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);
}
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);
}
return 0;
}
后续
接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容
评论前必须登录！
注册