题解 CF1840C Ski Resort

Problem

给定一个序列 $a$，问在其中有多少个连续的长度不小于 $k$ 且所有数不大于 $q$ 的子序列。

Solution

读入时统计在 $a_i$ 和 $a_i$ 前面有多少个不大于 $q$ 的数，设其为 $d_i$，于是以 $a_i$ 结尾的复合条件的子序列个数为 $\max\{0, d_i - k + 1\}$。累加即可。

Code

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <string>
#include <cstring>
#include <cctype>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int inf = 0x3f3f3f3f;
#define elif else if
#define il inline

int t, n, k, q, a[200005];

int main()
{
    cin >> t;
    while (t--)
    {
        cin >> n >> k >> q;
        int d = 0;
        ll ans = 0;
        for (int i = 1; i <= n; i++)
        {
            cin >> a[i];
            if (a[i] <= q)
                d++;
            else
                d = 0;
            ans += max(0, d - k + 1);
        }
        cout << ans << endl; 
    }
    return 0;
}

---

• 分类： OI 题解
• 标签： 无标签