当前位置： 首页 > article >正文

《从入门到精通：蓝桥杯编程大赛知识点全攻略》（九）-连号区间数、递增三元组

article 2025/2/10 20:01:55

前言

在本篇博客中，我们将通过模拟方法解决两道经典的算法题：连号区间数和递增三元组。通过这两道题，我们将展示如何通过模拟操作和细致的算法设计来解决实际问题，帮助提升算法思维和编码能力。

连号区间数

小明这些天一直在思考这样一个奇怪而有趣的问题：
在 1∼N 的某个排列中有多少个连号区间呢？

这里所说的连号区间的定义是：如果区间 [L,R] 里的所有元素（即此排列的第 L 个到第 R 个元素）递增排序后能得到一个长度为 R−L+1 的“连续”数列，则称这个区间连号区间。
当 N很小的时候，小明可以很快地算出答案，但是当 N 变大的时候，问题就不是那么简单了，现在小明需要你的帮助。
输入格式
第一行是一个正整数 N，表示排列的规模。
第二行是 N 个不同的数字 Pi，表示这 N 个数字的某一排列。
输出格式
输出一个整数，表示不同连号区间的数目。
数据范围
1≤N≤10000,1≤Pi≤N
输入样例1：

4
3 2 4 1

输出样例1：

7

输入样例2：

5
3 4 2 5 1

输出样例2：

9

样例解释
第一个用例中，有 7 个连号区间分别是：[1,1],[1,2],[1,3],[1,4],[2,2],[3,3],[4,4]

第二个用例中，有 9 个连号区间分别是：[1,1],[1,2],[1,3],[1,4],[1,5],[2,2],[3,3],[4,4],[5,5]

算法思路

暴力做法，只需要枚举每一个区间的左端点和区间的右端点，然后分别对每一个区间进行排序，之后再对区间的元素进行遍历，当区间的后一个元素比前一个元素多一时，说明是一种方案。
这样的时间复杂度为O(n^3logn)，会超时，我们可以对区间内的元素是否是等差数列进行优化。
将区间的最大值和最小值记录一下，当区间的最大值-区间的最小值=右区间-左区间（即max- min == j-i）时就说明该方案是合格的。
此时时间复杂度是O(n^2)，能够通过。

代码如下

暴力做法

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n+1]; // 区间下标从1开始，所以n+1
        for (int i=1; i<=n; i++) {
            arr[i] = sc.nextInt();
        }

        int res = 0;
        for (int i=1; i<=n; i++) {
            for (int j=i; j<=n; j++) {
                int[] temp = arr.clone(); // 开一个新数组，便于每次新数组排序
                Arrays.sort(temp, i, j+1); // 把新数组中[i,j]排序
                boolean flag = true;
                for (int k=i; k<j; k++) {
                    if (temp[k+1] - temp[k] != 1) {
                        flag = false; 
                        break;
                    }
                }
                if (flag == true) {
                    res ++;
                }
            }
        }
        System.out.println(res);
    }
}

优化版本

import java.io.*;

public class Main {
    static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StreamTokenizer st = new StreamTokenizer(br);
    static int mod = 100000007;
    static int N = 10010;
    static int[] arr = new int[N];
    public static void main(String[] args) throws Exception {
        int n = nextInt();
        for(int i = 1; i <= n; i++){
            arr[i] = nextInt();
        }
        int res = 0;
        for(int i = 1; i <= n; i++){//枚举区间左端点
            int max = Integer.MIN_VALUE;
            int min = Integer.MAX_VALUE;
            for(int j = i; j <= n; j++){//枚举区间右端点
                max = Math.max(max, arr[j]);//区间最大值
                min = Math.min(min, arr[j]);//区间最小值
                if(max - min == j - i){
                    res++;
                }
            }
        }
        pw.println(res);
        pw.flush();
    }

    public static int nextInt()throws Exception{
        st.nextToken();
        return (int)st.nval;
    }
}

递增三元组

给定三个整数数组

A=[A1,A2,…AN],B=[B1,B2,…BN],C=[C1,C2,…CN],
请你统计有多少个三元组 (i,j,k) 满足：

  • 1≤i,j,k≤N
  • Ai<Bj<Ck

输入格式
第一行包含一个整数 N。
第二行包含 N 个整数 A1,A2,…AN。
第三行包含 N 个整数 B1,B2,…BN。
第四行包含 N 个整数 C1,C2,…CN。
输出格式
一个整数表示答案。
数据范围
1≤N≤105,0≤Ai,Bi,Ci≤105
输入样例：

3
1 1 1
2 2 2
3 3 3

输出样例：

27

算法思路

在这里插入图片描述
暴力做法直接枚举3层循环i、j、j，然后做判断满足 Ai < Bj && Bj < Ck的情况方案数加1即可，但会超时。
根据题意需要求有多少个i、j、k满足Ai<Bj<Ck，故就是求对于B数组中的每一个数Bj，在A数组中有多少个数小于Bj，在C数组中有多少个数大于Bj。
我们可以用前缀和的思路来处理这道题。对于在A中有多少个数小于Bj，用数组cnt来存储A数组中每个数出现在的次数即cnt[i]表示i这个值在A数组中出现的次数，然后求cnt数组的前缀和数组s，s[i] = cnt[0] + cnt[1]+…+cnt[i]表示在A数组中0~i出现的次数，最后求在A数组中有多少个数小于Bj即s[Bj - 1]。
求在C数组中有多少个数大于Bj，同样用前缀和的方法开处理，先将原本的cnt和s两个数组都清0，然后遍历C数组，用cnt数组统计C数组中每个值出现的次数即cnt[i]表示i这个值在C数组中出现的次数，然后求cnt数组的前缀和数组s，s[i]表示在C数组中0~i出现的次数，要求在C数组中有多少个数大于Bj即s[N -1] - s[Bj]。
最后将每一个Bj对应在A数组中有多少个数小于Bj，在C数组中有多少个数大于Bj两个结果相乘即可。

N = 100010，因为数组中数组的最大值是105，需要求大于Bj的值出现的次数，需要用0 ~ 10000所有数出现的次数即s[N-1]减去0~Bj的数出现的次数即s[Bj]就是大于Bj的数出现的次数。

因为数组中每个值的范围是0~105，同时我们需要统计cnt数组的前缀和数组，但此时cnt[0]表示数组中0出现的次数，而s[0]其实是无意义的，故做题时数组输入值时都加1，这样可以让cnt[0]变为无意义，s[0]也无意义，减少做题的复杂度。

在这里插入图片描述

代码如下

暴力枚举（会超时）：

import java.util.*;
import java.io.*;
public class Main {
    static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StreamTokenizer st = new StreamTokenizer(br);
    static int N = 100010;
    static int n;
    static int[] a = new int[N];
    static int[] b = new int[N];
    static int[] c = new int[N];
    public static void main(String[] args)throws Exception {
        int n = nextInt();
        for(int i = 1; i <= n; i++){
            a[i] = nextInt();
        }
        for(int i = 1; i <= n; i++){
            b[i] = nextInt();
        }
        for(int i = 1; i <= n; i++){
            c[i] = nextInt();
        }
        long res = 0;
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                for(int k = 1; k <= n; k++){
                    if(a[i] < b[j] && b[j] < c[k]){
                        res++;
                    }
                }
            }
        }
        pw.println(res);
        pw.flush();

    }
    public static int nextInt() throws Exception {
        st.nextToken();
        return (int) st.nval;
    }

}

前缀和方法代码如下：


import java.io.*;
import java.util.Arrays;

public class Main {
    static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StreamTokenizer st = new StreamTokenizer(br);
    static int N = 100010;
    static int n;
    static int[] a = new int[N];
    static int[] b = new int[N];
    static int[] c = new int[N];
    //as[i]在A数组中有多少个数小于b[i]
    static int[] as = new int[N];
    //cs[i]在A数组中有多少个数大于b[i]
    static int[] cs = new int[N];
    static int[] cnt = new int[N];
    //前缀和数组
    static int[] s = new int[N];
    public static void main(String[] args) throws Exception {
        n = nextInt();
        for (int i = 1; i <= n; i++) {
            a[i] = nextInt()+1;
        }
        for (int i = 1; i <= n; i++) {
            b[i] = nextInt()+1;
        }
        for (int i = 1; i <= n; i++) {
            c[i] = nextInt()+1;
        }
        //求as[]

        for(int i = 1; i <= n; i++){
            cnt[a[i]]++;
        }
        //输入的时候3个数组中的值保证了最小值是1，这样求cnt数组的前缀和的时候可以保证s[0]还是0
        for(int i = 1; i < N; i++){
            s[i] = s[i-1] + cnt[i];
        }
        for(int i = 1; i <= n; i++){
            as[i] = s[b[i] - 1];
        }

        //求cs[]
        Arrays.fill(cnt, 0);
        Arrays.fill(s, 0);
        for(int i = 1; i <= n; i++){
            cnt[c[i]]++;
        }
        for(int i = 1; i < N; i++){
            s[i] = s[i-1] + cnt[i];
        }
        for(int i = 1; i <= n; i++){
            cs[i] = s[N - 1] - s[b[i]];
        }
        //枚举每个b[i]
        long res = 0;
        for(int i = 1; i <= n; i++){
            res += (long)cs[i] * as[i];
        }
        pw.println(res);
        pw.flush();
    }
    public static int nextInt() throws Exception {
        st.nextToken();
        return (int) st.nval;
    }
}

总结

通过这两道模拟题，我们不仅实践了模拟技巧，还掌握了如何通过细致的操作和逐步验证来解决复杂问题。希望本篇博客能为大家提供解决此类题目的一些启发，提升在算法与编程上的实战能力。


http://www.kler.cn/a/539681.html

相关文章：

  • Json-RPC框架项目(一)
  • redis底层数据结构——简单动态字符串
  • 在 Open WebUI+Ollama 上运行 DeepSeek-R1-70B 实现调用
  • 在请求时打印出实际代理的目标地址
  • R语言LCMM多维度潜在类别模型流行病学研究：LCA、MM方法分析纵向数据
  • Python分享20个Excel自动化脚本
  • git连接——问题
  • 第3章 使用 Vue 脚手架
  • 搜索插入位置：二分查找的巧妙应用
  • 【0401】Postgres内核 CREATE DATABASE database-name 源码实现 ①
  • 65【服务器攻击原理讲解】
  • 大模型赋能网络安全整体应用流程概述
  • c/c++蓝桥杯经典编程题100道（14）矩阵转置
  • 水上安全杂志水上安全杂志社水上安全编辑部2024年第24期目录
  • 51单片机俄罗斯方块计分函数
  • SpringBoot 01 简单介绍与应用
  • ZooKeeper 和 Dubbo 的关系：技术体系与实际应用
  • 如何在 Linux 上为 SSH 启用 MFA（Google Authenticator 方式）
  • C++ Primer sizeof运算符
  • 金字塔原理——阅读笔记
  • 微服务 day01 注册与发现 Nacos OpenFeign
  • Perl语言的云计算
  • idea启动报错# EXCEPTION_ACCESS_VIOLATION (0xc0000005) at pc=0x00007ffccf76e433
  • VueRouter 的路由匹配与组件渲染
  • JUnit 5 TestInstanceFactory 功能与使用详解
  • 第二十二章：游戏结缘与现实的相遇