企业官网建设流程全解析

2020年的信息学入门级认证，第一道题叫《优秀的拆分》。这题在考场上给不少选手来了个下马威——有人看完题目下意识往深搜上想，有人直接套动态规划，还有人用贪心试了半天样例，结果交上去只过了一两个点。实际上这道题既不需要搜索，也不需要DP，它考察的是最基础也最容易忽略的“二进制表示”。把一个正整数拆成若干个互不相同的2的正整数次幂之和，这件事本质上就是“把这个数用二进制展开”。想通这一点，整道题就是三五行代码的事；想不通，就会在枚举和回溯里绕很久。这篇文章我从头到尾把题目拆一遍，讲清楚为什么它和二进制绑定在一起，然后给出可以直接照抄的完整代码，再分享一些我在实际写题和调试过程中踩过的坑。

1. 题目到底在问什么

1.1 复述题目与输入输出规则

简单说，题目给了你一个正整数 n，要求判断它能不能被拆成若干个“互不相同的 2 的正整数次幂”之和。这里的限定词有两个：第一个是“互不相同”，也就是说如果拆出了 2，就不能再拆出另一个 2；第二个是“正整数次幂”，意味着允许出现的底数只有 2 的 1 次方、2 次方、3 次方……也就是 2、4、8、16 这些数，注意这里没有 1，因为 2 的 0 次方不是正整数次幂。

如果能拆，就按某种顺序输出拆分出的这些数；如果不能拆，输出 -1。题目给的两个样例非常典型：输入 6，输出 4 2，因为 6 = 4 + 2；输入 7，输出 -1，因为 7 无论怎么试，都凑不出若干个互不相同的 2 的正整数次幂。

第一次看到这个题目，很多人会自然地去想：那我用深度优先搜索枚举所有组合，把不超过 n 的 2 的幂全部拿出来，然后挨个试能不能凑成 n。这个思路本身没错，但放在第一题的位置上，显然不是在考搜索。

1.2 为什么说“优秀的拆分”不是普通拆分

普通的“整数拆分”是一个计数问题，比如把 5 拆成若干个正整数之和有多少种拆法。那个问题看起来简单，实际上涉及到生成函数、递推、动态规划，复杂度并不低。但“优秀的拆分”完全不是一个量级，因为它把每一项都限制成了互不相同的 2 的幂。

一旦做了这个限制，事情立刻就变得“唯一”了起来。你可以试着从最大的 2 的幂开始往小里选，也可以从最小的开始往上凑，最后你会发现：对于任何一个正整数 n，它的二进制表示是唯一的，而二进制表示恰好就是“若干互不相同的 2 的幂相加”。换句话说，这个世界里本来就不存在多种优秀拆分方案，除非 n 根本没法拆。

这就引出了整道题的核心：判断能否拆分，等价于判断 n 的二进制表示中是否包含 2 的 0 次方这一位，也就是最低位是否为 1。如果最低位是 1，说明 n 是奇数，那它一定包含一个“1”的因子，但这个“1”是不允许出现的，所以直接输出 -1；如果最低位是 0，说明 n 是偶数，那就把二进制里所有为 1 的位提取出来，这些位对应的权值就是你要输出的拆分结果。

2. 从暴力枚举到二进制：思维转换的过程

2.1 第一反应为什么是暴力

我刚拿到题时，第一反应也是枚举。毕竟“拆分”这个词很具有迷惑性，会让人联想到背包、回溯、组合数学。具体来说，可以先预处理出所有不超过 n 的 2 的正整数次幂，得到一个类似 [2, 4, 8, 16, ...] 的数组，然后从这些数里选若干个，使它们的和刚好等于 n。因为每个数只能用一次，这确实就是一个 0/1 背包或者一个经典的回溯问题。

对于小数据来说，这样做完全可行。比如 n = 100，不超过它的 2 的正整数次幂只有 2、4、8、16、32、64 这六个数，枚举所有子集也只有 2 的 6 次方也就是 64 种情况，很快就能出结果。问题在于，CSP-J 的数据范围往往给到 10 的 9 次方，这个时候不超过 n 的 2 的正整数次幂大约有 30 个，枚举子集的最坏情况是 2 的 30 次方，也就是超过 10 亿种组合，显然不可接受。

所以这道题的第一重考验就是：你能不能及时从“枚举”跳到“数学”。如果跳不出来，第一题就会消耗大量时间，而且还不一定对。

2.2 二进制表示为什么是最优解

任何正整数 n 都可以写成唯一的二进制形式，比如 13 等于 8 + 4 + 1，二进制就是 1101。这里的 8、4、1 正好分别对应二进制的第 3 位、第 2 位和第 0 位。如果题目允许 2 的 0 次幂，那 13 的优秀拆分就是 8 + 4 + 1，直接输出 8 4 1 即可。

但题目不允许 1 出现，所以当 n 是奇数时，二进制最低位一定是 1，这个 1 无论如何也消不掉，因为其他所有位都是偶数，只有最低位贡献了奇偶性。一个奇数减去若干个偶数依然是奇数，永远到不了 1，所以奇数一定无解。反过来，如果 n 是偶数，最低位是 0，那么它从第 1 位开始往上取，每一位要么是 0 要么是 1，把是 1 的那些位对应的权值全部加起来，刚好等于 n，且每一项都大于等于 2，完美满足题目要求。

这里面的数学直觉可以类比成砝码称重：假设你有一套砝码，分别是 1 克、2 克、4 克、8 克……每个砝码只有一个，那么你最多能称出多少种重量？答案是这些砝码能表示从 1 到它们总和之间的所有整数，而且表示方式唯一。原因很简单，二进制每一位只有选或不选两种状态，这正好对应了一个砝码的取或不取。回到题目，它相当于把 1 克砝码从套装里去掉了，于是所有需要用到 1 克砝码的重量都没法称，而那些不需要 1 克砝码的重量，依然有且仅有一种表示方式。

2.3 一个容易混淆的细节：n 是 2 的幂怎么办

如果 n 本身就是 2 的正整数次幂，比如 4、16、64，那么它的二进制只有一个位是 1，优秀拆分就是它自己。比如输入 4，输出 4；输入 16，输出 16。这个情况在代码里不需要特殊处理，只要按位提取，自然只会输出一个数。

但如果输入 2，输出也是 2，因为 2 = 2，单独一项就是合法拆分。这里要特别提醒，千万不要因为“拆分”两个字就认为至少要有两项，单项也是合法的。原题并没有要求拆成两项以上，所以这一点很多人在写代码时容易产生自我怀疑，其实不需要。

3. 解题代码的三种实现方式

3.1 解法一：按二进制位从低到高收集，再倒序输出

这是最直白的做法。先用 n & 1 判断最低位是否为 1，如果是就直接输出 -1 并结束。如果不是，就循环从 1 到 30 枚举二进制位数，检查第 i 位是否为 1。如果为 1，就把 2 的 i 次方存下来。

之所以要存下来再倒序输出，是因为题目样例给出的是从大到小输出，也就是从高位到低位。举例来说，n = 10 的二进制是 1010，第 1 位和第 3 位是 1，按低位到高位收集会得到 [2, 8]，倒序后就是 [8, 2]，输出 8 2。

#include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; if (n & 1) { cout << -1 << endl; return 0; } vector<int> ans; for (int i = 1; i <= 30; i++) { int cur = 1 << i; if (n & cur) { ans.push_back(cur); } } for (int i = ans.size() - 1; i >= 0; i--) { cout << ans[i]; if (i > 0) cout << " "; } cout << endl; return 0; }

这里循环上限定到 30 是因为 int 最多能表示 2 的 31 次方减 1，而常规数据范围是 10 的 9 次方，2 的 30 次方约等于 1.07 乘 10 的 9 次方，已经覆盖住了。如果你担心数据范围更大，可以把 int 换成 long long，循环上限设到 60，本质上没有区别。

3.2 解法二：用 lowbit 提取每一个存在的位

lowbit 是树状数组里的老朋友，公式是 n & (-n)，它返回的是 n 的二进制表示中最低位的 1 所对应的权值。举个例子，n = 12，二进制是 1100，lowbit(12) = 4。这一步提取出来的数本身就是 2 的幂，且因为 n 是偶数，最低位至少也是 2，不会出现 1。

利用 lowbit 可以写一个循环，每次把当前最低位的 1 提取出来，然后从 n 中减掉或者异或掉，直到 n 变成 0。这样收集到的所有数就是 n 的所有二进制位对应的权值。由于 lowbit 是从低位往高位提取的，收集顺序是升序，最后用 sort 降序输出即可。

#include <bits/stdc++.h> using namespace std; int main() { long long n; cin >> n; if (n & 1) { cout << -1 << endl; return 0; } vector<long long> ans; while (n) { long long low = n & (-n); ans.push_back(low); n ^= low; // 也可以用 n -= low } sort(ans.begin(), ans.end(), greater<long long>()); for (int i = 0; i < (int)ans.size(); i++) { if (i) cout << ' '; cout << ans[i]; } cout << endl; return 0; }

第二种写法比起第一种更优雅，也能很好地展示你对位运算的理解。不过我要提醒一个细节：n ^= low 和 n -= low 在大多数情况下是等价的，因为 low 一定是当前 n 的二进制位中的某个 1，异或掉它和减掉它的效果一致。对于这道题，两者没有任何区别，但如果是其他需要维护低位特征的题目，要注意区分。

3.3 解法三：Python 一行流

如果你用的是 Python，代码可以更短。先读入 n，判断奇偶，然后从第 1 位枚举到第 30 位，用右移看当前位是不是 1，把对应的 1 << i 加到列表里，最后反转输出。

n = int(input()) if n & 1: print(-1) else: ans = [] for i in range(1, 31): if (n >> i) & 1: ans.append(1 << i) print(" ".join(map(str, reversed(ans))))

这里有一个 Python 初学者非常容易踩的坑：n & 1不能写成n & 1 == 0，因为在 Python 中比较运算符优先级低于位运算符，所以n & 1 == 0会被解析成n & (1 == 0)，理论上会得到 0，但这个写法非常容易造成困扰。最稳妥的方式是加上括号，写成(n & 1) == 0，或者直接判断if n & 1:。

3.4 输出格式的细节处理

这题虽然简单，输出格式反而可能成为失分点。样例输出 4 2，两个数之间有空格，行末没有多余空格，最后有换行。有的同学在循环里无脑输出cout << cur << " "，结果最后一个数后面也跟了一个空格。对于 strict 判题机，这种多余的末位空格往往会被判成 Presentation Error，虽然不算全错，但会影响心情和最终分数。

比较稳妥的做法有两种：一种是把答案存进数组，打印时判断当前是不是最后一个元素，不是才输出空格；另一种是用标志位控制。上面的代码已经写了第一种方式，可以直接照搬。

4. 考场上最常见的扣分点与排查技巧

4.1 没有判断奇数直接输出所有二进制位

这是最容易犯的错误。很多选手写出了按位提取的代码，但忘记在最前面判断 n 是否为奇数。如果 n = 7，二进制是 111，按位提取会得到 4、2、1，然后输出 4 2 1，看起来像模像样，但 1 不是 2 的正整数次幂，整个方案非法，会被判错。

我见过有同学说：那我直接把 1 过滤掉不就行了吗？过滤之后 7 变成了 4 + 2 = 6，和 7 不相等，这显然不行。所以正确的做法不是过滤，而是在开头直接把所有奇数排除掉。判断奇数用n & 1即可，一个位运算搞定，不要用n % 2 == 1，虽然效果一样，但在信息学竞赛里位运算更显功底，也更快。

4.2 把 1 左移 31 位导致溢出

很多选手在枚举二进制位时，会顺手写1 << i，用 int 存储。如果 i 到了 31，1 << 31已经超出了 int 能表示的正整数范围，会变成负数。之后再用这个负数去和 n 做按位与，结果就会出现各种奇怪的数字，甚至导致死循环。

解决办法很简单：枚举范围控制在 1 到 30，或者把所有变量声明成 long long，又或者一开始就用 64 位整数来存1LL << i。在竞赛环境里，宁可多花一点空间也要保证不溢出，这是写任何位运算题目的铁律。

另外还有一个优先级问题：if (n & (1 << i) != 0)这段代码里，!=的优先级高于&，所以它会被解析成n & ((1 << i) != 0)。虽然最终结果未必错，但这种写法极易引起逻辑混乱。正确写法是if ((n & (1 << i)) != 0)，括号一定要打全。

4.3 暴力深搜在小数据能过，大数据超时

如果你在考场上真的用回溯去枚举组合，那么 n 比较小的时候确实可以过，比如 n 是两位数甚至三位数。但一旦 n 到了 10 的 7 次方以上，枚举的复杂度会迅速飙升。不要觉得“反正 30 个 2 的幂，组合不算多”，30 个元素的所有子集数量是 2 的 30 次方，约等于 10 亿。即便用剪枝，最坏情况下依然要遍历大量无用的分支。

这道题的正解复杂度是 O(log n)，也就是只需要扫描 n 的二进制位数。第一题考这样的复杂度，本质上是想告诉你：做题之前先想想数学结构，再用算法实现。而不是上来就套模板。

4.4 忽视输出顺序导致样例都对但判题不过

有些同学会好奇：我只输出从小到大的顺序，比如说 2 4，是不是也算对？如果题目明确说明了输出顺序，那么必须严格遵守。从我看到的题目版本和相关题解来看，绝大多数题解都采用从大到小输出，也就是先输出最高位对应的幂。所以这里建议直接采用从大到小输出，不要临场自由发挥。

如果实在不确定题目要求，你可以做一个保险动作：把结果存入 vector，然后统一 sort 成降序再输出。这样至少能匹配题目的常见输出格式。还有一种情况是题面没有明确规定顺序，但判题数据里做了固定顺序匹配，这时候按样例格式走就是最稳的。

5. 二进制思想在信息学竞赛中的延伸应用

5.1 判断一个数是不是 2 的幂

掌握了这道题之后，你会立刻发现很多相关的位运算技巧都可以串起来。比如判断一个数 n 是不是 2 的正整数次幂，传统写法是循环除以 2，看最后是否等于 1。位运算的写法只需要一行：n > 0 && (n & (n - 1)) == 0。原理是 2 的幂的二进制表示只有一个 1，减 1 之后会把它变成 0，并让后面的低位全部变成 1，两者按位与的结果必然为 0。这个技巧在很多题目里都能直接使用。

5.2 快速幂与指数二进制化

快速幂算法的本质就是把指数展开成二进制，根据每一位决定是否乘上对应的幂次。比如计算 a 的 13 次方，13 的二进制是 1101，也就是 8 + 4 + 1，那么 a 的 13 次方就等于 a 的 8 次方乘 a 的 4 次方乘 a 的 1 次方。每一步循环里不断把底数平方，同时检查指数的当前位是否为 1，决定是否累乘进答案。这个思路和“优秀的拆分”完全同构，只不过一个是拆指数，一个是拆底数。

5.3 树状数组的 lowbit 思想

树状数组里的核心操作也是 lowbit。不管是单点更新还是区间查询，都需要反复用到i += lowbit(i)或i -= lowbit(i)来在虚拟树上跳跃。很多初学者理解不了树状数组为什么能这么快，其实就是因为它借助了二进制最低位的规律，把区间划分成了若干个与二进制相关的块。如果你今天能把 lowbit 在“优秀的拆分”里用得很熟练，后面学树状数组时会轻松很多。

5.4 状态压缩与子集枚举

在搜索题和状态压缩 DP 题里，一个 int 的每一位可以代表某个物品选或不选。比如 0 到 2 的 n 次方减 1 之间的每个整数，都对应了一种子集方案。枚举子集的标准写法是for (int sub = mask; sub; sub = (sub - 1) & mask)，这个写法也依赖了对二进制位的理解。所以说，这道看似简单的第一题，其实是后续很多高级算法的基础。

5.5 统计二进制中 1 的个数

统计一个整数二进制表示中有多少个 1，暴力的做法是逐位判断，位运算的做法是不断用 lowbit 消掉最低位的 1。这个技巧与“优秀的拆分”中的循环提取如出一辙。很多大题里需要快速统计状态数量，提前把位数统计函数写好，可以在解题时省下不少时间。

6. 给备考者的一些实实在在的建议

6.1 拿到送分题不要过度紧张

第一题在整场考试里的定位就是“送分题”。它的存在不是为了刁难你，而是为了让你平稳进入状态。因此当你读完题发现它是一道位运算题时，不要怀疑自己是不是想简单了，更不要为了“显得有技术含量”而强行套一个复杂算法。我在实际练习中见过一些同学，明明已经想到了二进制解法，却因为觉得“这么简单是不是漏了什么”而开始自我怀疑，最后绕回搜索，白白浪费二十分钟。

6.2 养成手推样例和边界数据的习惯

写完代码之后，一定不要只测题面给的样例。你要自己多测几组数据，比如输入 2，应该输出 2；输入 1，应该输出 -1；输入 8，应该输出 8；输入 10，应该输出 8 2；输入 12，应该输出 8 4；输入 14，应该输出 8 4 2。把这些小数据在草稿纸上手算一遍，再和程序输出对比。边界条件往往是隐藏的扣分点，比如 1、2、最大数据，都值得单独测试一遍。

6.3 把位运算模板整理进笔记

我建议你准备一个专门的笔记页，把常见的位运算技巧全部写下来，包括判断奇偶、取 lowbit、消去最低位的 1、判断 2 的幂、统计 1 的个数、枚举子集、快速幂核心步骤等。每次做题遇到位运算，就回到这一页对照一下。时间一长，这些操作会变成你的条件反射。到那时再看到类似题，你就能直接读出它的考点，而不是在那里从零开始推理。

6.4 赛后复盘比盲目刷题更重要

很多同学刷题只求 AC，AC 之后就再也不看这道题了。其实赛后复盘才是提升的关键。做完《优秀的拆分》，你可以回头想一想：自己在哪个环节卡住了？是因为没有往二进制方向想，还是因为输出格式踩了坑？这些反思比多刷十道同样难度的题更有价值。信息学竞赛的知识点看似很多，但实际上很多都是相通的，建立起知识网络之后，考场上遇到新题才不会慌。

从这道题往后看，你会发现信息学竞赛中很多“简单题”都不只是简单考查代码能力，而是在考查数学直觉。二进制、奇偶性、位运算这些东西听起来基础，但它们几乎渗透在从入门到省选的每一个角落。我自己最初写这道题时也走了弯路，第一版写了个 DFS，样例能过，一提交就超时；改成按位提取后，整个思路一下就清晰了。后来我带过的学员里，几乎每个人都经历过这个“顿悟瞬间”。

最后再分享一个小技巧：以后看到“互不相同”“若干个”“2 的幂”“正整数次幂”这些词凑在一起时，第一反应就应该是二进制。一个数能不能被拆成互不相同的 2 的幂之和，判断标准就是它的二进制表示里有没有不允许出现的位；能拆的话，拆出的每一项就是二进制里那些为 1 的位本身。这道题的名字叫“优秀的拆分”，真正优秀的地方不在拆分，而在于你看穿它和二进制是一回事的那个瞬间。