2013年第四届蓝桥杯省赛-J. 连号区间数

2020-09-25 · 25次阅读 · 原创 · 数据结构与算法

#蓝桥杯 #题解 #动态规划

原题链接

题面

小明这些天一直在思考这样一个奇怪而有趣的问题：

在 1 ~ N 的某个全排列中有多少个连号区间呢？

这里所说的连号区间的定义是：

如果区间 [L, R]里的所有元素（即此排列的第 L 个到第 R 个元素）递增排序后能得到一个长度为 R-L+1 的"连续"数列，则称这个区间连号区间。

当 N 很小的时候，小明可以很快地算出答案，但是当 N 变大的时候，问题就不是那么简单了，现在小明需要你的帮助。

输入描述

第一行是一个正整数 N ( $1 \leq N \leq 5 \times 10^4$ ), 表示全排列的规模。

第二行是 N 个不同的数字 $P_i\ (1 \leq P_i \leq N)$ ，表示这 N 个数字的某一全排列。

输出描述

输出一个整数，表示不同连号区间的数目。

输入样例

4
3 2 4 1

输出样例

题解

DP，找规律

动态规划

每个区间 i 到 j 的是否为连号区间及判断其子区间 i+1 到 j （该自取件要为连号区间，要进行判断）的最大值与在 i 位置的元素的关系，如果**arr[i]比该子区间大1或者小1，则该区间 i 到 j 也为连号区间，同样还要判断子区间 i 到 j-1 与arr[j]*的关系。由于用二维数组比较大，在此可借助vector来写一个压缩的下三角矩阵dp，存放位置 i 到 j的最大值max和最小值min，其中压缩矩阵与原矩阵的映射关系为： dp[k] = dp[i(i+1)/2+j]。
找规律

通过观察数组的规律可以知道，一个区间 i到j 的最大值max和最小值min的差值为该区间长度减1，即有

$max-min = j-i$ ，则可固定左端点i，遍历右端点j，计算该区间的最大最小，若满足上述条件，则计算器加一，j到末端后再遍历左端点i，可求得结果。

代码

#include<iostream>
#include<climits>
#include<cstdio>

using namespace std;
const int N = 50005;
int a[N], n, res;

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) scanf("%d", &a[i]);

    for (int i = 0; i < n; ++i) {
        int minv = INT_MAX;
        int maxv = INT_MIN;

        for (int j = i; j < n; ++j) {
            maxv = max(maxv, a[j]);
            minv = min(minv, a[j]);
            if (maxv - minv == j - i) res++;
        }
    }

    cout << res << endl;

    return 0;
}

标题：	2013年第四届蓝桥杯省赛-J. 连号区间数
链接：	https://www.fightingok.cn/detail/10
更新：	2022-09-18 22:31:41
版权：	本文采用 CC BY-NC-SA 3.0 CN 协议进行许可