【CSP】CSP-J 2020真题 | 优秀的拆分 luogu-P7071 |(适合GESP二、三级及以上考生练习)

CSP-J 2020第一题-优秀的拆分，重点考察整数的二进制位拆分思想，适合GESP二、三级及以上的考生从多种思路下手练习，难度⭐☆，洛谷难度等级入门−。

P7071 [CSP-J 2020] 优秀的拆分

题目要求

题目描述

一般来说，一个正整数可以拆分成若干个正整数的和。

例如，， 等。对于正整数  的一种特定拆分，我们称它为“优秀的”，当且仅当在这种拆分下， 被分解为了若干个不同的  的正整数次幂。注意，一个数  能被表示成  的正整数次幂，当且仅当  能通过正整数个  相乘在一起得到。

例如， 是一个优秀的拆分。但是， 就不是一个优秀的拆分，因为  不是  的正整数次幂。

现在，给定正整数 ，你需要判断这个数的所有拆分中，是否存在优秀的拆分。若存在，请你给出具体的拆分方案。

输入格式

输入只有一行，一个整数 ，代表需要判断的数。

输出格式

如果这个数的所有拆分中，存在优秀的拆分。那么，你需要从大到小输出这个拆分中的每一个数，相邻两个数之间用一个空格隔开。可以证明，在规定了拆分数字的顺序后，该拆分方案是唯一的。

若不存在优秀的拆分，输出 -1。

输入输出样例 #1

输入 #1

6

输出 #1

4 2

输入输出样例 #2

输入 #2

7

输出 #2

-1

输入输出样例 #3

输入 #3

126

输出 #3

64 32 16 8 4 2

说明/提示

样例 1 解释

 是一个优秀的拆分。注意， 不是一个优秀的拆分，因为拆分成的  个数不满足每个数互不相同。

【数据规模与约定】

• 对于  的数据，。
• 对于另外  的数据，保证  为奇数。
• 对于另外  的数据，保证  为  的正整数次幂。
• 对于  的数据，。
• 对于  的数据，。

题目分析

本题作为 CSP-J 的第一道真题，主要考察基本数学逻辑及初版进制拆分思想。题目要求把一个十进制整数 ，寻找是否能拆分成互不相同的一系列“2 的整数次幂”的和。

解题思路切入点剖析：

1. 为什么奇数是不允许的？在所有的“2 的次幂”中： 这些“正整数次幂”全部都是偶数。 能够用来组成奇数的“次幂”有且仅有 。但请仔细阅读题意：题目中明确要求我们需要的是“正整数次幂（即次数至少是 1）”！ 所以无论使用多少个纯偶数次幂去组合，都不可能凑出奇数。 结论非常干脆：如果输入的数  是奇数，直接输出 -1 结束计算即可。

2. 如何找到对应拆分？其本质是什么？实际上题目就是暗示我们进行二进制转换。因为十进制转二进制的过程，本质就是把一个十进制数，写成若干个“不同高低位带来的 2 的次幂的和”。 比如  的正反换算二进制会变成 。它的从右向左第一位对应十进制的 2权值，它的第三位对应了十进制的 8权值，相加恰好就是 10。从高位遍历到低位输出进制基数刚恰就是符合题目的“从大到小”要求！

面对处在不同阶段学习进度的初学、进阶选手，我们可以有多种手段实现上述逻辑，激发自己对基础算法底层实现的思考：

示例代码

解法一：直观的贪心与模拟（初学者友好推荐）

即使你完全没有学过进制转换，也没有听说过位运算机制，也能顺理成章通过“生活常识”写出本题。面对一个目标数 ，我们每次只需要找出最接近而不撑爆  的那个“最大的 2 的倍增次幂”，抠掉它之后，我们再找剩下碎片的下一个倍增次幂……直到  被减完了。

例如：，不超过它的最大 2 次幂是 。减掉 8 后余下 ；继续找不超过  的最大次幂，它就是  本身，全部剪完 0 收工。因此拆分出的数值先后是 8 2。

#include<iostream>intmain(){    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，那么果断计算这一位的自带“次幂物理意义”并打印出来即可！

#include<iostream>intmain(){    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;}

“luogu-”系列题目可在洛谷题库进行在线评测。

“bcqm-”系列题目可在编程启蒙题库进行在线评测。