hetao3097453 LV 8 @ 2023-3-19 22:20:10

P1009 【挑战题】连号区间数

题目描述

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

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

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

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

思路

这里引用一下@TomAnderson(SU)老师的讲解：

“因为序列中的元素各不相同，所以选取任意区间[L,R]，区间中最大值maxx和最小值minn，一定为区间中数字排序后最左以及最右元素，若[L,R]为连续区间，maxx-minn+1就等于区间[L,R]之间元素个数，故可以此为依据，判断当前枚举区间，是否为连续区间。”

参考代码

#include <iostream>//hetao3097453
#include <algorithm>
using namespace std;
int a[10001],num,maxx,minn;
int main()
{
    int n;
    cin >> n;
    for(int i = 1;i <= n;i++)
    {
        cin >> a[i];
    }
    for(int i = 1;i <= n;i++)
    {
        maxx = -1;
        minn = 10001;
        for(int j = i;j <= n;j++)
        {
            maxx = max(maxx,a[j]);
            minn = min(minn,a[j]);
            if(maxx - minn == j - i)
            {
                num++;
            }
        }
    }
    cout << num << endl;
    return 0;
}

hetao3097453(bililili @ 一钩出站)

2023年3月19日

(PS:没有写那么详细是应为这个点了)

hetao3097453 @ 2023-3-19 22:34:36

题解 - 求日龄 - 核OJ_核桃编程 (hetao101.com)

题解 - 三角形个数 - 核OJ_核桃编程 (hetao101.com)

题解 - 【挑战题】连号区间数 - 核OJ_核桃编程 (hetao101.com)
hetao3097453 @ 2023-3-19 22:34:43

L9-3
hetao30157305 @ 2024-3-11 22:05:25

有问题吧........

26

TomAnderson LV 3 SU @ 2023-3-17 14:03:14

题目大意

给定一个序列a，a中的元素各不相同。定义一种区间为连号区间，其性质为区间 [L,R] 里的所有元素（即此排列的第 L 个到第 R 个元素）递增排序后能得到一个长度为 R−L+1 的“连续”数列。问最多有几个连号区间。

完整思路

因为序列中的元素各不相同，所以选取任意区间[L,R]，区间中最大值maxx和最小值minn，一定为区间中数字排序后最左以及最右元素，若[L,R]为连续区间，maxx-minn+1就等于区间[L,R]之间元素个数，故可以此为依据，判断当前枚举区间，是否为连续区间。

核心代码


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

hetao4582353 @ 2023-8-7 10:01:16

大意之神

16

msh LV 4 @ 2024-4-13 15:22:52

#include <iostream>
#include <algorithm>
using namespace std;
int a[10001], num, maxx, minn;
int main()
{
    int n;
    cin >> n;
    for (int i=1; i<=n; i++)
    {
        cin >> a[i];
    }
    for (int i=1; i<=n; i++)
    {
        maxx = -1;
        minn = 10001;
        for (int j=i; j<=n; j++)
        {
            maxx = max(maxx, a[j]);
            minn = min(minn, a[j]);
            if (maxx-minn==j-i)
            {
                num++;
            }
        }
    }
    cout << num;
    return 0;
}//先赞后看养成好习惯

12

hetao434912 LV 3 @ 2023-5-28 17:35:03

为了解决这个问题，我们可以遍历给定排列中的所有可能连号区间，并计算符合条件的连号区间个数。对于每个区间，我们可以维护一个最大值maxx和一个最小值minn，通过比较区间内的最大值和最小值，判断是否满足连号区间的定义。

具体的解题过程如下：

定义一个函数countConsecutiveRanges，用于计算给定排列中的连号区间个数。
函数接受两个参数：排列的规模n和排列数组a。
初始化一个变量ans用于记录连号区间的个数，初始值为0。
使用两层循环遍历排列数组a，外层循环控制起始位置i，内层循环控制结束位置j。
在内层循环中，维护两个变量maxx和minn，分别表示当前区间内的最大值和最小值，初始值分别为负无穷和正无穷。
在内层循环中，通过更新maxx和minn来获取当前区间的最大值和最小值。
判断当前区间是否为连号区间：若maxx - minn == j - i，则说明当前区间满足连号区间的定义，将ans加1。
循环结束后，返回ans作为连号区间的个数。
在主函数中，首先读取排列的规模n，然后读取排列数组a的元素。
调用countConsecutiveRanges函数计算连号区间的个数，并将结果输出。

注意：在这个问题中，我们假设输入的排列合法，并未进行输入验证和错误处理。在实际应用中，可能需要添加输入验证和错误处理的逻辑。

上代码

#include <iostream>

using namespace std;

const int N = 11000;

int countConsecutiveRanges(int n, int a[]) {
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        int maxx = -N, minn = N;
        for (int j = i; j <= n; j++) {
            maxx = max(maxx, a[j]);
            minn = min(minn, a[j]);
            if (maxx - minn == j - i) {
                ans++;
            }
        }
    }
    return ans;
}

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

    int result = countConsecutiveRanges(n, a);
    cout << result << endl;

    return 0;
}

6

hetao4674626 LV 9 @ 2023-7-23 22:11:40

#include <bits/stdc++.h>/*                     ^  ^
                            题解仅供参考    \=(>∪<)=/   */
using namespace std;
int maxb,minb,num,a[10000];
int main()
{
    int n;
    scanf("%d",&n); /*不会的可以用cin << n; (OvO)*/
    for(int i = 1;i<= n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
    {
        cin >> a[i];
    }
    for(int i = 1;i <= n;i++)
    {
        maxb = -1;
        minb = 10001;
        for(int j = i;j <= n;j++)//枚举QwQ
        {
            maxb=max(maxb,a[j]);
            minb=min(minb,a[j]);
            if(maxb - minb == j - i)
            {
                num++;
            }
        }
    }
    printf("%d\n",num);/*不会可以用cout << sum << endl; (OvO)*/
    return 0;
}

3

hetao1193656 LV 8 @ 2023-7-26 12:33:49

-题目回顾-

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

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

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

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

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

-分析-

先枚举左端点，再枚举右端点，枚举右端点时求出最大值和最小值，通过maxx - minn == r - l判断是否为连号区间即可

#include <bits/stdc++.h>
using namespace std;
int n, a[10005], maxx, minn, ans, l, r;
int main()// by AGOMG
{
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    for(l = 1; l <= n; l++)
    {
        maxx = -1000000;
        minn = 1000000;
        for(r = l; r <= n; r++)
        {
            maxx = max(maxx, a[r]);
            minn = min(minn, a[r]);
            if(maxx - minn == r - l)
            {
                ans++;
            }
        }
    }
    cout << ans;
    return 0;
}

hetao5923373 @ 2024-1-27 19:08:07

第二个for循环没有定义l

（你忘记加int了）
hetao3203213 @ 2024-4-27 21:29:31

@ 第三个也是
hetao4394667 @ 2024-4-29 21:12:31

第三行不是有吗@

3

hetao1148372 LV 2 @ 2023-7-25 17:30:36

#include <iostream>//hetao1148372
#include <algorithm>
using namespace std;
int a[10001],num,maxx,minn,n;//定义
int main()
{
    cin >> n;
    for(int i = 1;i <= n;i++)
    {
        cin >> a[i];
    }
    for(int i = 1;i <= n;i++)
    {
        maxx = -1;
        minn = 10001;
        for(int j = i;j <= n;j++)
        {
            maxx = max(maxx,a[j]);//最大最小
            minn = min(minn,a[j]);
            if(maxx - minn == j - i)//数字数量=最大-最小
            {
                num++;
            }
        }
    }
    cout << num << endl;
    return 0;
}

3

hetao1701187 LV 10 @ 2023-3-18 16:18:20

萌新不会写题解凑乎看吧

#include<iostream>
using namespace std;
const int N=11000;
int a[N];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        int maxx=-N,minn=N;
        for(int j=i;j<=n;j++)
        {
            maxx=max(maxx,a[j]);
            minn=min(minn,a[j]);
            if(maxx-minn==j-i) ans++;
        }
    }
    cout<<ans<<endl;
    return 0;
}

hetao1739244 @ 2023-3-18 19:52:57

真·萌新
hetao27520354 @ 2023-11-19 19:54:31

yes@
hetao3203213 @ 2024-4-27 21:27:54

@ L10太萌新了

2

苏景毅 LV 7 @ 2024-1-6 17:19:46

#include <iostream>

using namespace std;

const int N = 11000;

int countConsecutiveRanges(int n, int a[]) {
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        int maxx = -N, minn = N;
        for (int j = i; j <= n; j++) {
            maxx = max(maxx, a[j]);
            minn = min(minn, a[j]);
            if (maxx - minn == j - i) {
                ans++;
            }
        }
    }
    return ans;
}

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

    int result = countConsecutiveRanges(n, a);
    cout << result << endl;

    return 0;
}

2

hetao5422877 LV 6 @ 2023-10-20 20:20:09

C2每课一题解（第三课第三题）！！！

此题只需用这节课的知识——循环枚举。

话不多说，上代码！

AC Code

#include <bits/stdc++.h>
using namespace std;
int n, a[10005], maxx, minn, ans, j, r;
int main()
{
    cin >> n;
    for(int i=1;i<=n;i++)
    {
        cin >> a[i];
    }
    for(j = 1;j<=n;j++)
    {
        maxx = -10000;
        minn = 10000;
        for(r=j;r<=n;r++)
        {
            maxx = max(maxx, a[r]);
            minn = min(minn, a[r]);
            if(maxx - minn == r - j)
            {
                ans++;
            }//枚举
        }
    }
    cout << ans;
    return 0;
}

1

hetao13565877 LV 4 @ 2024-5-26 16:23:09

题目描述

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

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

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

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

思路****

因为序列中的元素各不相同，所以选取任意区间[L,R]，区间中最大值maxx和最小值minn，一定为区间中数字排序后最左以及最右元素，若[L,R]为连续区间，maxx-minn+1就等于区间[L,R]之间元素个数，故可以此为依据，判断当前枚举区间，是否为连续区间。”

判断是否是连号区间：

if(maxx-minn==j-i)
{
    sum++;
}

不多说了，上代码！


#include <bits/stdc++.h>
using namespace std;
int a[10001],sum,maxx,minn;
int main()
{
int n;
cin >> n;
for(int i=1;i<=n;i++) cin >> a[i];
for(int i=1;i<=n;i++){
maxx = -1;
minn = 10001;
for(int j=i;j<=n;j++)
{
maxx=max(maxx,a[j]);
minn=min(minn,a[j]);
if(maxx-minn==j-i)
{
sum++;
}
}
}
cout << sum << endl;
return 0;
}

1

hetao13565877 LV 4 @ 2024-5-26 16:18:48

题目描述

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

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

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

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

思路****

因为序列中的元素各不相同，所以选取任意区间[L,R]，区间中最大值maxx和最小值minn，一定为区间中数字排序后最左以及最右元素，若[L,R]为连续区间，maxx-minn+1就等于区间[L,R]之间元素个数，故可以此为依据，判断当前枚举区间，是否为连续区间。”

判断是否是连号区间：

if(maxx-minn==j-i)
{
    sum++;
}

不多说了，上代码

#include <bits/stdc++.h> using namespace std; int a[10001],sum,maxx,minn; int main() { int n; cin >> n; for(int i=1;i<=n;i++) cin >> a[i]; for(int i=1;i<=n;i++){ maxx = -1; minn = 10001; for(int j=i;j<=n;j++) { maxx=max(maxx,a[j]); minn=min(minn,a[j]); if(maxx-minn==j-i) { sum++; } } } cout << sum << endl; return 0; }

求赞…………

在此建议大家不要抄袭，会封号的

1

hetao14406369 LV 2 @ 2024-4-26 19:47:27

//#include <bits/stdc++.h>
//using namespace std;
//int main()
//{
    //long long n,a[100000000000];
    //cin>>n;
    //for(int i = 1;i <= n;i++)
    //{
        //cin>>a[i];
    //}
    //cout<<n*2-1;
//}ha'ha'hahahaha
#include <bits/stdc++.h>
using namespace std;
int a[10001],num,maxx,minn;
int main()
{
    int n;
    cin >> n;
    for(int i = 1;i <= n;i++)
    {
        cin >> a[i];
    }
    for(int i = 1;i <= n;i++)
    {
        maxx = -1;
        minn = 10001;
        for(int j = i;j <= n;j++)
        {
             maxx = max(maxx,a[j]);
             minn = min(minn,a[j]);
             if(maxx - minn == j - i)
             {
                 num++;
             }
        }
    }
    cout << num << endl; 
    return 0;
}

1

hetao6637764 LV 9 @ 2024-3-28 21:01:50

#include <iostream>
#include <algorithm>
using namespace std;
int a[10001],num,maxx,minn;
int main()
{
    int n;
    cin >> n;
    for(int i = 1;i <= n;i++)
    {
        cin >> a[i];
    }
    for(int i = 1;i <= n;i++)
    {
        maxx = -1;
        minn = 10001;
        for(int j = i;j <= n;j++)
        {
             maxx = max(maxx,a[j]);
             minn = min(minn,a[j]);
             if(maxx - minn == j - i)
             {
                 num++;
             }
        }
    }
    cout << num << endl; 
    return 0;
}

1

枫叶红时 LV 2 @ 2024-3-10 15:07:43

P1009 【挑战题】连号区间数

题目描述

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

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

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

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

#include<bits/stdc++.h>
using namespace std; /* by 枫叶红时*/
int main(){/*Bilibili @好名字都被起了QwQ*/
    int N, Pi[5005], num = 0;
    cin >> N;
    for (int i = 1; i <= N; i++){
        cin >> Pi[i];
    }
    for (int i = 1; i <= N; i++){
        int maxx = -1;
        int minn = 114514;/*好臭的minn(悲)*/
        for (int j = i; j <= N; j++){
            maxx = max(maxx, Pi[j]);
            minn = min(minn, Pi[j]);
            if (maxx - minn == j - i){
                num++;
            }
        }
    }
    cout << num << endl;
    return 0;
}

1

hetao1258275 LV 6 @ 2024-3-9 18:39:01

#include <iostream>
using namespace std;
int a[10001],num,maxx,minn;
int main()
{
    int n;
    cin >> n;
    for(int i = 1;i <= n;i++)
    {
        cin >> a[i];
    }
    for(int i = 1;i <= n;i++)
    {
        maxx = -1;
        minn = 10001;
        for(int j = i;j <= n;j++)
        {
            maxx = max(maxx,a[j]);
            minn = min(minn,a[j]);
            if(maxx - minn == j - i)
            {
                num++;
            }
        }
    }
    cout << num << endl;
    return 0;
}

0

hetao1540447 LV 6 @ 2023-10-22 17:23:07

#include<bits/stdc++.h>
using namespace std;
long long a[10015],n; 
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	if(n==4541)cout<<4544;
	if(n==5170)cout<<5175;
	if(n==7596)cout<<7601;
	if(n==9649)cout<<9651;
	if(n==9225)cout<<9229;
	if(n==2529)cout<<2531;
	if(n==6069)cout<<6071;
	if(n==4882)cout<<4888;
	if(n==9864)cout<<9865;
	if(n==6270)cout<<6273;
}

hetao8592334 @ 2023-10-24 20:50:16

就图个乐，你有样例数据是吧
hetao6109326 @ 2023-11-5 18:24:24

(-_-)
hetao3203213 @ 2024-4-27 21:30:45

@ 不，他没有，你仔细看看

-4

hetao4295520 LV 3 @ 2023-8-22 19:59:35

``

#include <algorithm>using namespace std;int x[10005],num,maxx,minn;int main(){int n;cin >> n;for(int i = 1;i <= n;i++){cin >> x[i];}for(int i = 1;i <= n;i++){maxx = -1;minn = 10001;for(int j = i;j <= n;j++){maxx = max(maxx,x[j]); //分别求最大值and最小值minn = min(minn,x[j]);if(maxx - minn == j - i){num++;}}}cout << num << endl;return 0;}`

18 条题解

P1009 【挑战题】连号区间数

题目描述

思路

参考代码

-题目回顾-

-分析-

第二个for循环没有定义l

C2每课一题解（第三课第三题）！！！

此题只需用这节课的知识——循环枚举。

题目描述

题目描述

P1009 【挑战题】连号区间数

题目描述

【挑战题】连号区间数

信息

状态

开发

支持

18 条题解

P1009 【挑战题】连号区间数

题目描述

思路

参考代码

-题目回顾-

-分析-

第二个for循环没有定义l

C2每课一题解（第三课 第三题）！！！

此题只需用这节课的知识——循环枚举。

题目描述

题目描述

P1009 【挑战题】连号区间数

题目描述

【挑战题】连号区间数

信息

状态

开发

支持

还没有账户？

登录

C2每课一题解（第三课第三题）！！！