【CSP】CSP-J 2020真题 | 优秀的拆分 luogu-P7071 （适合GESP二、三级及以上考生练习）
CSP-J 2020第一题-优秀的拆分，重点考察整数的二进制位拆分思想，适合GESP二、三级及以上的考生从多种思路下手练习，难度⭐☆，洛谷难度等级入门−。
P7071 [CSP-J 2020] 优秀的拆分
题目要求
题目描述
一般来说，一个正整数可以拆分成若干个正整数的和。
例如，$1=1$，$10=1+2+3+4$ 等。对于正整数 $n$ 的一种特定拆分，我们称它为“优秀的”，当且仅当在这种拆分下，$n$ 被分解为了若干个不同的 $2$ 的正整数次幂。注意，一个数 $x$ 能被表示成 $2$ 的正整数次幂，当且仅当 $x$ 能通过正整数个 $2$ 相乘在一起得到。
例如，$10=8+2=2^3+2^1$ 是一个优秀的拆分。但是，$7=4+2+1=2^2+2^1+2^0$ 就不是一个优秀的拆分，因为 $1$ 不是 $2$ 的正整数次幂。
现在，给定正整数 $n$，你需要判断这个数的所有拆分中，是否存在优秀的拆分。若存在，请你给出具体的拆分方案。
输入格式
输入只有一行，一个整数 $n$，代表需要判断的数。
输出格式
如果这个数的所有拆分中，存在优秀的拆分。那么，你需要从大到小输出这个拆分中的每一个数，相邻两个数之间用一个空格隔开。可以证明，在规定了拆分数字的顺序后，该拆分方案是唯一的。
若不存在优秀的拆分，输出
-1。
输入输出样例 #1
输入 #1
1
6
输出 #1
1
4 2
输入输出样例 #2
输入 #2
1
7
输出 #2
1
-1
输入输出样例 #3
输入 #3
1
126
输出 #3
1
64 32 16 8 4 2
说明/提示
样例 1 解释
$6=4+2=2^2+2^1$ 是一个优秀的拆分。注意，$6=2+2+2$ 不是一个优秀的拆分，因为拆分成的 $3$ 个数不满足每个数互不相同。
【数据规模与约定】
- 对于 $20\%$ 的数据，$n \le 10$。
- 对于另外 $20\%$ 的数据，保证 $n$ 为奇数。
- 对于另外 $20\%$ 的数据，保证 $n$ 为 $2$ 的正整数次幂。
- 对于 $80\%$ 的数据，$n \le 1024$。
- 对于 $100\%$ 的数据，$1 \le n \le {10}^7$。
题目分析
本题作为 CSP-J 的第一道真题，主要考察基本数学逻辑及初版进制拆分思想。题目要求把一个十进制整数 $n$，寻找是否能拆分成互不相同的一系列“2 的整数次幂”的和。
解题思路切入点剖析：
为什么奇数是不允许的？ 在所有的“2 的次幂”中：$2^1=2, 2^2=4, 2^3=8 \dots$ 这些“正整数次幂”全部都是偶数。 能够用来组成奇数的“次幂”有且仅有 $2^0=1$。但请仔细阅读题意：题目中明确要求我们需要的是“正整数次幂（即次数至少是 1）”！ 所以无论使用多少个纯偶数次幂去组合，都不可能凑出奇数。 结论非常干脆：如果输入的数 $n$ 是奇数，直接输出
-1结束计算即可。如何找到对应拆分？其本质是什么？ 实际上题目就是暗示我们进行二进制转换。因为十进制转二进制的过程，本质就是把一个十进制数，写成若干个“不同高低位带来的 2 的次幂的和”。 比如 $10{\text{十进制}}$ 的正反换算二进制会变成 $1010{\text{二进制}}$。它的从右向左第一位对应十进制的 2权值，它的第三位对应了十进制的 8权值，相加恰好就是 10。从高位遍历到低位输出进制基数刚恰就是符合题目的“从大到小”要求！
面对处在不同阶段学习进度的初学、进阶选手，我们可以有多种手段实现上述逻辑，激发自己对基础算法底层实现的思考：
示例代码
解法一：直观的贪心与模拟（初学者友好推荐）
即使你完全没有学过进制转换，也没有听说过位运算机制，也能顺理成章通过“生活常识”写出本题。面对一个目标数 $n$，我们每次只需要找出最接近而不撑爆 $n$ 的那个“最大的 2 的倍增次幂”，抠掉它之后，我们再找剩下碎片的下一个倍增次幂……直到 $n$ 被减完了。
例如：$n = 10$，不超过它的最大 2 次幂是 $8$。减掉 8 后余下 $2$；继续找不超过 $2$ 的最大次幂，它就是 $2$ 本身，全部剪完 0 收工。因此拆分出的数值先后是 8 2。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
int main() {
int n;
std::cin >> n;
// 第一步：如果 n 不能被 2 整除，说明是奇数，不满足题意无法分配。
if (n % 2 != 0) {
std::cout << -1 << std::endl;
return 0; // 直接打断退出
}
// 第二步：循环倍增。找到刚好不超过 n 的那个最大的 2 的次幂值
int power = 2; // 起点最少是 2
while (power <= n) {
power *= 2;
}
// 循环结束后 power 肯定跑到 n 的上限上面超标了，比如 n=10 就会导致 power 大到了 16。
// 我们在此回退一档：
power /= 2;
// 第三步：拿到的这个最大的 power 开始开动，依次减去符合要求的配额
while (n > 0) {
if (n >= power) { // 判断当前的 n 够不够减
std::cout << power << " "; // 够减必定是要这个权值的，马上输出
n -= power; // 目标数字扣掉消耗
}
power /= 2; // 不断降档试探！次幂阶梯往下降一等级，例如从 8 砍下来降到去试探 4
}
std::cout << std::endl;
return 0;
}
解法二：优雅的二进制位运算（进阶降维打击）
如果你已经熟练掌握了 C++ 中的高级法宝 位运算（按位与 &，左移 <<，右移 >>），这题可以直接用几行代码解决！
任何数字在计算机底层早已自带打包做做好了“二进制形态”，我们不需要做任何模拟裁剪。直接从最高的比特位往下查验每个内存位，只要这位是 1，那么果断计算这一位的自带“次幂物理意义”并打印出来即可！
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
int main() {
int n;
std::cin >> n;
// 奇数（二进制最低位为1）肯定不能拆分成若干个正整数次幂（2的次幂要求都是偶数）
// 所以如果是奇数，直接输出 -1。在底层运算中，n & 1 和 n % 2 != 0 是一模一样的意义！
if (n & 1) {
std::cout << -1 << std::endl;
} else {
// 从最高可能位数跨度开始，向下判断系统内每一位是否为 1。
// 数据提示 n 最大是 10^7, 而 2^23=8388608, 2^24=16777216。
// 保险起见从 24 位往下查，一直推回到第 1 位。
for (int i = 24; i >= 1; --i) {
// 通过右移掩码位运算 (n >> i) & 1 取出第 i 位的值是否为 "真 (1)"
if ((n >> i) & 1) {
// 如果该位有值确被占据着，则它身上必定披着对应量级的 2 次幂
// 逆着位运算把权值还原并输出： (1 << i)
std::cout << (1 << i) << " ";
}
}
std::cout << std::endl;
}
return 0;
}
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
GESP 学习专题站：GESP WIKI
"luogu-"系列题目可在洛谷题库进行在线评测。
"bcqm-"系列题目可在编程启蒙题库进行在线评测。
欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答
欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总
欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助
