【蓝桥真题5】带三百人训练了十天精选蓝桥真题，看看他们都练些什么（三门语言题解）
source link: https://blog.51cto.com/u_15492302/6852392
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
⭐️引言⭐️
大家好啊，我是执梗。最近一周多都没有更新文章了，因为确实是非常忙，在上篇文章了一下开启了蓝桥打卡31日的活动。每天忙着群里管理解答，统计打卡，寻找真题，根本没有时间更新文章。每天也过的非常的累，这篇文章也是断断续续写了几天，这次也是将这段时间训练的真题总结了一下，还请大家多多支持。
讲解的题目大多都是这星期内训练营内每日训练的题目，因为我是Java语言实现的，当然群内也有各种语言非常多的大佬写的题解，后面我也会附上他们的链接，大家可以去看看他们的优质题解。包括JAVA、C++、Python都有（很多都是这几天的热榜文😂）
⭐️目录⭐️
🌸1.等差数列
🍀 2.买不到的数目
🌺 3.连号区间数
🍁4.递增三元组
🍃5.回文日期
🍂6.全球变暖
🍄7.数的幂次
🌵8.最大乘积
🌴9.含二天数
🌰 10.积木大赛
🚀11.大佬候选区（三门语言大佬题解可供选择）
🌸1.等差数列
数学老师给小明出了一道等差数列求和的题目。但是粗心的小明忘记了一 部分的数列，只记得其中 N 个整数。
现在给出这 N 个整数，小明想知道包含这 N 个整数的最短的等差数列有几项？
题目链接： 等差数列
输入输入可在题目链接查看
等差数列，大家高中做烂了的题目。相信大家光看题目还是很兴奋的吧哈哈哈，感觉非常简单，但是还是有一些需要注意的细节。首先拿到这道题目要明白和想清楚下面几个点
- 给定的序列是不是有序的？我们需不需要排序？
- 为了保证等差数列尽可能短，我们应该如何去确定公差？
首先对于第一个问题，不言而喻我们肯定是需要先对接收到的数组进行排序。因为等差数列本身就是一个递增序列。其次思考第二个问题，如何保证数列尽可能短？思考这个问题前我们可以先思考如何让数组尽可能的长？理所当然，如果公差为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组合出来。
本题的要求就是在已知两个包装的数量时，求最大不能组合出的数字。题目链接： 买不到的数目
这题考察的是数论的知识——对于互质的两个数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变大的时候，问题就不是那么简单了，现在小明需要你的帮助。题目链接： 连号区间数
这道题唯一的核心就是：如何保证一个子数组是一个公差为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题目链接： 递增三元组
这道题的要求我们分别从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;
}
}🍃5.回文日期
题目链接： 回文日期
一道代码量比较大的模拟题，考察的又是时间的处理，这里我同样套用之前蓝桥真题中讲过的日期模拟模板。模拟能力是一项考察算法能力很基础的一项，一旦代码量一大许多同学就会在各种地方出现问题，而且由于代码量大能以发现问题。如果能AC这题相信对你的模拟能力有很大的提升，我们直接来看代码转换：
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
static int[] M={0,31,28,31,30,31,30,31,31,30,31,30,31};
static int a;
static int b;
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
List<Integer> list=new ArrayList<>();
while(n!=0) {
list.add(0,n%10);
n/=10;
}
int y=list.get(0)*1000+list.get(1)*100+list.get(2)*10+list.get(3);
int m=list.get(4)*10+list.get(5);
int d=list.get(6)*1+list.get(7);
boolean flag1=true;
boolean flag2=true;
String anser1="";
String anser2="";
while(flag1||flag2) {
if(y%400==0||(y%4==0&&y%100!=0)) {
M[2]=29;
}else {
M[2]=28;
}
d++;
if(d>M[m]) {
d=1;
m++;
}
if(m>12) {
m=1;
y++;
}
if(check1(y,m,d)&&flag1) {
anser1=test(y,m,d);
flag1=false;
}
if(check2(y,m,d)&&flag2) {
anser2=test(y,m,d);
flag2=false;
}
}
System.out.println(anser1);
System.out.println(anser2);
}
static boolean check1(int y,int m,int d) {
String sb=test(y,m,d);
int n=sb.length();
int l=0;
int r=n-1;
while(l<r) {
if(sb.charAt(l++)!=sb.charAt(r--)) return false;
}
return true;
}
static boolean check2(int y,int m,int d) {
String sb=test(y,m,d);
char a1=sb.charAt(0);
char b1=sb.charAt(1);
char c1=sb.charAt(2);
char d1=sb.charAt(3);
char e1=sb.charAt(4);
char f1=sb.charAt(5);
char g1=sb.charAt(6);
char h1=sb.charAt(7);
return a1!=b1&&a1==c1&&c1==f1&&f1==h1&&b1==d1&&d1==e1&&e1==g1;
}
static String test(int y,int m,int d) {
StringBuilder sb=new StringBuilder();
sb.append(y);
if(m<10) {
sb.append("0"+m);
}else {
sb.append(m);
}
if(d<10) {
sb.append("0"+d);
}else {
sb.append(d);
}
return sb.toString();
}
}🍂6.全球变暖
你有一张某海域NxN像素的照片，"."表示海洋、"#"表示陆地，如下所示：
.......
.##....
.##....
....##.
..####.
...###.
.......
其中"上下左右"四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有2座岛屿。
由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)，它就会被淹没。
例如上图中的海域未来会变成如下样子：
.......
.......
.......
.......
....#..
.......
.......
请你计算：依照科学家的预测，照片中有多少岛屿会被完全淹没。题目链接： 全球变暖
题目可以用深搜和广搜来做，我们套模板即可。深搜和广搜的重要性不言而喻，这道题大家拿来练手是非常合适的。无论是深搜还是广搜，每次我们遍历一个岛屿时，都要判断这个岛屿是否存在上下左右都是陆地的的陆地。这里要注意的是由于深搜会进行栈递归，在最后一个大数据的情况下会爆栈，而广搜就没有这个问题。下面贴上两种代码
深度优先搜索：
import java.util.Scanner;
public class Main {
static int[] dx= {1,-1,0,0};
static int[] dy= {0,0,1,-1};
static boolean[][] visit;
static int ans=0;
static boolean flag=false;
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
char[][] arr=new char[n][n];
for(int i=0;i<n;++i) {
arr[i]=sc.next().toCharArray();
}
visit=new boolean[n][n];
for(int i=0;i<n;++i) {
for(int j=0;j<n;++j) {
if(arr[i][j]=='#'&&!visit[i][j]) {
dfs(arr,i,j);
if(!flag) ans++;
flag=false;
}
}
}
System.out.println(ans);
}
static void dfs(char[][] arr,int a,int b) {
if(check(arr,a+dx[0],b+dy[0])&&check(arr,a+dx[1],b+dy[1])&&check(arr,a+dx[2],b+dy[2])&&check(arr,a+dx[3],b+dy[3])) {
flag=true;
}
visit[a][b]=true;
for(int i=0;i<4;++i) {
int newX=a+dx[i];
int newY=b+dy[i];
if(arr[newX][newY]=='#'&&!visit[newX][newY]) dfs(arr,newX,newY);
}
}
static boolean check(char[][] arr,int i,int j) {
return arr[i][j]=='#';
}
}宽度优先搜索：
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
static int[] dx= {1,-1,0,0};
static int[] dy= {0,0,1,-1};
static boolean[][] visit;
static int ans=0;
static boolean flag=false;
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
char[][] arr=new char[n][n];
for(int i=0;i<n;++i) {
arr[i]=sc.next().toCharArray();
}
visit=new boolean[n][n];
for(int i=0;i<n;++i) {
for(int j=0;j<n;++j) {
if(arr[i][j]=='#'&&!visit[i][j]) {
Queue<int[]> queue=new LinkedList<>();
queue.offer(new int[] {i,j});
visit[i][j]=true;
dfs(arr,queue);
if(!flag) ans++;
flag=false;
}
}
}
System.out.println(ans);
}
static void dfs(char[][] arr,Queue<int[]> queue) {
while(!queue.isEmpty()) {
int size=queue.size();
while(size-->0) {
int[] curr=queue.poll();
int a=curr[0];
int b=curr[1];
if(check(arr,a+dx[0],b+dy[0])&&check(arr,a+dx[1],b+dy[1])&&check(arr,a+dx[2],b+dy[2])&&check(arr,a+dx[3],b+dy[3])) {
flag=true;
}
for(int i=0;i<4;++i) {
int newX=a+dx[i];
int newY=b+dy[i];
if(arr[newX][newY]=='#'&&!visit[newX][newY]){
visit[newX][newY]=true;
queue.offer(new int[] {newX,newY});
}
}
}
}
}
static boolean check(char[][] arr,int i,int j) {
return arr[i][j]=='#';
}
}🍄7.数的幂次
题目链接： 数的幂次
考察快速幂的考点，这个考点还是比较重要且常考的。大家可以直接通过快速幂函数的公式套进去即可。大家复制下来背下来直接食用即可，类似gcd一样。
import java.io.*;
import java.util.*;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StreamTokenizer st = new StreamTokenizer(br);
static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
public static void main(String[] args)throws Exception {
int t=nextInt();
while(t-->0) {
int n=nextInt();
int m=nextInt();
int p=nextInt();
out.write(check(n,m,p)+"\n");
}
out.flush();
}
//快速幂函数，赋值照用即可
static long check(long a,int k,int p) {
long res=1;
while(k>0) {
//这样判断k的二进制最后一位是否是1
if((k&1)==1) res=res*a%p;
k>>=1;
a=(long)a*a%p;
}
return res;
}
// 读入整形（一个）
public static int nextInt() throws Exception {
st.nextToken();
return (int) st.nval; // nval 读入的是 double 类型
}
// 读取字符串（一个）
// 若读入的不是字符串，会 null
public static String nextStr() throws Exception {
st.nextToken();
return st.sval;
}
}🌵8.最大乘积
题目链接： 最大乘积
还是全排列的问题，但是这里我们需要去考虑插入乘号的位置。乘号可以放在第一个数字之后，或者最后一个数字之前。然后我们去判断乘积是否符合数字1~9的排列情况，如果符合就在已保存的值中取更大值。大家最好把每一段的逻辑抽成一个方法去写，这样出错我们可以更容易的去排错。
import java.util.HashSet;
import java.util.Set;
public class 最大乘积 {
static int max=0;
static int[] arr= {1,2,3,4,5,6,7,8,9};
public static void main(String[] args) {
dfs(0);
System.out.println(max);
}
//全排列
static void dfs(int k) {
if(k==9) {
check();
return;
}
for(int i=k;i<arr.length;++i) {
exch(i,k);
dfs(k+1);
exch(i,k);
}
}
//插入乘号位置
static void check() {
for(int i=1;i<=8;++i) {
int a=test(arr,i);
if(isOk(a)) {
max=Math.max(a,max);
}
}
}
//获取乘积
static int test(int[] arr,int k) {
int pre=0;
int count1=0;
while(k-->0) {
count1=count1*10+arr[pre];
pre++;
}
int count2=0;
for(int i=pre;i<arr.length;++i) {
count2=count2*10+arr[i];
}
return count1*count2;
}
//判断答案是否有且仅包含1~9
static boolean isOk(int n){
Set<Integer> set=new HashSet<>();
for(int i=1;i<=9;++i) set.add(i);
while(n!=0) {
int a=n%10;
if(!set.contains(a)) return false;
else set.remove(a);
n/=10;
}
return set.size()==0;
}
//交换函数
static void exch(int a,int b) {
int tmp=arr[a];
arr[a]=arr[b];
arr[b]=tmp;
}
}🌴9.含二天数
小蓝特别喜欢 22，今年是公元 2020 年，他特别高兴，因为每天日历上都可以看到 22。
如果日历中只显示年月日，请问从公元 1900 年 1 月 1 日到公元 99 年 12 月 31 日，一共有多少天日历上包含 22。即有多少天中年月日的数位中包含数字 2。
题目： 含2天数
还是同样的日期问题，调用我们的日期模板直接秒杀即可！
代码转换：
public class 含2天数 {
static int[] M= {0,31,28,31,30,31,30,31,31,30,31,30,31};
public static void main(String[] args) {
int ans=0;
int y=1900,m=1,d=1;
//先升日期再升值
while(y!=9999||m!=12||d!=31) {
if(y%400==0||(y%4==0&&y%100!=0)){
M[2]=29;
}else {
M[2]=28;
}
d++;
if(d>M[m]) {
m++;
d=1;
}
if(m>12) {
m=1;
y++;
}
if(check(y,m,d)) {
ans++;
}
}
System.out.println(ans);
}
static boolean check(int y,int m,int d) {
while(y!=0) {
if(y%10==2) return true;
y/=10;
}
while(m!=0) {
if(m%10==2) return true;
m/=10;
}
while(d!=0) {
if(d%10==2) return true;
d/=10;
}
return false;
}
}🌰 10.积木大赛
题目链接： 积木大赛
题目的本质是贪心。对于增加操作，我们也可以理解成将数组所有元素减到0的最少操作次数。我们可以将原数组分为n个递增的子数组，a[0,i],a[i+1,j],a[j+1,k]....。答案就是每段递增子序列的最大值减去除去第一段的每段的最小值之和。
代码转换：
import java.util.Scanner;
public class 积木大赛 {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int ans=0,last=0;
for(int i=0;i<n;++i) {
int a=sc.nextInt();
if(a>last) ans+=(a-last);
last=a;
}
System.out.println(ans);
}
}Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK