蓝桥杯训练历届试题连号区间数（枚举 + 规律）

忘是亡心i 2022-03-16 06:10 259阅读 0赞

**问题描述**

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

**在1~N的某个全排列中有多少个连号区间呢？这里所说的连号区间的定义是：**

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

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

**输入格式**

**第一行是一个正整数N (1 <= N <= 50000), 表示全排列的规模。**

**第二行是N个不同的数字Pi(1 <= Pi <= N)， 表示这N个数字的某一全排列。**

**输出格式**

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

**样例输入1**

**4  
3 2 4 1**

**样例输出1**

**7**

**样例输入2**

**5  
3 4 2 5 1**

**样例输出2**

**9**

> 根据这个题目给的条件，给的数列为某个数的全排列， 那么没有两个数是一样的， 所以如果某一个区间的最大值 - 最小值 = 区间的长度-1， 那么这个区间肯定是就是题目所说的连号区间。

#include<iostream>
    #include<algorithm>
    #include<cstdio>
    #include<cstring>
    #include<string>
    using namespace std;
    
    int main() {
    	int n,m,j,k,i,T;
    	int a[50000+10];
    	scanf("%d",&n);
    	for (i=0; i<n; i++)
    		scanf("%d",&a[i]);
    
    	int ans=0;
    	for (i=0; i<n; i++) {
    		int max=-1,min=10000000;
    		for (j=i; j<n; j++) {
    
    
    			if (a[j]>max)
    				max = a[j];
    			if (a[j]<min)
    				min = a[j];
    
    			if (max-min+1==j-i+1)
    				ans++;
    		}
    	}
    	printf("%d\n",ans);
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，259人围观）

还没有评论，来说两句吧...

相关阅读

相关历届试题连号区间数获取关键信息

问题描述小明这些天一直在思考这样一个奇怪而有趣的问题：在1~N的某个全排列中有多少个连号区间呢？这里所说的连号区间的定义是：如果区间\[L, R\] 里的所有元素（

深碍√TFBOYSˉ_/ 2024年02月17日 20:21/ 0 赞/ 53 阅读

相关历届试题连号区间数

试题历届试题连号区间数资源限制时间限制：1.0s 内存限制：256.0MB 问题描述小明这些天一直在思考这样一个奇怪而有趣的问题：

我就是我/ 2023年07月13日 13:59/ 0 赞/ 18 阅读

相关蓝桥杯历届试题小朋友排队

历届试题小朋友排队时间限制：1.0s 内存限制：256.0MB 问题描述　　n 个小朋友站成一排。现在要把他们按身高从低到高的顺序排列，但是每次只能交换位置相邻的两

清疚/ 2022年08月21日 04:58/ 0 赞/ 279 阅读

相关蓝桥杯历届试题翻硬币

问题描述小明正在玩一个“翻硬币”的游戏。桌上放着排成一排的若干硬币。我们用 \ 表示正面，用 o 表示反面（是小写字母，不是零）。比如，可能情形是： ![在这

亦凉/ 2022年03月26日 08:26/ 0 赞/ 289 阅读

相关蓝桥杯训练历届试题连号区间数（枚举 + 规律）

问题描述小明这些天一直在思考这样一个奇怪而有趣的问题：在1~N的某个全排列中有多少个连号区间呢？这里所说的连号区间的定义是：如果区间\[L, R\] 里的所有元素（

忘是亡心i/ 2022年03月16日 06:10/ 0 赞/ 260 阅读

相关蓝桥杯训练历届试题带分数（全排列 + 枚举）

问题描述 100 可以表示为带分数的形式：100 = 3 + 69258 / 714。还可以表示为：100 = 82 + 3546 / 197。注意特征：带分数中，数

青旅半醒/ 2022年03月15日 04:20/ 0 赞/ 270 阅读

相关蓝桥杯训练历届试题 k倍区间（前缀数组和）

问题描述　　给定一个长度为N的数列，A1, A2, ... AN，如果其中一段连续的子序列Ai, Ai+1, ... Aj(i <= j)之和是K的倍数，我们就称这个区间\

ゝ一纸荒年。/ 2022年03月11日 08:07/ 0 赞/ 211 阅读

相关蓝桥杯训练历届试题 Excel地址

问题描述　　Excel单元格的地址表示很有趣，它使用字母来表示列号。　　比如，　　A表示第1列，　　B表示第2列，　　Z表示第26列，　　AA

不念不忘少年蓝@/ 2022年03月08日 21:18/ 0 赞/ 286 阅读

相关历届试题连号区间数

思路分析：直接暴力枚举区间左右端点小技巧，维护区间的最大值最小值用来判断区间满足条件最大值-最小值+1==区间长度，即为连号区间，不需要排序

雨点打透心脏的1/2处/ 2022年03月06日 18:44/ 0 赞/ 189 阅读

相关蓝桥杯试题算法训练二进制数数

试题算法训练二进制数数资源限制时间限制：1.0s 内存限制：256.0MB 问题描述　　给定L,R。统计\[L,R\]区间内的所有数在二进制下包含的“1

悠悠/ 2021年09月24日 00:34/ 0 赞/ 363 阅读