1. 从“优秀的拆分”说起一道题背后的算法思维启蒙如果你正在准备CSP-J/S的初赛或者刚开始接触信息学竞赛那么“优秀的拆分”这道题绝对是一个绕不开的经典。作为CSP-J 2020年普及组的第一题它看似简单却精准地考察了参赛者对计算机底层二进制表示、循环与条件判断等基础算法的掌握程度。很多新手第一次看到题目可能会有点懵“拆分”是什么意思“优秀”又怎么定义这恰恰是竞赛题目的魅力所在——将一个抽象的计算概念包装成一个具体的、需要你一步步推理解决的问题。这道题的核心其实是让我们把一个给定的正整数表示成若干个不同的2 的正整数次幂的和。比如数字 6 可以拆成 2 4因为 2 是 2^14 是 2^2它们都是2的正整数次幂并且互不相同。这种表示方法在计算机科学里非常基础因为它直接对应着二进制。任何一个正整数在计算机内部都是以二进制的形式存储的而二进制数的每一位从低到高就代表了 2^0, 2^1, 2^2... 这些幂次是否包含在内。题目要求的“从大到小输出”其实就是让我们从二进制的高位向低位进行解析。所以解决这道题不仅仅是写对一个程序更是理解“如何将人类对数字的直观理解转化为计算机能够一步步执行的机械过程”。这个过程就是算法思维的核心。接下来我会带你彻底拆解这道题从题意理解、思路分析、代码实现到易错点排查手把手让你不仅做出这道题更能掌握这类问题的通用思考方法。2. 题意深度解析与“优秀拆分”的数学本质我们先抛开代码把题目要求用人话彻底讲清楚。题目描述通常是这样的对于一个正整数 ( n )如果它能被表示为若干个不同的2 的正整数次幂即 ( 2^k )其中 ( k \ge 1 ) 之和那么这种拆分被称为“优秀的拆分”。我们的任务是给定一个 ( n )如果它存在优秀拆分则从大到小输出这些幂次如果不存在则输出-1。这里有几个关键约束必须一字一句地理解不同的这意味着在拆分结果里同一个2的幂次只能出现一次。比如8 不能拆成 44因为4出现了两次。2的正整数次幂这意味着幂次 ( k ) 必须大于等于1。也就是说数值上只能是 2, 4, 8, 16, 32...特别注意1即 ( 2^0 ) 是不被允许的因为0不是正整数。这是本题最大的陷阱之一。从大到小输出这是输出格式要求决定了我们遍历或生成这些幂次的顺序。那么什么样的 ( n ) 才拥有“优秀的拆分”呢根据上面的定义因为不能使用1(2^0)所以拆分中用到的所有数都是偶数2, 4, 8... 都是偶数。若干个偶数相加结果必然还是偶数。由此我们可以得出一个至关重要的结论当且仅当 ( n ) 是大于0的偶数时它才可能存在优秀的拆分。奇数比如1, 3, 5, 7...一定没有优秀拆分。为什么我们反证一下假设一个奇数能被拆成若干个不同的2的正整数次幂之和。这些幂次最小是2都是偶数。偶数偶数...偶数的结果一定是偶数不可能等于奇数。所以奇数直接排除。那是不是所有偶数都有优秀拆分呢是的。这基于二进制的一个基本事实任何一个正整数都可以唯一地表示成若干个2的幂次之和这就是二进制原理。对于偶数 ( n )它的二进制表示的最低位代表2^0一定是0。那么我们只需要在它的标准二进制表示中忽略掉那个不存在的2^0即1剩下的位所代表的幂次2^1, 2^2, 2^3...就构成了一个“优秀的拆分”。因为二进制表示本身保证了这些幂次是“不同的”并且我们只取 ( k \ge 1 ) 的位。举例说明( n 6 ): 二进制是110。从低到高位分别是0个(2^0)1个(2^1)值为21个(2^2)值为4。忽略(2^0)我们得到的拆分就是 4 和 2。从大到小输出4 2。( n 10 ): 二进制是1010。位信息0个11个20个41个8。拆分结果8 2。( n 2 ): 二进制是10。拆分结果2。( n 1 ): 二进制是1。它只包含一个(2^0)而(2^0)不被允许所以没有优秀拆分输出-1。至此我们完全从数学和逻辑上理解了题目。接下来的任务就是把这份理解翻译成 C 代码。3. 算法思路设计与实现方案对比理解了数学本质我们可以设计出至少两种清晰的算法思路。这两种思路本质相通但思考角度和实现细节略有不同适合不同思维习惯的选手。3.1 思路一二进制位解析法推荐这是最直接、最贴近问题本质的方法。既然我们知道了偶数的二进制表示中从第1位2^1开始的每个‘1’都对应一个合法的幂次那么算法步骤就非常清晰读入整数 ( n )。合法性判断如果 ( n ) 是奇数或 ( n \le 0 )直接输出-1并结束程序。幂次提取我们需要从大到小输出也就是从二进制的高位向低位扫描。定义一个变量power初始值设为一个足够大的2的幂次比如 ( 2^{30} ) 或 ( 2^{25} )因为题目通常约定 ( n \le 10^7 )( 2^{24} ) 约1600万已经足够覆盖。或者我们可以先找到不大于 ( n ) 的最大的2的幂次。从大到小遍历power(例如power 1073741824(2^30) 开始不断除以2)。对于每个power如果n power说明当前power这个分量存在于拆分中。那么我们就输出power并且从 ( n ) 中减去powern - power。继续检查更小的power直到power减小到 2 为止因为1不能要。输出在遍历过程中每找到一个合法的power就输出自然保证了从大到小的顺序。这个思路的优点是直观且不需要使用数组暂存结果可以边计算边输出。它清晰地模拟了“用尽可能大的2的幂次去凑原数”的贪心过程。3.2 思路二除二取余逆序法这个方法更侧重于“进制转换”的过程对于刚学会十进制转二进制的同学可能更容易理解。读入整数 ( n )进行同样的奇偶判断。转换为二进制过程用一个数组或向量bits来存储二进制位从低位到高位。不断将 ( n ) 除以2记录余数0或1直到 ( n ) 变为0。这个过程会得到完整的二进制表示包括最低位2^0。筛选与输出我们已经知道第0位对应值1是无效的。所以我们从第1位下标为1对应值2开始检查。如果bits[i] 1那么对应的幂次(1 i)即 ( 2^i ) 就是拆分的一部分。但是我们需要从大到小输出而数组存储是从低位到高位。因此我们需要逆序遍历这个数组从最高位向下遍历到第1位。输出逆序遍历时遇到值为1的位就输出对应的(1 i)。这个思路的优点是流程标准复习了二进制转换。缺点是需要额外的数组空间并且多了一个存储和逆序遍历的过程。两种思路如何选择在竞赛中思路一位解析法通常是更优解。它空间复杂度为 O(1)常数时间操作代码也更简洁。思路二作为理解过渡非常好但多了一步存储。在正式比赛追求效率和简洁的语境下我们优先采用思路一。4. 核心代码实现与逐行解读下面我们按照思路一二进制位解析法用 C 给出详细的代码实现并附上每一部分的解读。#include iostream using namespace std; int main() { int n; cin n; // 步骤1读入正整数n // 步骤2合法性判断 // 如果n是奇数或者n小于等于0虽然题目说正整数但养成判断习惯则不存在优秀拆分 if (n % 2 ! 0 || n 0) { cout -1 endl; return 0; // 直接结束程序 } // 步骤3寻找并输出拆分项 // 我们需要从最大的可能的2的幂次开始尝试 // 因为n 10^7 2^23 8388608 2^24 16777216所以从2^24开始尝试完全足够 // 这里使用 (1 24) 来计算2的24次方即左移24位 int power 1 24; // 初始化一个足够大的2的幂次 // 但是如果n本身很小比如n2power初始值远大于n我们需要先找到第一个不大于n的power // 这个循环用于将power调整到不大于n的最大2的幂次 // 如果power大于n就不断除以2右移1位 while (power n) { power 1; // 等价于 power power / 2; } // 步骤4贪心分解与输出 // 从当前power开始向下遍历所有2的幂次直到2因为1不能要 // 注意循环条件是 power 2 确保不会输出1 while (power 2) { if (n power) { // 如果当前的n包含这个power cout power ; // 输出这个幂次 n - power; // 从n中减去这个power } power 1; // 检查下一个更小的2的幂次 } // 步骤5处理输出格式可选 // 上面的循环会在每个输出后加一个空格最后会多一个尾随空格。 // 在大多数评测系统中尾随空格和换行符通常是允许的不影响答案正确性。 // 如果追求严格可以在循环中控制最后一个输出不加空格但非必须。 // cout endl; // 如果需要显式换行可以加上。但上面输出完程序结束也会换行。 return 0; }代码关键点解读if (n % 2 ! 0 || n 0)这是整个程序的“守门员”。n % 2 ! 0判断是否为奇数n 0是一个防御性判断虽然题目说是正整数但好的习惯能避免意外输入导致的问题。两者满足其一直接输出-1并返回。int power 1 24;利用位运算左移快速计算2的幂次。1 24表示将1的二进制左移24位即 ( 2^{24} )。第一个while (power n)循环这是一个预处理优化。如果直接从 ( 2^{24} ) 开始判断对于n6这种情况前很多次循环判断 ( 2^{24}, 2^{23}, ... ) 直到 ( 2^3 )都是在做无用的if (n power)判断结果都是false。这个循环快速将power下降到刚好小于等于n的2的幂次使得后续分解循环次数最少。例如n6power会快速降到4。第二个while (power 2)循环这是核心的贪心分解循环。if (n power)判断当前剩余的n是否还包含power这个分量。由于我们是从大到小尝试这保证了如果有这个分量它一定是当前剩余部分中最大的可行2的幂次。cout power ;输出。n - power;减去这个分量用剩下的值继续后续判断。power 1;无论是否使用当前power都将其减半检查下一个更小的2的幂次。 1是右移一位等价于除以2效率更高。循环条件power 2确保了不会输出1。当power变成1时循环停止。5. 常见错误与边界情况测试即使思路正确实现时也容易掉进一些坑里。下面我列举几个常见的错误点并给出测试用例。5.1 错误1遗漏对奇数1的判断这是最经典的错误。很多人只判断n % 2 ! 0就输出 -1。那么输入n1时1 % 2 ! 0成立输出 -1这看起来是对的。但是如果单独判断n1输出 -1而忘了判断其他奇数就会出错。最稳妥的就是统一用n % 2 ! 0判断所有奇数。测试用例输入1。预期输出-1。输入3。预期输出-1。输入7。预期输出-1。5.2 错误2错误地包含了2^0即1在循环中如果条件写成while (power 1)那么当power1时如果n恰好为1但n是偶数所以不会出现或者上一步n减剩为1就会输出1。这违反了“正整数次幂”的要求。必须严格保证power 2。测试用例输入2。如果循环包含1程序流程可能是power2输出2n0power1n(0) 1 不成立不输出。看起来没问题。但这是侥幸。关键在于逻辑的纯洁性。一个更明显的例子是如果你用思路二除二取余法忘记跳过最低位就会错误地把1考虑进去。5.3 错误3输出顺序错误题目要求“从大到小”输出。如果你的算法是从小到大生成幂次然后试图反转数组输出这增加了复杂度且易错。像我们上面给出的算法从大到小尝试并输出是最高效且不易错的方法。测试用例输入10。预期输出8 2。如果输出2 8就是错误的。5.4 错误4对极大幂次初始值处理不当我们的代码中使用了power 1 24和while (power n)来调整初始值。一个常见的替代写法是int power 1; while (power n) { power 1; } power 1;这个写法逻辑是先找到一个比n大的最小2的幂次然后回退一步得到不大于n的最大2的幂次。这个写法也是完全正确的而且不需要预估n的范围。两种写法都可以选择你理解最顺畅的。5.5 边界情况测试集一个好的程序应该能通过以下所有测试输入 (n)预期输出说明1-1奇数无拆分22最小的有效偶数3-1奇数64 2标准案例108 2标准案例128 4二进制11000或负数-1非法输入防御虽然题目说正整数10000000(一千万)一串从大到小的2的幂次大数测试检查循环效率和是否溢出你可以用这些测试用例来验证你的程序。6. 算法优化与扩展思考虽然这道题对于普及组来说已经解决但我们不妨再深入一步思考一下优化和相关的知识扩展。6.1 使用lowbit运算进行优化进阶在更底层的位运算中有一个著名的lowbit操作它可以直接得到一个整数二进制表示中最低位的1所代表的值。例如lowbit(6) 2因为6的二进制是110最低位的1代表2。我们可以利用lowbit从另一个角度解题不断取出当前n的lowbit如果这个lowbit不是1则它就是一个合法的拆分项2的正整数次幂。然后从n中减去这个lowbit直到n为0。lowbit的经典计算方式是n -n。这个技巧基于补码原理。#include iostream #include vector #include algorithm using namespace std; int main() { int n; cin n; if (n % 2 ! 0) { cout -1; return 0; } vectorint ans; while (n) { int lb n -n; // 计算lowbit if (lb ! 1) { // 排除掉1 ans.push_back(lb); } n - lb; // 去掉这个lowbit } // 注意lowbit是从小到大取出的所以需要逆序输出 sort(ans.rbegin(), ans.rend()); // 从大到小排序 // 或者逆序遍历 if (ans.empty()) { cout -1; } else { for (int x : ans) { cout x ; } } return 0; }这个方法的优点是概念高级直接操作二进制位。缺点是需要容器存储并排序代码不如第一种方法简洁高效。但它是一个很好的位运算练习。6.2 扩展思考如果允许使用12^0呢如果题目修改为“2的非负整数次幂”那么1就可以被使用了。此时任何正整数都存在这样的拆分其实就是它的二进制表示本身。算法会变得更简单只需要判断n 0然后像思路一一样从高到低输出每个为1的位对应的值即可。这个修改后的题目就成了一个单纯的“十进制转二进制并输出权重”的问题。6.3 与“二进制表示”知识点的关联这道题是学习“二进制”及其应用的绝佳入门题。它让你直观地看到一个数如何用2的幂次唯一表示。奇偶性在二进制中的体现最低位为1则是奇数。位运算左移、右移可以高效地计算2的幂次。贪心算法思想从大到小选取每次选能选的最大分量。掌握这道题就为后续学习更复杂的进制转换、位运算优化、状态压缩等知识点打下了坚实的基础。7. 实战调试技巧与考场策略最后分享一些在实战中解决此类题目的经验和策略。调试技巧先手算拿到题目不要急着写代码。先用手工计算几个例子比如 n6, 10, 12, 2, 1。确保你完全理解输入到输出的映射关系。边界测试写完代码后务必测试边界情况最小的偶数2、奇数1和3、一个稍大的数如100。确保程序在这些情况下行为正确。使用调试输出如果不确定循环逻辑可以在循环内添加临时输出打印power和n的当前值观察程序是如何一步步“拆分”数字的。验证输出格式检查输出是否严格符合要求是空格分隔还是换行分隔最后有没有多余的空格通常评测系统会自动忽略文末空格和换行但最好保持一致。考场策略时间分配CSP-J第一题通常比较简单建议在10-15分钟内完成读题、构思、编码和基本测试。不要因为简单而粗心。代码简洁为上竞赛评分只看输出结果是否正确不看你代码是否高深。在保证正确的前提下代码越简单、越直接越好。我们介绍的第一种方法位解析法就是简洁高效的典范。变量命名清晰使用n,power这样有意义的变量名避免使用a,b,x等单字母除非是循环计数器ij。清晰的命名有助于你在紧张时理清思路。重视初始化像power这样的变量确保在循环使用前有一个合理的初始值。仔细阅读输入输出描述确认输入是一个整数还是多个输出是空格分隔还是换行分隔。这道题是单个整数输出空格分隔的数字。这道“优秀的拆分”就像一把钥匙帮你打开了用程序语言描述数学逻辑的大门。它考察的基础知识非常纯粹但正是这些纯粹的基础构成了解决更复杂问题的基石。希望这篇详细的拆解能让你不仅学会解这一道题更能体会到算法设计中“理解题意、转化问题、设计步骤、代码实现、测试完善”的完整流程。在之后的练习中不妨多试试用不同的思路去解决同一道题这种思维训练对提升编程能力大有裨益。