题解(带思路)
2026-03-31 19:30:24
发布于:浙江
0阅读
0回复
0点赞
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
// 奇数直接输出-1,因为奇数无法拆分为多个偶数之和
if (n % 2 != 0) {
cout << -1 << endl;
return 0;
}
// 找到最高位的2的幂次
int p = 1; // p表示当前2的幂次,初始为2^0=1
// 循环找到不大于n的最大2的幂次(至少为2^1=2)
while (p * 2 <= n) {
p *= 2;
}
bool f = true; // f标记是否是第一个输出的数,控制空格输出
int t = n; // t保存剩余需要拆分的数值
// 从最高位到最低位遍历所有2的幂次(最小为2^1=2)
while (p >= 2) {
if (t >= p) { // 如果剩余数值大于等于当前幂次
if (!f) { // 不是第一个数,先输出空格
cout << " ";
}
cout << p; // 输出当前幂次
t -= p; // 剩余数值减去当前幂次
f = false; // 标记已输出过第一个数
}
p /= 2; // 幂次减半,处理下一个更低的幂次
}
cout << endl; // 输出换行符
return 0;
}
问题深度解析
核心定理推导
存在优秀拆分的充要条件:一个正整数n存在优秀拆分,当且仅当n是偶数。
证明:
必要性:所有2的正整数次幂都是偶数,偶数之和必为偶数,故奇数无法拆分
充分性:任何偶数都可通过二进制表示转换为不同2的幂次之和(二进制中1的位置对应2的幂次)
拆分唯一性证明
优秀拆分方案是唯一的,因为每个偶数的二进制表示是唯一的,对应唯一的2的不同幂次组合。
这里空空如也




有帮助,赞一个