6631.[CSP-J2020] 优秀的拆分

算法思路

1. 问题分析

题目要求将正整数 $n$ 拆分为不同的 $2$ 的正整数次幂（即 $2^k$，$k≥1$）。关键点：

• 拆分不能包含 $2^0=1$（因为要求正整数次幂）
• 奇数一定无法拆分（其二进制最低位为 1，必然包含 $2^0$）
• 偶数的拆分方案对应其二进制表示中的 $1$ 位（排除 $2^0$ 位）
• 本质是位运算问题，属于二进制分解的变体

2. 解决策略

1. 边界处理：奇数直接返回 -1
2. 二进制分解：
   • 从低位到高位扫描 $n$ 的二进制位
   • 当某位为 1 时，记录对应的 $2^k$ 值（$k≥1$）
3. 结果输出：
   • 将记录的幂值从大到小排序输出
   • 注意跳过 $k=0$ 的情况（由偶数保证自然跳过）

3. 复杂度分析

• 时间复杂度：$O(\log n)$
  • 需要扫描 $n$ 的二进制表示的每一位
  • 最大位数 $\log_2(10^7) \approx 24$，可视为常数时间
• 空间复杂度：$O(\log n)$
  • 存储二进制分解结果，最坏情况有 $O(\log n)$ 个拆分项

代码实现

C++解法

cpp
复制
1#include <iostream>
2#include <cstdio>
3using namespace std;
4
5int main() {
6    int n;
7    scanf("%d", &n);
8    
9    // 奇数不存在优秀拆分（必然包含2^0）
10    if (n % 2 == 1) {
11        printf("-1");
12        return 0;
13    }
14    
15    int result[30] = {0}; // 存储拆分结果（10<sup>7<2</sup>24）
16    int count = 0;        // 有效结果计数器
17    
18    // 从低到高扫描二进制位
19    int pos = 0;          // 当前位索引
20    while (n) {
21        if (n & 1) {      // 当前位为1
22            int value = 1 << pos; // 计算2^pos
23            if (pos > 0) {       // 跳过2^0
24                result[count++] = value;
25            }
26        }
27        pos++;
28        n >>= 1;          // 右移处理下一位
29    }
30    
31    // 从大到小输出结果
32    for (int i = count - 1; i >= 0; i--) {
33        printf("%d", result[i]);
34        if (i > 0) printf(" ");
35    }
36    
37    return 0;
38}

代码解释：

1. 边界处理：第 9-12 行直接处理奇数情况
2. 二进制分解：
   • 第 17 行：n & 1 检测当前最低位是否为 1
   • 第 18 行：1 << pos 计算 $2^{\text{pos}}$ 的值
   • 第 19 行：跳过 $k=0$（pos>0 保证只取正整数次幂）
3. 结果输出：
   • 第 27 行：逆序遍历数组实现从大到小输出
   • 第 28 行：处理空格分隔符

Python3解法

python
复制
1import sys
2
3def main():
4    n = int(sys.stdin.readline().strip())
5    
6    # 奇数直接返回-1
7    if n % 2 == 1:
8        print("-1")
9        return
10    
11    res = []       # 存储拆分结果
12    pos = 0        # 当前位索引
13    
14    # 从低到高扫描二进制位
15    while n:
16        if n & 1:  # 当前位为1
17            value = 1 << pos  # 计算2^pos
18            if pos > 0:       # 跳过2^0
19                res.append(value)
20        pos += 1
21        n //= 2    # 等价于n >>= 1
22    
23    # 逆序输出（从大到小）
24    if res:
25        print(" ".join(map(str, reversed(res))))
26    else:  # 理论不会触发（n>=2的偶数至少含1个有效位）
27        print("-1")
28
29if __name__ == "__main__":
30    main()

代码解释：

1. 与C++差异：
   • 动态列表替代固定数组
   • reversed() 替代显式逆序循环
   • 整数除法 //2 替代位右移（效果相同）
2. 关键逻辑：
   • 第 12 行：n & 1 进行位检测
   • 第 13 行：1 << pos 计算幂值
   • 第 17 行：n //= 2 移除已处理位
3. Python特性：
   • map(str, reversed(res)) 快速生成逆序字符串
   • 动态列表自动管理内存

复杂度对比

选择建议：

1. 竞赛场景：优先选择 C++
   • 位运算直接编译为 CPU 指令
   • 静态数组避免动态内存分配开销
2. 开发效率：选择 Python
   • 动态列表简化代码逻辑
   • 内置逆序操作减少编码错误
3. 特殊注意：当 $n=2$ 时
   • 两种实现均输出 $2$（$2=2^1$）
   • 验证了边界情况处理正确性