【蓝桥真题5】带三百人训练了十天精选蓝桥真题，看看他们都练些什么（三门语言题解）（上）

2022-05-22 140

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 【蓝桥真题5】带三百人训练了十天精选蓝桥真题，看看他们都练些什么（三门语言题解）

🌸1.等差数列

数学老师给小明出了一道等差数列求和的题目。但是粗心的小明忘记了一部分的数列，只记得其中 N 个整数。

现在给出这 N 个整数，小明想知道包含这 N 个整数的最短的等差数列有几项？

题目链接：等差数列https://www.lanqiao.cn/problems/192/learning/

输入输入可在题目链接查看

等差数列，大家高中做烂了的题目。相信大家光看题目还是很兴奋的吧哈哈哈，感觉非常简单，但是还是有一些需要注意的细节。首先拿到这道题目要明白和想清楚下面几个点

给定的序列是不是有序的？我们需不需要排序？

为了保证等差数列尽可能短，我们应该如何去确定公差？

首先对于第一个问题，不言而喻我们肯定是需要先对接收到的数组进行排序。因为等差数列本身就是一个递增序列。其次思考第二个问题，如何保证数列尽可能短？思考这个问题前我们可以先思考如何让数组尽可能的长？理所当然，如果公差为1，长度就是数列中的最大值减去最小值了。反过来，为了数列尽可能短，我们得让公差尽可能大！但是我们必须保证所有的数字都属于这个等差数列，于是我们可以去获取排序后的数组所有相邻两相的差，然后得到这堆差的最大公因数。这样就最大程度地保证了所有的数字一定可以成为这个等差数列的项且尽可能地少增加数字，这样就能使等差数列尽可能短。

答案就用数组中的最大值减去最小值然后除以差值的最大公约数，然后+1（因为还得加上数列中最小的元素），当然我们需要对公差为0的情况进行特判，不然会出现除零异常。如果不太理解的建议草稿纸演示一遍非常容易搞懂。

让我们来看看代码实现：

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];
        for(int i=0;i<n;++i) arr[i]=sc.nextInt();
        //一定要先对数组进行排序
        Arrays.sort(arr);
        //先赋值为第一个相邻差值
        int cut=arr[1]-arr[0];
        for(int i=2;i<n;++i){
            //不断通过gcd公式获得最大公约数
            cut=gcd(cut,arr[i]-arr[i-1]);
        }
        //这里一定要特判公差为0的情况，否则下面会出现除零异常
        if(cut==0){
             System.out.println(n);
        }else
        //注意这里要加+1。因为前面获取的值不包括数列中最小的值
        System.out.println((arr[n-1]-arr[0])/cut+1);
    }
    //获取a和b的最大公约数，不了解的可以看前面的蓝桥真题
    static int gcd(int a,int b){
        return b==0?a:gcd(b,a%b);
    }
}

🍀 2.买不到的数目

　小明开了一家糖果店。他别出心裁：把水果糖包成4颗一包和7颗一包的两种。糖果不能拆包卖。

小朋友来买糖的时候，他就用这两种包装来组合。当然有些糖果数目是无法组合出来的，比如要买 10 颗糖。

你可以用计算机测试一下，在这种包装情况下，最大不能买到的数量是17。大于17的任何数字都可以用4和7组合出来。

本题的要求就是在已知两个包装的数量时，求最大不能组合出的数字。

题目链接：买不到的数目http://lx.lanqiao.cn/problem.page?gpid=T2917

这题考察的是数论的知识——对于互质的两个数a和b，其不能组成的最大整数为a*b-a-b。

这里不展开讲具体的证明，有兴趣的可以上网了解，结论很简单，大家记住就好。

注意这里a和b一定得是互质的，否则是无解的。题目给你的例子也肯定是会互相为质数的，除非题目有说若无解则输出-1。当然这题也可以暴力去求解一下。

import java.util.Scanner;
public class Main {
  public static void main(String[] args) {
  Scanner sc=new Scanner(System.in);
  int n=sc.nextInt();
  int m=sc.nextInt();
  System.out.println(n*m-n-m);
  }
}

🌺 3.连号区间数

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

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

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

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

题目链接：连号区间数http://lx.lanqiao.cn/problem.page?gpid=T2926

这道题唯一的核心就是：如何保证一个子数组是一个公差为1的等差数列。

我们要明白一个性质。对于数组arr一段子数组[i,j]，如果这段序列最大值为max，最小值为min。如果max-min==j-i，那么说明这段子数组就是一段公差为1的等差数列。

所以对于每一段子数组，我们可以去遍历获得它的最大值和最小值，然后判断它们的差值是否等于下标差。

直接看代码即可，理解了原理就非常简单：

import java.util.Scanner;
public class Main { 
  public static void main(String[] args) {
  Scanner sc=new Scanner(System.in);
  int n=sc.nextInt();
  int[] arr=new int[n];
  for(int i=0;i<n;++i) arr[i]=sc.nextInt();
  int ans=0;
  for(int i=0;i<n;++i) {
    int max=arr[i];
    int min=arr[i];
    for(int j=i;j<n;++j) {
    max=Math.max(max, arr[j]);
    min=Math.min(min,arr[j]);
    if(max-min==j-i) ans++;
    }
  }
  System.out.println(ans);
  }
}

🍁4.递增三元组

给定三个整数数组

A = [A1, A2, ... AN],

B = [B1, B2, ... BN],

C = [C1, C2, ... CN]，

请你统计有多少个三元组(i, j, k) 满足：

1. 1 <= i, j, k <= N

2. Ai < Bj < Ck

题目链接：递增三元组http://lx.lanqiao.cn/problem.page?gpid=T2728

这道题的要求我们分别从A,B,C找出三个数。保证A[i]<B[j]<C[k]。但是对ijk三者的关系并没有要求。所以由此我们首选可以想到去排序。那我们应该去排序哪些数组呢？ABC全都排序吗？没有必要！我们只需要对AC数组进行排序，然后去遍历B数组即可。通过二分查找从A数组找到小于B[i]的最大值下标，从C数组找到大于B[i]的最小值下标。这样就能获得A组中小于B[i]的个数和C组中大于B[i]的个数。两者一相乘就是选择B[i]情况下能组成递增三元组的数目，以此遍历一遍B数组即可获得答案。

代码转换：

import java.util.Arrays;
import java.util.Scanner;
public class Main {
  public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[] A=new int[n];
        int[] B=new int[n];
        int[] C=new int[n];
        for(int i=0;i<n;++i) {
            A[i]=sc.nextInt();
        }
        for(int i=0;i<n;++i) {
            B[i]=sc.nextInt();
        }
        for(int i=0;i<n;++i) {
            C[i]=sc.nextInt();
        }
        //只需要对AC排序即可
        Arrays.sort(A);
        Arrays.sort(C);
        long ans=0;
        //遍历一遍B数组
        for(int i=0;i<n;++i) {
            int a=test2(A,B[i]);
            //-1的情况说明没有符合的元素，则B[i]无法构成递增三元组
            //直接continue
            if(a==-1) continue;
            int b=test1(C,B[i]);
            if(b==-1) continue;
            //这里是特别容易出错的地方。
            ans+=(long)(a+1)*(n-b);
        }
        System.out.println(ans);
    }
    //从C数组中找到第一个大于target的元素的下标
    static int test1(int[] arr,int target) {
        if(arr[arr.length-1]<=target) return -1;
        int l=0;
        int r=arr.length-1;
        while(l<r) {
            int mid=(l+r)>>1;
            if(arr[mid]<=target) l=mid+1;
            else r=mid;
        }
        return l;
    }
    //从A数组中找到一个小于target的最大数
    static int test2(int[] arr,int target) {
        if(arr[0]>=target) return -1;
        int l=0;
        int r=arr.length-1;
        while(l<r) {
            int mid=(l+r+1)>>1;
            if(arr[mid]>=target) r=mid-1;
            else l=mid;
        }
        return l;
    }
}