摘要
Title: 2074. 倒计数
Tag: 双指针、差分
Memory Limit: 64 MB
Time Limit: 1000 ms

2074. 倒计数

题意

艾弗里有一个由 N 个正整数构成的数组。
数组中的第 i 个整数是 Ai。
如果一个连续的子数组的长度为 m，并且按顺序包含整数 m,m−1,m−2,…,2,1，则称它为 m 倒计数。
例如，[3,2,1] 是 3 倒计数。
请帮助艾弗里计算她的数组中有多少个 K 倒计数。
思路

思路是差分
- 先将连续的区间标记出来，再做前缀和
- 再枚举每个点x，看另一端的原数组是否为1，看前缀和数组这个点是否为x

代码

/*
* @Author: NEFU AB-IN
* @Date: 2022-08-13 15:39:09
* @FilePath: \Acwing\2074\2074.cpp
* @LastEditTime: 2022-08-13 16:01:19
*/
#include <bits/stdc++.h>
using namespace std;
#define N n + 100
#define int long long
#define SZ(X) ((int)(X).size())
#define IOS                                                                                                            \
    ios::sync_with_stdio(false);                                                                                       \
    cin.tie(nullptr);                                                                                                  \
    cout.tie(nullptr)
#define DEBUG(X) cout << #X << ": " << X << '\n'
typedef pair<int, int> PII;

void solve(int T)
{
    int n, k;
    cin >> n >> k;
    vector<int> a(n + 1), b(n + 1);
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
        if (i > 1 && a[i - 1] - a[i] == 1)
        {
            b[i] = b[i - 1] = 1;
        }
    }
    for (int i = 1; i <= n; ++i)
        b[i] += b[i - 1];

    int ans = 0;
    for (int i = 1; i + k - 1 <= n; ++i)
    {
        if (a[i] - a[i + k - 1] == k - 1 && b[i + k - 1] - b[i - 1] == k && a[i + k - 1] == 1)
            ans += 1;
    }
    printf("Case #%lld: %lld\n", T, ans);
    return;
}

signed main()
{
    IOS;
    int T;
    cin >> T;
    for (int i = 1; i <= T; ++i)
    {
        solve(i);
    }
    return 0;
}

当然也可以用双指针，看连续的段，有没有长度大于等于k即可

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 200010;

int n, m;
int q[N];

int main()
{
    int T;
    scanf("%d", &T);
    for (int cases = 1; cases <= T; cases ++ )
    {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i ++ ) scanf("%d", &q[i]);
        int res = 0;

        for (int i = n; i; i -- )
        {
            if (q[i] != 1) continue;
            int j = i - 1;
            while (j && q[j] == q[j + 1] + 1) j -- ;
            if (i - j >= m) res ++ ;
            i = j + 1;
        }
        printf("Case #%d: %d\n", cases, res);
    }

    return 0;
}

2074. 倒计数

题意

思路

代码