Moe's CF Life

喵哈~ 各位小伙伴们好呀！今天由我，你们最可爱的小猫娘，来给大家讲解一道关于滑雪度假的有趣问题，Codeforces 1840C - Ski Resort！这道题不难，但里面藏着一些可爱的小技巧哦，一起来看看吧，喵~

题目大意

这道题是说，有一个叫 Dima 的同学要去度假啦，总共有 $n$ 天假期。他超级想去滑雪，所以计划找一段连续的日子去。

不过 Dima 有两个小小的要求，喵~

他的滑雪旅行必须至少持续 $k$ 天。一天两天的太短啦，玩不尽兴的说！
他来自西伯利亚，怕热不怕冷。所以，旅行期间的每一天，温度都不能超过 $q$ 度。

我们呢，会拿到一个包含 $n$ 天天气预报的数组 $a$ ，其中 $a_i$ 表示第 $i$ 天的温度。我们的任务就是，帮健忘的 Dima 算一算，总共有多少种不同的方式来选择度假的日期区间呢？

举个例子，如果 [1, 2, 3] 是一段合法的旅行日期，[2, 3, 4] 也是，那这就是两种不同的方案哦。

解题思路

拿到题目，我们先来分析一下 Dima 的要求，喵。最重要的限制条件就是温度不能超过 $q$ 度。任何一天温度只要高于 $q$ ，Dima 就绝对不会在那天滑雪。

这给了我们一个很棒的思路！我们可以把所有温度高于 $q$ 的日子看作是**“坏日子”，它们就像讨厌的分割线，把整个假期划分成了一段一段连续的“好日子”**（也就是温度 $ \le q$ 的日子）。

Dima 的任何一次旅行，都必须完完整整地落在某一段连续的“好日子”里，绝对不能跨越任何一个“坏日子”，对吧？

那么问题就简化啦：

首先，我们找出所有由“好日子”组成的连续段。
然后，对每一段连续的“好日子”，我们单独计算它能产生多少种合法的旅行方案。
最后，把所有段的方案数加起来，就是最终的答案啦！

那么，对于一个长度为 $L$ 的连续“好日子”段，要怎么计算方案数呢？

Dima 的旅行至少要 $k$ 天。所以：

如果这段“好日子”的长度 $L < k$ ，那它太短了，连最短的旅行要求都满足不了，所以它贡献的方案数是 0，喵。
如果这段“好日子”的长度 $L \ge k$ ，那它就有很多种可能性啦！我们可以选择在这里面度过 $k$ 天，或者 $k+1$ 天，...，一直到 $L$ 天。

我们来数一数：

长度为 $k$ 的旅行方案有多少种？在一个长度为 $L$ 的段里，长度为 $k$ 的子段可以从第 1 天开始，第 2 天开始，...，直到第 $L-k+1$ 天开始。所以总共有 $L-k+1$ 种。
长度为 $k+1$ 的旅行方案有多少种？同理，有 $L-(k+1)+1 = L-k$ 种。
...
长度为 $L$ 的旅行方案有多少种？只有 1 种，就是整个“好日子”段。

所以，总方案数就是把这些全都加起来：$$(L-k+1) + (L-k) + \dots + 2 + 1$$。咦？这不就是一个从 1 加到 $L-k+1$ 的等差数列嘛！让咱们设 $m = L-k+1$ ，那这个和就是 $1 + 2 + \dots + m$ 。根据我们小学就学过的（真的吗喵？）高斯求和公式，这个和等于 $\frac{m \times (m+1)}{2}$ 。

所以，我们的最终算法就是：

遍历整个天气数组。
用一个计数器 current_length 记录当前连续“好日子”的长度。
如果遇到一个“好日子” (温度 $ \le q$)，就给 current_length 加一。
如果遇到一个“坏日子” (温度 $ > q$)，说明一段连续的“好日子”结束了。此时检查刚刚记录的 current_length：
- 如果 current_length >= k，就用上面的公式 $\frac{m \times (m+1)}{2}$ (其中 $m = \text{current\_length} - k + 1$ ) 计算出方案数，加到总答案 total_ways 里。
- 然后，把 current_length 重置为 0，准备记录下一段。
特别注意！ 当遍历完所有天数后，最后一段“好日子”可能不会被一个“坏日子”打断。所以循环结束后，我们要对最后记录的 current_length 再做一次步骤 4 的计算，可不能把它漏掉啦，就像猫猫舔毛要舔干净每个角落一样，喵~

题解代码

下面就是根据这个思路写出的 C++ 代码啦，我已经加上了可爱的注释哦！

cpp

#include <iostream>
#include <vector>

void solve() {
    long long n, k, q;
    std::cin >> n >> k >> q;
    std::vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }

    long long total_ways = 0;      // 用来存放最终答案的总方案数
    long long current_length = 0;  // 记录当前连续“好日子”的长度

    for (int i = 0; i < n; ++i) {
        if (a[i] <= q) {
            // 今天天气不错 (<= q)，是“好日子”！
            current_length++;
        } else {
            // 哎呀，天气太热了 (> q)，是“坏日子”！
            // 一段连续的“好日子”到此结束了，我们来结算一下~
            if (current_length >= k) {
                // 这段“好日子”足够长，可以安排旅行
                long long L = current_length;
                long long m = L - k + 1; // 可以选择的旅行起点种类数
                // 使用等差数列求和公式计算方案数
                total_ways += m * (m + 1) / 2;
            }
            // 遇到“坏日子”后，连续天数就要重新计数啦
            current_length = 0;
        }
    }

    // 循环结束后，别忘了处理最后一段可能的“好日子”！
    // 因为它后面没有“坏日子”来触发结算逻辑了
    if (current_length >= k) {
        long long L = current_length;
        long long m = L - k + 1;
        total_ways += m * (m + 1) / 2;
    }

    std::cout << total_ways << "\n";
}

int main() {
    // 加速输入输出，让程序跑得像猫一样快，喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

知识点介绍

这道题虽然简单，但涉及了几个很实用的编程思想和数学知识点哦！

分治思想 (Divide and Conquer) / 段处理 这道题的核心就是把一个大问题（在 $n$ 天里找方案）分解成一个个小问题（在每个“好日子”段里找方案）。我们通过“坏日子”作为分割点，将原数组切分成若干个独立的子问题，分别求解后再合并结果。这种思想在处理连续子数组或子串问题时非常常见！
等差数列求和 (Sum of an Arithmetic Series) 喵~ 这是一个小小的数学魔法！当我们要计算从 1 加到 m（即 $1+2+3+\dots+m$ ）的时候，不需要一个一个地加，有一个超级方便的公式： $\frac{m \times (m+1)}{2}$ 。这个公式能让我们在 O(1) 的时间内完成计算，大大提高了效率。能发现并应用这个公式是解题的关键之一。
边界情况处理 (Edge Case Handling) 在编程中，我们总是要小心翼翼地处理边界。这道题最容易出错的地方，就是忘记处理数组末尾的那一段连续“好日子”。因为我们的计算逻辑是在遇到“坏日子”时触发的，如果数组以“好日子”结尾，循环体内就不会处理最后一段。所以，在循环外补充一次检查和计算，是保证程序正确性的重要一步。就像猫咪走路会小心避开水坑一样，我们写代码也要小心绕开这些“坑”呀！

好啦，今天的讲解就到这里啦！希望大家都能理解这道题的思路，并且玩得开心。下次再见，喵~ (ฅ'ω'ฅ)

题目大意 ​

解题思路 ​

题解代码 ​

知识点介绍 ​

题目大意

解题思路

题解代码

知识点介绍