[CSP-J 2020] 优秀的拆分

GitHub跳转原题关系图返回列表

把 n 看成二进制位权之和；若 n 为奇数就必然需要用到 1 无解，否则直接按二进制拆成若干不同的 2 的幂。

OJ: luogu

题目 ID: P7071

难度:普及-

标签:数学二进制构造

日期: 2026-06-18 22:56

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结

题意

给出一个正整数 n，要求判断它能否拆成若干个互不相同的 2 的正整数次幂之和。
如果能，输出一种拆分方案；否则输出 -1。

思路

先看一个可以直接验证想法的朴素解：

先把所有不超过 n 的 2 的幂列出来，再用 DFS 枚举选或不选，看能不能拼出 n。

cpp
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> pw;
vector<int> ans;
vector<int> path;
bool found = false;

void dfs(int idx, int sum) {
    if (found) {
        return;
    }
    if (sum == n) {
        ans = path;
        found = true;
        return;
    }
    if (sum > n || idx < 0) {
        return;
    }

    path.push_back(pw[idx]);
    dfs(idx - 1, sum + pw[idx]);
    path.pop_back();
    dfs(idx - 1, sum);
}

void solve() {
    for (int x = 2; x <= n; x <<= 1) {
        pw.push_back(x);
    }

    dfs((int)pw.size() - 1, 0);
    if (!found) {
        cout << -1 << '\n';
        return;
    }

    for (int i = 0; i < (int)ans.size(); i++) {
        if (i) {
            cout << ' ';
        }
        cout << ans[i];
    }
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    solve();

    return 0;
}

下面是另一种「01 序列」风格的暴力写法。它按每个 2 的幂依次决定选或不选，递归生成完整选择后，叶子节点统一检查和是否等于 n，再保存可行方案：

另一种暴力写法：01 序列
cpp
// brute_01_style.cpp：01 序列风格暴力，按每个 2 的幂决定选或不选。
#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> power_list;
vector<int> choose_power; // choose_power[i] = 0/1，表示第 i 个 2 的幂不选/选
vector<int> answer;
bool found;

int calc_sum() {
    int sum = 0;
    for (int i = 0; i < (int)power_list.size(); i++) {
        if (choose_power[i] == 1) sum += power_list[i];
    }
    return sum;
}

void save_answer() {
    answer.clear();
    for (int i = (int)power_list.size() - 1; i >= 0; i--) {
        if (choose_power[i] == 1) {
            answer.push_back(power_list[i]);
        }
    }
}

void dfs_choose(int dep) {
    if (dep == (int)power_list.size()) {
        if (!found && calc_sum() == n) {
            save_answer();
            found = true;
        }
        return;
    }

    // 第 dep 个 2 的幂的 01 选择：0 不选，1 选。
    for (int i = 0; i <= 1; i++) {
        choose_power[dep] = i;
        dfs_choose(dep + 1);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;

    if (n % 2 == 1) {
        cout << -1 << '\n';
        return 0;
    }

    for (int x = 2; x <= n; x <<= 1) {
        power_list.push_back(x);
    }

    found = false;
    choose_power.assign(power_list.size(), 0);
    dfs_choose(0);

    if (!found) {
        cout << -1 << '\n';
        return 0;
    }

    for (int i = 0; i < (int)answer.size(); i++) {
        if (i > 0) {
            cout << ' ';
        }
        cout << answer[i];
    }
    cout << '\n';

    return 0;
}

这个暴力做法能帮助理解题目，但真正的关键规律其实非常直接：

  • 不同的 2 的幂之和，本质上就是一个数的二进制展开。

例如：

n 二进制 对应拆分
6 110 4 + 2
7 111 需要 4 + 2 + 1，无解
26 11010 16 + 8 + 2

表格第三列说明：
如果最低位也是 1，那就会被迫用到数字 1。
但 1 = 2^0 不是 2 的正整数次幂，所以这种情况不合法。

于是结论就很清楚了：

  1. 如果 n 是奇数，输出 -1
  2. 如果 n 是偶数，直接把二进制里所有为 1 的位对应的权值输出出来

按从大到小输出，就和样例风格一致。

代码

cpp
#include <bits/stdc++.h>
using namespace std;

int n;

void solve() {
    if (n % 2 == 1) {
        cout << -1 << '\n';
        return;
    }

    bool first = true;
    for (int p = 1 << 23; p >= 2; p >>= 1) {
        if (n >= p) {
            n -= p;
            if (!first) {
                cout << ' ';
            }
            first = false;
            cout << p;
        }
    }
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    solve();

    return 0;
}

复杂度

时间复杂度是 O(logn)O(log n)，空间复杂度是 O(1)O(1)。

总结

这题表面像拆分搜索题，实际上是一个标准的二进制构造题。

核心只要记住一句话：

  • 偶数可以直接按二进制拆；
  • 奇数一定会需要用到 1，因此无解。