C++

$\color{gold}{— > 蓝桥杯辅导课题解}$

$80分做法：$

思路：

暴力

$三重循环，第一重枚举左端点i，第二重枚举右端点j，第三重枚举区间[i, j]$

$有不是连续的数，break;否则res ++$

$时间复杂度：O(n^3logn)$

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

using namespace std;

const int N = 1e4 + 10;

int n;
int p[N], b[N];
int res;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> p[i];

    for (int i = 1; i <= n; i ++) // 左端点
        for (int j = i; j <= n; j ++) { // 右端点
            memcpy(b, p, sizeof p);
            sort(b + i, b + j + 1);

            bool flag = true;
            for (int k = i; k < j; k ++)  // 区间[i, j]
                if (b[k + 1] - b[k] != 1) {
                    flag = false;
                    break;
                }
            if (flag) res ++;
        }

    cout << res;    

    return 0;
}

$ps:蓝桥杯官网测试结果$

$100分(满分)做法：$

思路：

枚举

$1、两重循环，第一重枚举左端点i，第二重枚举右端点j，同时不断确定[i, j]的最大,最小值$

$2、如果max1 - min1 == j - i，res ++$

$(由于所给的n个数是1到n的全排列，所以不会出现重复的数)$

$时间复杂度：O(n^2)$

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

using namespace std;

const int N = 1e4 + 10, INF = 1e8;

int n;
int p[N];
int res;

int main() {
    cin >> n;
    for (int i = 0; i < n; i ++) cin >> p[i];

    for (int i = 0; i < n; i ++) { // 左端点
        int max1 = -INF, min1 = INF;
        for (int j = i; j < n; j ++) { // 右端点
            max1 = max(max1, p[j]); 
            min1 = min(min1, p[j]);
            if (max1 - min1 == j - i) res ++;
        }
    }

    cout << res;

    return 0;
}

$\small{分享：}$

$\large\color{blue}{— > C/C++输入字符串}$