Moe's CF Life

Appearance

D. Phoenix and Science - 题解 ​

比赛与标签 ​

比赛: Codeforces Round 638 (Div. 2) 标签: binary search, constructive algorithms, greedy, implementation, math 难度: *1900

嘿，小伙伴们！一起来解开细菌之谜吧~ 喵~ ​

这道题是说，我们伟大的科学家菲尼克斯正在研究细菌的生长呐。

  • 初始状态: 第1天，有1个质量为1的细菌。
  • 分裂 (白天): 每天，我们可以选择任意数量的细菌进行分裂。一个质量为 m 的细菌会分裂成两个质量为 m/2 的新细菌。
  • 生长 (晚上): 每天晚上，每个细菌的质量都会增加1。

我们的任务是，对于给定的总质量 n，判断是否可能达到这个质量。如果可以，要用最少的夜晚数来实现，并告诉菲尼克斯每天需要分裂多少个细菌。

简单来说，就是：

  • 输入: 一个目标总质量 n。
  • 输出:
    • 如果能达到，输出两行：
      • 第一行是最少需要的夜晚数 d。
      • 第二行是 d 个整数，表示第1天到第d天，每天分裂的细菌数量。
    • 如果达不到，就输出 -1（不过这道题好像总是有解的喵~）。

解题思路喵~ 让我们一步步来分析！ ​

这道题看起来有点复杂，但只要我们理清细菌数量和质量的变化关系，就会变得清晰起来啦！

第一步：建立数学模型 ​

让我们用一些可爱的变量来描述这个过程~

  • d: 总共经过的夜晚数。
  • c_i: 第 i 天分裂后，细菌的总数量。我们让 c_0 = 1 表示初始状态。
  • s_i: 第 i 天分裂的细菌数量。

当第 i 天开始时，我们有 c_{i-1} 个细菌。我们选择其中的 s_i 个进行分裂。

  • s_i 个分裂的细菌变成了 2 * s_i 个。
  • c_{i-1} - s_i 个没分裂的细菌保持不变。 所以，第 i 天分裂后，总细菌数 c_i = (c_{i-1} - s_i) + 2 * s_i = c_{i-1} + s_i。 因为分裂的细菌数不能超过总数，所以 0 <= s_i <= c_{i-1}。 把这个代入上面的式子，我们就得到了一个至关重要的关系： c_{i-1} <= c_i <= 2 * c_{i-1}

接下来看总质量 n。

  • 初始时，总质量是 1。
  • 经过第1个夜晚，每个细菌质量+1。因为有 c_1 个细菌，所以总质量增加了 c_1。
  • 经过第2个夜晚，总质量又增加了 c_2。
  • ...
  • 经过第 d 个夜晚，总质量增加了 c_d。

所以，经过 d 个夜晚后的总质量 n 就是： n = 1 (初始质量) + c_1 + c_2 + ... + c_d 也就是 n - 1 = c_1 + c_2 + ... + c_d。

我们的目标，就是找到满足这两个核心条件的最小 d 和对应的 s_i 序列！

  1. n - 1 = c_1 + c_2 + ... + c_d
  2. c_{i-1} <= c_i <= 2 * c_{i-1} (其中 c_0 = 1)

第二步：确定最少的夜晚数 d ​

要让夜晚数 d 最少，我们就要让质量增长得尽可能快！质量的增长量是 c_i，所以我们应该让每天的细菌数量 c_i 尽可能多。 根据 c_i <= 2 * c_{i-1}，最快的增长方式就是每天让所有细菌都分裂，即 s_i = c_{i-1}，这样 c_i = 2 * c_{i-1}。 在这种极限情况下，细菌数量序列会是：c_0=1, c_1=2, c_2=4, ..., c_d=2^d。 此时能达到的最大总质量是 1 + 2^1 + 2^2 + ... + 2^d = 2^{d+1} - 1。 为了能够达到质量 n，我们需要的最小 d 必须满足 n <= 2^{d+1} - 1。 我们可以从小到大枚举 d，找到第一个满足这个条件的 d，这就是我们需要的答案啦！

第三步：贪心构造 s_i 序列 ​

找到了最小的 d 之后，我们就需要构造一个可行的 s_i 序列。直接构造 s_i 不太方便，但如果我们能先构造出 c_i 序列，就可以通过 s_i = c_i - c_{i-1} 轻松得到 s_i 啦。

我们来玩一个贪心游戏，从 c_1 到 c_d 一个一个确定它们的值。 在确定 c_i 的值时，它必须满足两个限制：

  1. 来自过去的限制: c_i >= c_{i-1}。这是因为最少可以一个都不分裂嘛。
  2. 来自未来的限制: c_i 的选择不能让后面的 c_{i+1}, ..., c_d 无法满足总和的要求。

让我们来推导一下这个“未来”的限制。 假设我们已经确定了 c_1, ..., c_{i-1}，还剩下 rem = c_i + c_{i+1} + ... + c_d 的质量需要凑。 我们知道 c_{i+1} <= 2*c_i, c_{i+2} <= 2*c_{i+1} <= 4*c_i, ... , c_{i+k} <= 2^k * c_i。 所以，rem 的最大可能值是： rem <= c_i + (2*c_i) + (4*c_i) + ... + (2^{d-i}*c_i)rem <= c_i * (1 + 2 + 4 + ... + 2^{d-i})rem <= c_i * (2^{d-i+1} - 1) 反过来，这就给了 c_i 一个下限： c_i >= rem / (2^{d-i+1} - 1)

喵喵，这个公式有点绕，让我们换个角度看代码里的实现，它更直观！ 当我们在第 i 轮循环（i 从 0 到 d-1）决定 c_{i+1}（在代码中是 c[i]）时：

  • rem 是剩余需要凑的总和 c_{i+1} + ... + c_d。
  • c_{i+1} 后面还有 d - (i+1) 项，也就是 d-i-1 项。
  • 从 c_{i+1} 开始，这一串子序列的最大可能增长是 c_{i+1}, 2*c_{i+1}, 4*c_{i+1}, ...
  • 所以 rem = c_{i+1} + ... + c_d <= c_{i+1} * (1 + 2 + ... + 2^{d-i-1}) = c_{i+1} * (2^{d-i} - 1)。
  • 这就得到了 c_{i+1} 的下限： c_{i+1} >= rem / (2^{d-i} - 1)。

所以，在确定 c_i 时，它必须同时满足：

  • c_i >= c_{i-1}
  • c_i >= ceil( (c_i + ... + c_d) / (2^{d-i+1} - 1) )

我们的贪心策略就是：每次选择满足这两个下限的最小整数值。 c_i = max(c_{i-1}, ceil(rem / (2^{d-i+1} - 1))) 这样，我们既保证了序列的递增关系，又给未来留下了最大的可能性，一定能构造出解！

确定了 c_1, ..., c_d 之后，我们就可以用 s_i = c_i - c_{i-1}（其中 c_0=1）来计算每天的分裂数啦！

代码实现喵~ ​

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

void solve() {
    long long n;
    std::cin >> n;

    // 步骤一: 计算最少的夜晚数 d 喵~
    // 经过 d 个夜晚，最多能达到的质量是 1 + 2 + 4 + ... + 2^d = 2^(d+1) - 1
    // 我们要找到最小的 d，使得 2^(d+1) - 1 >= n
    int d = 0;
    long long max_mass = 1; // 对应 2^(0+1)-1
    long long power_of_2 = 2; // 对应 2^1
    while (max_mass < n) {
        max_mass += power_of_2; // 加上 2^d
        power_of_2 *= 2;        // 准备下一轮的 2^(d+1)
        d++;
    }

    std::cout << d << "\n";

    // 步骤二: 贪心构造细菌数量序列 c_i (代码里是 c[0]..c[d-1])
    // 我们知道 n - 1 = c_1 + c_2 + ... + c_d
    // 并且 c_{i-1} <= c_i <= 2*c_{i-1}
    std::vector<long long> c(d);
    long long c_prev = 1; // c_0 = 1
    long long rem = n - 1; // 这是 c_1 + ... + c_d 的总和

    for (int i = 0; i < d; ++i) {
        // 我们正在决定 c_{i+1} (即代码中的 c[i])
        
        // 限制1: c[i] >= c_prev, 也就是 c_{i+1} >= c_i
        long long lower_c_from_prev = c_prev;
        
        // 限制2: c[i] 必须足够大，以保证剩下的项可以被凑出来
        // rem' = c[i] + ... + c[d-1]
        // rem' <= c[i] * (1 + 2 + ... + 2^(d-1-i)) = c[i] * (2^(d-i) - 1)
        // 所以 c[i] >= rem' / (2^(d-i) - 1)
        long long lower_c_from_rem;
        long long num_rem_terms_including_current = d - i;
        long long denom = (1LL << num_rem_terms_including_current) - 1;
        // 使用 (rem + denom - 1) / denom 来计算向上取整，防止精度问题
        lower_c_from_rem = (rem + denom - 1) / denom;

        // 贪心选择：取两个下限中较大的一个
        c[i] = std::max(lower_c_from_prev, lower_c_from_rem);
        
        // 更新剩余总和和前一个 c 的值
        rem -= c[i];
        c_prev = c[i];
    }

    // 步骤三: 根据 c_i 计算每天的分裂数 s_i
    std::vector<long long> s(d);
    c_prev = 1; // 重置 c_0 = 1
    for (int i = 0; i < d; ++i) {
        s[i] = c[i] - c_prev; // s_{i+1} = c_{i+1} - c_i
        c_prev = c[i];
    }

    // 步骤四: 输出结果~
    for (int i = 0; i < d; ++i) {
        std::cout << s[i] << (i == d - 1 ? "" : " ");
    }
    std::cout << "\n";
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

复杂度分析的说 ​

  • 时间复杂度: O(log n) 的说。
    • 计算 d 的循环，每次 max_mass 大约翻倍，所以循环次数是 log 级别的，即 O(log n)。
    • 构造 c 序列和计算 s 序列的循环都执行 d 次，而 d 本身就是 O(log n)。
    • 所以每个测试用例的总时间复杂度是 O(log n) 哦，非常快！
  • 空间复杂度: O(log n) 的说。
    • 我们需要两个 vector 来存储 c_i 和 s_i，它们的长度都是 d，也就是 O(log n)。

知识点与总结喵~ ​

这真是一道有趣的构造题，融合了数学和贪心思想！

  1. 数学建模是关键: 解题的第一步是把问题描述转化为清晰的数学关系式，即 n - 1 = Σc_i 和 c_{i-1} <= c_i <= 2*c_{i-1}。这是我们所有推导的基础呐。
  2. 极端情况分析: 为了求出最小天数 d，我们考虑了最快的增长情况（每天全部分裂），从而得到了一个关于 n 和 d 的不等式，巧妙地确定了 d。
  3. 贪心构造: 确定了 d 之后，我们采用贪心策略一步步构造出 c_i 序列。这里的贪心选择是“在满足所有约束的前提下，取当前能取的最小值”，这样能为后续步骤留出最大的操作空间。
  4. 边界推导: 解题中最有挑战性的部分就是推导 c_i 的下限。理解 c_i 不仅受前一项 c_{i-1} 的影响，还受未来所有项总和的约束，是解题的核心洞察。

希望这篇题解能帮助你理解这道题的奇妙之处！继续加油，探索更多算法的奥秘吧！喵~ >w<

Released under the MIT License.

Copyright © 2024-present Moe