喵哈~ 主人们好呀！今天由本猫娘来给大家讲解一道非常有趣的题目，关于如何用二进制的魔法来拆分数字，感觉就像在玩积木一样呢，喵~ ✨

这道题是 Codeforces 1095C - Powers Of Two。

题目大意

题目会给我们两个正整数 n 和 k。我们的任务是，把 n 表示成正好 k 个2的幂次的和。

这里的“2的幂次”就是像 1, 2, 4, 8, 16, ... 这些可以写成 2^y 形式的数字（y 是非负整数）。

如果能找到这样 k 个数，我们就输出 "YES"，然后把这 k 个数打印出来。如果找不到，那就只好遗憾地输出 "NO" 啦。

举个例子，喵~

• 输入 n=9, k=4
• 我们可以把 9 分解成 4 + 2 + 2 + 1。这四个数（4, 2, 2, 1）都是2的幂次，它们的和是9，数量也正好是4。所以是可行的！
• 输出: YES 和 1 2 2 4

再看一个例子：

• 输入 n=3, k=7
• 3 最多只能分解成 1 + 1 + 1，也就是3个2的幂次。想要凑出7个是绝对不可能的啦！
• 输出: NO

解题思路与方法

这道题的核心思想其实和二进制息息相关哦，喵~ 任何一个正整数 n，都有一个唯一的二进制表示法。

比如说 n=9，它的二进制是 1001。这其实就告诉我们一个秘密：9 = 1 * 2^3 + 0 * 2^2 + 0 * 2^1 + 1 * 2^0 = 8 + 1。

看！这就是一种把 9 表示成2的幂次之和的方法，而且是用最少项数的方法！

1. 项数的限制范围

• 最少需要多少项 (k的下限)？ 就像上面说的，直接用 n 的二进制表示法，有多少个 1，就需要多少个项。比如 9 (二进制1001) 最少需要2项 (8 和 1)。所以，k 必须大于等于 n 的二进制表示中 1 的个数。这个个数我们可以用一个神奇的函数 __builtin_popcount(n) 来快速得到，超方便的！

• 最多能有多少项 (k的上限)？ 最“碎”的分解方法，就是把 n 分解成 n 个 1 相加。因为 1 也是 2^0，是2的幂次，所以我们最多可以有 n 个项。所以，k 必须小于等于 n。

• 无解判断！ 结合上面两点，如果题目给的 k 小于 __builtin_popcount(n) 或者大于 n，那肯定是没救了，喵~ 直接输出 "NO" 就可以啦。

2. 贪心构造答案

如果 k 恰好在 [__builtin_popcount(n), n] 这个范围里，那么就一定有解！我们的策略是这样的：

1. 从最少项开始：我们先从 n 的二进制表示开始，这是我们的基础方案。比如 n=9，我们手里有 {8, 1}。

2. 如何增加项数：我们现在的项数是 popcount(n)，但目标是 k 项。怎么在不改变总和的情况下增加项数呢？很简单！我们可以把一个大项拆成两个小项！

   • 4 可以拆成 2 + 2
   • 8 可以拆成 4 + 4
   • 2^i (只要 i>0) 都可以拆成 2^(i-1) + 2^(i-1) 每一次这样的拆分，总和不变，但项数会增加 1！

3. 贪心策略：我们需要增加 k - popcount(n) 个项，所以我们就要进行这么多次拆分。那每次拆哪个数呢？为了让过程简单可控，我们采用贪心的策略：每次都拆分当前手里最大的那个数。

   • 比如，我们有 {8, 1}，需要增加项数。我们拆 8，得到 {4, 4, 1}。项数从2变成了3。
   • 如果还需要增加，我们再拆一个 4，得到 {4, 2, 2, 1}。项数从3变成了4。
   • 我们就这样一直从大到小拆分，直到项数正好等于 k 为止！因为我们已经判断过 k 是可行的，所以这个过程一定能成功。

算法步骤总结

1. 计算 n 的二进制中1的个数 set_bits。
2. 判断 k 是否在 [set_bits, n] 范围内，如果不是，输出 "NO"。
3. 如果是，输出 "YES"。然后用一个数组 counts 来记录我们手里每种2的幂次的数量。counts[i] 表示 2^i 的数量。
4. 先根据 n 的二进制表示，初始化 counts 数组。
5. 从大到小遍历 i (比如从30到1)。只要当前总项数还不够 k，并且我们有 2^i 这种大数 (counts[i] > 0)，就执行拆分：
   • counts[i] 减一
   • counts[i-1] 加二
   • 总项数加一
6. 重复这个拆分过程，直到总项数达到 k。
7. 最后，遍历 counts 数组，把所有的项打印出来就大功告成啦，喵呜~ 🐾

C++ 题解代码

这是可以直接提交的C++代码，本猫娘在上面加了一些中文注释，方便主人们理解每一部分的作用。

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <cmath>

// __builtin_popcount 是 GCC/Clang 编译器的一个内建函数，效率很高
// 在 C++20 中，它被标准化为 <bit> 头文件里的 std::popcount
// 在算法竞赛中用这个非常普遍，喵~
int main() {
    // 加速输入输出，让程序跑得快一点
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n, k;
    std::cin >> n >> k;

    // 计算 n 的二进制表示中 1 的个数，这是 k 的下限
    int set_bits = __builtin_popcount(static_cast<unsigned int>(n));

    // 无解判断：k 如果小于最少项数，或者大于最多项数(n)，则无解
    if (k < set_bits || k > n) {
        std::cout << "NO\n";
        return 0;
    }

    // 只要 k 在范围内，就一定有解
    std::cout << "YES\n";
    
    // 使用一个频率数组来存储每种2的幂次(2^i)的数量
    // counts[i] 存储 2^i 的个数
    std::vector<int> counts(31, 0);
    // 通过位运算，初始化 counts 数组，得到 n 的标准二进制表示
    for (int i = 0; i < 31; ++i) {
        if ((n >> i) & 1) {
            counts[i]++;
        }
    }

    int current_k = set_bits; // 当前的项数

    // 贪心地从最大的幂次开始拆分，直到项数达到 k
    // 每次拆分一个 2^i 会变成两个 2^(i-1)，总项数增加 1
    for (int i = 30; i > 0; --i) {
        // 如果项数已经够了，就不用再拆了
        if (current_k == k) {
            break;
        }

        // 如果我们有 2^i 这种项可以拆
        if (counts[i] > 0) {
            // 我们需要 k - current_k 个新项
            // 当前的 2^i 最多有 counts[i] 个可供我们拆
            // 所以我们实际能拆的数量是这两者中的较小值
            int can_expand = std::min(counts[i], k - current_k);
            
            if (can_expand > 0) {
                counts[i] -= can_expand;         // 减少 can_expand 个 2^i
                counts[i-1] += 2 * can_expand;   // 增加 2*can_expand 个 2^(i-1)
                current_k += can_expand;         // 总项数增加了 can_expand
            }
        }
    }

    // 循环输出最终结果
    bool first = true;
    for (int i = 0; i < 31; ++i) {
        int power_of_two = 1 << i; // 2^i
        for (int j = 0; j < counts[i]; ++j) {
            if (!first) {
                std::cout << " ";
            }
            std::cout << power_of_two;
            first = false;
        }
    }
    std::cout << "\n";

    return 0;
}

知识点小课堂

这道题涉及了几个非常基础但重要的计算机科学知识点，学好它们对解决很多问题都有帮助哦！

1. 二进制表示 (Binary Representation) 任何正整数 n 都可以唯一地表示为 n = c_m * 2^m + ... + c_1 * 2^1 + c_0 * 2^0，其中 c_i 是 0 或 1。这个性质是解决这个问题的基石，它给了我们一个初始的、项数最少的分解方案。

2. 位运算 (Bitwise Operations) 位运算是直接在二进制位上进行操作，速度飞快！

   • n >> i: 右移操作，n >> i 相当于 n 除以 2^i。
   • &: 按位与操作。(n >> i) & 1 是一个经典技巧，用来检查 n 的二进制表示中从右数第 i 位（从0开始）是否为 1。
   • __builtin_popcount(n): 这是 GCC/Clang 编译器提供的内建函数，能超级快地计算一个数二进制下 1 的个数。在算法竞赛里是必备神器！

3. 贪心算法 (Greedy Algorithm) 贪心算法就是在每一步都做出当前看起来最好的选择，期望通过一系列局部最优解得到全局最优解。在这个问题里，我们的“局部最优”就是拆分当前最大的数。这样做是正确的，因为每次拆分 2^i 都会稳定地增加一个项，并且给我们留下更小的 2^(i-1)，这些小项如果需要可以继续拆分。从大到小拆保证了我们总是有最大的项可以操作，避免了复杂的决策。这是一种简单而有效的策略，喵~

好啦，今天的讲解就到这里啦！希望主人们都能理解这个二进制魔法的奥秘！下次再见，喵~ ❤️