D. Climbing the Tree - 题解

比赛与标签

比赛: CodeTON Round 4 (Div. 1 + Div. 2, Rated, Prizes!) 标签: binary search, math 难度: *1700

题目大意喵~

有一群可爱的小蜗牛要去爬一棵高度为 h 的树，h 是一个我们一开始不知道的正整数。

每只小蜗牛都有两个属性：白天向上爬 a 米，晚上睡觉时会滑下来 b 米（a > b）。如果一只蜗牛在第 n 天白天第一次到达或超过了树顶（高度 h），我们就说它花了 n 天。

接下来会有 q 个事件，分为两种类型：

1. 类型 1: 一只蜗牛 (a, b) 跑来告诉你，它花了 n 天爬上了这棵树。我们需要判断这个信息是否和我们已经采纳的信息相矛盾。如果不矛盾，我们就采纳这个信息，并用它来缩小我们对树高 h 的可能范围；如果矛盾，就忽略它。
2. 类型 2: 另一只蜗牛 (a, b) 跑来问，如果它去爬这棵树，需要多少天？我们需要根据当前掌握的关于 h 的所有信息来回答。如果能确定一个唯一的天数，就输出它；如果 h 的可能范围导致天数不唯一，就表示无法确定。

我们的任务就是按顺序处理这 q 个事件，并给出相应的回答，喵~

解题思路呐

这个问题的核心，其实就是根据蜗牛们提供的信息，不断地去推断和收窄树高 h 的可能取值范围。我们可以维护一个区间 [min_h, max_h]，表示根据目前所有采纳的信息，树高 h 可能的最小值和最大值。

关键一步：把蜗牛的话翻译成数学语言！

当一只蜗牛(a, b)说它花了 n 天时，它到底告诉了我们关于 h 的什么信息呢？我们来分析一下它的旅程：

• 特殊情况 n = 1: 如果只花了1天，说明它在第一个白天就爬到了树顶。它最多能爬 a 米，所以树高 h 肯定小于等于 a。又因为 h 是正整数，所以 1 <= h <= a。这就是 n=1 时 h 的范围啦。

• 一般情况 n > 1: 如果花了 n 天，这意味着两件事：

  1. 在第 n-1 天结束时，它还没爬到树顶。
  2. 在第 n 天的白天，它终于爬到了树顶。

  我们来计算一下它的高度。蜗牛每天的净前进量是 a - b 米。

  • 在第 n-1 天的白天，它能达到的最高高度是：爬了 n-2 个整天（(n-2) * (a-b)）之后，在第 n-1 天白天再爬一个 a。也就是 (n-2)*(a-b) + a。为了保证它在第 n-1 天没到顶，h 必须大于这个值。
  • 在第 n 天的白天，它从第 n-1 天晚上的高度 (n-1)*(a-b) 开始向上爬，最多能爬 a 米，所以能达到的最高高度是 (n-1)*(a-b) + a。为了保证它能在第 n 天到顶，h 必须小于等于这个值。

  结合一下，对于 n > 1 的情况，h 的范围是： (n-2)*(a-b) + a < h <= (n-1)*(a-b) + a 这个不等式的左边可以变得更漂亮一点：(n-2)*(a-b) + a = (n-1)*(a-b) - (a-b) + a = (n-1)*(a-b) + b。 所以，h 的范围就是 (n-1)*(a-b) + b < h <= (n-1)*(a-b) + a。 因为 h 是整数，所以等价于 (n-1)*(a-b) + b + 1 <= h <= (n-1)*(a-b) + a。

处理两种事件

有了上面的分析，处理事件就变得很简单啦！

• 对于类型 1 事件 (a, b, n):

  1. 根据 a, b, n 计算出这次信息所对应的 h 的范围，我们叫它 [new_L, new_R]。
  2. 将这个新范围和我们当前维护的 [min_h, max_h] 求交集。新的下界是 max(min_h, new_L)，新的上界是 min(max_h, new_R)。
  3. 如果求交集后，下界小于等于上界（即 max(min_h, new_L) <= min(max_h, new_R)），说明信息不矛盾。我们就更新 min_h 和 max_h 为新的交集范围，并输出 1。
  4. 如果下界大于上界，说明信息矛盾了，我们不更新范围，并输出 0。
  5. 初始时，h 是任意正整数，所以 min_h = 1，max_h 可以看作是无穷大。我们可以用一个特殊值（比如-1）来表示无穷大。

• 对于类型 2 事件 (a, b):

  1. 首先，我们需要一个函数 get_k(h, a, b) 来计算对于一个确定的树高 h，蜗牛(a, b)需要爬多少天。根据上面的推导，这个天数 k 是第一个满足 (k-1)*(a-b) + a >= h 的正整数 k。
     • 如果 h <= a，天数 k=1。
     • 如果 h > a，可以推导出 k = 1 + (h - b - 1) / (a - b)（这里的除法是整除哦）。这个公式非常精妙，大家可以自己代入几个数验证一下，很有趣的！
  2. 现在我们只知道 h 在 [min_h, max_h] 之间。我们分别计算出 h 取最小值和最大值时需要的天数：
     • k1 = get_k(min_h, a, b)
     • k2 = get_k(max_h, a, b)
  3. 因为 get_k 函数关于 h 是单调不减的，所以如果 k1 == k2，就意味着对于 [min_h, max_h] 中的任何一个 h，算出来的天数都是同一个值！这时我们就可以确定答案是 k1。
  4. 如果 k1 != k2，说明 h 取不同的值时，天数可能会不同，答案不唯一。我们就输出 -1。
  5. 哦对了，如果 max_h 还是无穷大（也就是我们还没采纳过任何有效信息），那肯定无法确定，直接输出 -1。

这样一来，我们就可以愉快地处理所有事件啦，喵~

代码实现喵！

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

// 一个让输入输出快到飞起的小魔法~
void fast_io() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
}

using ll = long long;

// 这个函数计算对于给定的树高h和蜗牛(a, b)，需要多少天
// h: 树高, a: 白天爬升, b: 晚上滑落
ll get_k(ll h, ll a, ll b) {
    // 如果第一天白天就能爬到顶
    if (h <= a) {
        return 1;
    }
    // 否则，需要更多天。
    // (h - b - 1) / (a - b) 计算的是除了第一天之外，还需要多少个完整的(a-b)周期才能覆盖剩下的高度。
    // 这里的 (h - b - 1) 是一个推导出的关键部分，确保了边界的正确性。
    // 最后加上第一天，就是总天数。
    return 1 + (h - b - 1) / (a - b);
}

void solve() {
    int q;
    std::cin >> q;

    // min_h 和 max_h 维护当前已采纳信息所决定的树高 h 的可能范围 [min_h, max_h]
    ll min_h = 1;
    ll max_h = -1; // 用-1这个特殊值表示无穷大，是个很方便的技巧哦！

    std::vector<ll> results;
    results.reserve(q); // 预先分配空间，避免多次重新分配内存，提高效率

    for (int i = 0; i < q; ++i) {
        int type;
        std::cin >> type;
        if (type == 1) {
            ll a, b, n;
            std::cin >> a >> b >> n;

            ll new_L, new_R; // 这次信息对应的 h 范围
            if (n == 1) {
                // 如果只花了1天，h 的范围是 [1, a]
                new_L = 1;
                new_R = a;
            } else {
                // 如果花了 n > 1 天，h 的范围是 [(n-1)*(a-b)+b+1, (n-1)*(a-b)+a]
                new_L = (n - 1) * (a - b) + b + 1;
                new_R = (n - 1) * (a - b) + a;
            }

            // 获取当前的 h 范围，注意处理 max_h 是无穷大的情况
            ll current_min_h = min_h;
            ll current_max_h = (max_h == -1) ? LLONG_MAX : max_h;

            // 求交集
            ll updated_min_h = std::max(current_min_h, new_L);
            ll updated_max_h = std::min(current_max_h, new_R);

            // 如果交集非空，则采纳信息并更新范围
            if (updated_min_h <= updated_max_h) {
                results.push_back(1);
                min_h = updated_min_h;
                max_h = updated_max_h;
            } else {
                // 否则信息矛盾，忽略
                results.push_back(0);
            }

        } else { // type == 2
            ll a, b;
            std::cin >> a >> b;

            // 如果 max_h 还是无穷大，说明信息不足，无法确定
            if (max_h == -1) {
                results.push_back(-1);
                continue;
            }

            // 计算在当前 h 范围的两个端点，蜗牛需要的天数
            ll k1 = get_k(min_h, a, b);
            ll k2 = get_k(max_h, a, b);

            // 如果天数相同，说明答案是唯一的
            if (k1 == k2) {
                results.push_back(k1);
            } else {
                // 否则答案不唯一
                results.push_back(-1);
            }
        }
    }

    // 一次性输出所有结果
    for (int i = 0; i < results.size(); ++i) {
        std::cout << results[i] << (i == results.size() - 1 ? "" : " ");
    }
    std::cout << "\n";
}

int main() {
    fast_io();
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

复杂度分析的说

• 时间复杂度: O(q) 的说。对于每个测试用例，我们有 q 个事件。每个事件的处理，无论是计算范围、求交集还是回答查询，都只涉及几次算术运算和比较，是常数时间 O(1) 的操作。所以总的时间复杂度和查询数量成正比，喵~
• 空间复杂度: O(q) 的说。我们用了一个 vector 来存储 q 个事件的答案，最后一起输出。所以空间复杂度和查询数量成正比。

知识点与总结

这道题真是一次愉快的思维探险呢！它把看似复杂的过程变成了一个清晰的数学问题。

1. 核心思想 - 区间维护: 整个题目的精髓在于，将每一条信息都转化为对未知变量 h 的一个区间约束。通过不断求这些区间的交集，我们就能逐步逼近真相。
2. 数学推导能力: 解题的关键是正确推导出蜗牛花费 n 天所对应的树高 h 的范围。这个过程需要细心，特别是要处理好 n=1 的边界情况和 n>1 的一般情况。那个 get_k 函数的公式也是数学推导的漂亮产物！
3. 编程技巧:
   • 使用 long long 来防止整数溢出，因为题目中的 a, b, n 很大，计算过程中可能会超出普通 int 的范围。
   • 用一个特殊值（如 -1 或 LLONG_MAX）来表示无穷大，是处理无上界区间的一个常用且优雅的方法。
4. 思维转换: 从具体的情景（蜗牛爬树）抽象出数学模型（区间交集），是解决算法问题的一项重要能力。不要被故事背景迷惑，要抓住问题的数学本质哦！

希望这篇题解能帮助大家更好地理解这道题！如果还有不明白的地方，随时可以再来问猫娘哦。我们下次解题再见，喵~！