题目题解

问题理解

给定 $n$ 和 $k$，判断能否将 $n$ 表示为恰好 $k$ 个 2 的幂之和，并输出一种方案。

---

第一步：最小可能项数

将 $n$ 写成二进制，每个为 $1$ 的位对应一个 2 的幂。
例如 $n = 13 = 1101_2 = 8 + 4 + 1$，需要 $3$ 项。
因此，最小项数等于 $n$ 的二进制表示中 $1$ 的个数，记作 $\text{popcount}(n)$。

若 $k < \text{popcount}(n)$，则不可能，输出 "NO"。

---

第二步：增加项数

如果 $k$ 大于最小项数，我们可以将某个大于 $1$ 的项 $x$ 拆成两个 $\frac{x}{2}$，这样项数增加 $1$。
例如：$4 \to 2 + 2$，项数从 $1$ 变 $2$。

重复此过程，直到项数达到 $k$。

---

第三步：可行性条件

由于每次拆分将一项变成两项，项数增加 $1$，最多可将所有项拆成 $1$（不能再拆）。
因此，最大可能项数就是 $n$（全部拆成 $1$）。

所以，$k$ 必须满足：

$$\text{popcount}(n) \le k \le n.$$

若 $k$ 在此范围内，则一定可行。

---

第四步：构造方法

1. 将 $n$ 的二进制分解为若干 2 的幂，存入一个计数器 ans，同时将大于 $1$ 的项放入队列 q。
2. 若当前项数 cnt 小于 $k$，则从队列中取出一个大于 $1$ 的项 $z$，将其拆成两个 $z/2$：
   • 减少 $z$ 的计数，增加 $z/2$ 的计数。
   • 若 $z/2 > 1$，将两个 $z/2$ 都加入队列（以便后续继续拆分）。
   • 项数 cnt 增加 $1$。
3. 重复直到 cnt == k 或队列为空。
4. 若最终 cnt < k，则不可能（但根据条件应已判断），输出 "NO"。
5. 否则输出 "YES" 和所有项。

---

第五步：时间复杂度

• 二进制分解：$O(\log n)$。
• 拆分操作最多 $O(k)$ 次。
• 总复杂度 $O(k + \log n)$，满足 $k \le 2\times 10^5$。

---

代码实现

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

int main() {
    int n, k;
    cin >> n >> k;
    
    map<int, int> ans;
    queue<int> q;
    
    // 二进制分解
    for (int i = 0; i <= 30; i++) {
        if (n >> i & 1) {
            int val = 1 << i;
            if (val > 1) q.push(val);
            ans[val]++;
        }
    }
    
    int cnt = ans.size();
    if (cnt > k) {
        cout << "NO\n";
        return 0;
    }
    
    while (cnt < k && !q.empty()) {
        int z = q.front();
        q.pop();
        ans[z]--;
        ans[z / 2] += 2;
        if (z / 2 > 1) {
            q.push(z / 2);
            q.push(z / 2);
        }
        cnt++;
    }
    
    if (cnt < k) {
        cout << "NO\n";
        return 0;
    }
    
    cout << "YES\n";
    for (auto [val, count] : ans) {
        for (int i = 0; i < count; i++) {
            cout << val << " ";
        }
    }
    cout << "\n";
    
    return 0;
}

---

验证样例

输入：

9 4

输出：

YES
1 2 2 4

（顺序可能不同，但满足要求）

输入：

8 1

输出：

YES
8

输入：

5 1

输出：

NO

输入：

3 7

输出：

NO

与题目输出一致。

---

总结

本题的关键在于：

1. 最小项数为 $\text{popcount}(n)$，最大项数为 $n$。
2. 通过不断拆分大于 $1$ 的项，可以增加项数。
3. 用队列维护可拆分的项，贪心拆分直到达到 $k$。