蓝桥模拟赛
💐今日学习💐
目录
🎈第一题
🎯问题描述:
以下是一个 25 行 25 列的字母矩阵，全部由字母 A 和 B 组成。
AAAAAAABABBAABABABAAAAAAA
ABBBBBABBAABBBBBABABBBBBA
ABAAABABBBABAABBBBABAAABA
ABAAABABBBBBAABAABABAAABA
ABAAABABBABABBABABABAAABA
ABBBBBABBBABAABBBBABBBBBA
AAAAAAABABABABABABAAAAAAA
BBBBBBBBABAABABBBBBBBBBBB
AABAABABBAAABBAAABABBBBBA
ABBABABBBABBAAAABBBBAAAAB
BBBBAAABABAABABAABBBAABBA
BBAABABABAAAABBBAABBAAAAA
ABABBBABAABAABABABABBBBBA
AAAABBBBBABBBBAAABBBABBAB
AABAABAAABAAABAABABABAAAA
ABBBBBBBBABABBBBABAABBABA
ABBBAAABAAABBBAAAAAAABAAB
BBBBBBBBABBAAABAABBBABBAB
AAAAAAABBAAABBBBABABAABBA
ABBBBBABBAABABAAABBBABBAA
ABAAABABABBBAAAAAAAAAABAA
ABAAABABABABBBABBAABBABAA
ABAAABABBABBABABAABAABAAA
ABBBBBABABBBBBABBAAAABAAA
AAAAAAABAABBBAABABABBABBA
请问在这个矩阵中有多少个字母A？
package 模拟赛;
import java.util.Scanner;
/**
* @author yx
* @date 2022-03-23 13:23
*/
public class 第一题 {
public static void main(String[] args) {
int ans=0;
char [][]A=new char[25][25];
Scanner scanner = new Scanner(System.in);
for (int i = 0; i < 25; i++) {
String s=scanner.next();
for (int j = 0; j < 25; j++) {
A[i][j]=s.charAt(j);
if(A[i][j]=='A'){
ans++;
}
}
}
System.out.println(ans);
}
}
🎃题解分析：
（1）这个题目没啥好说的，懂得都懂，直接暴搜，白给题
🎈第二题
🎯问题描述:
如果一个整数的某个数位包含 2 ，则称这个数为一个“最2数字”。例如：102、2021 都是最2数字。
请问在 1（含） 到 2021（含） 中，有多少个最2数字。
package 模拟赛;
import javax.xml.transform.sax.SAXTransformerFactory;
/**
* @author yx
* @date 2022-03-23 13:38
*/
public class 第二题 {
static int ans=0;
public static void main(String[] args) {
for (int i = 1; i <=2021 ; i++) {
check(i);
}
System.out.println(ans);
}
static boolean check(int n){
int temp;
for (int i = 0; i < 4; i++) {
temp=n%10;
if(temp==2){
ans++;
return true;
}
n/=10;
}
return false;
}
}
🎃题解分析：
（1）首先写一个check（int n）函数用来判断n是否是符合要求的int型数字
（2）再然后就是从1到2021用check函数遍历过去就好，用ans记录答案
🎈第三题
有一个整数 A=2021，每一次，可以将这个数加 1 、减 1 或除以 2，其中除以 2 必须在数是偶数的时候才允许。
例如，2021 经过一次操作可以变成 2020、2022。
再如，2022 经过一次操作可以变成 2021、2023 或 1011。
请问，2021 最少经过多少次操作可以变成 1。
package 模拟赛;
import java.util.LinkedList;
import java.util.Queue;
public class 第三题_ {
public static void main(String[] args) {
Queue<Integer> q = new LinkedList<>();
int ans = 0;
boolean[] A = new boolean[10000];
q.offer(2021);
A[2021]=true;
int i;
while (!q.isEmpty()) {
for (int j = q.size(); j >0 ; j--) {
//for(int j=0;j<q.size(),j++)注意q.size()的值不是一个定值，在循环过程中会发生变化
i = q.poll();
if (i == 1) {
System.out.println(ans);
return;
}
if (!A[i + 1]) {
A[i + 1] = true;
q.offer(i + 1);
}
if (!A[i - 1]) {
A[i - 1] = true;
q.offer(i - 1);
}
if (!A[i / 2] && i % 2 == 0) {
A[i / 2] = true;
q.offer(i / 2);
}
}
ans++;
}
}
}🎃题解分析：
（1）题目问的是最少次数，其实我们仔细想想就会发现这个其实就是最短路径问题
（2）最短路径问题我们用的是BFS，与BFS相关的数据结构我们要马上想到是队列
（3）我们分析一下上图，首先我们把2021放入队列中，然后给队列头2021进行poll（去队列头，并删除该队列头），并按题目要求进行+1、-1、/2操作得到2022、2020，这个时候把2022、2020又放入队列中（上图中每一行的元素在同一个队列），重复操作，当队列中出现1时输出次数（这个时候一定是操作次数最少的）
（4）注意事项：我们要对每一个入队的元素进行标记（使用boolean数组），避免重复冗余操作，优化复杂度
🎈第四题
🎯问题描述:
对于一个 n 行 m 列的表格，我们可以使用螺旋的方式给表格依次填上正整数，我们称填好的表格为一个螺旋矩阵。
例如，一个 4 行 5 列的螺旋矩阵如下：
1 2 3 4 5
14 15 16 17 6
13 20 19 18 7
12 11 10 9 8
请问，一个 30 行 30 列的螺旋矩阵，第 20 行第 20 列的值是多少？
package 模拟赛;
import java.util.zip.DeflaterOutputStream;
/**
* @author yx
* @date 2022-03-23 13:59
*/
public class 第四题 {
static int [][]A=new int[30][30];
public static void main(String[] args) {
generateMatrix(30);
System.out.println(A[19][19]);
}
static public void generateMatrix(int n) {
int t = 0,l = 0;//上边界和左边界
int b=n-1,r = n - 1;//下边界和右边界
int num=1;
while (num<n*n){
for (int i = l; i <=r ; i++) {//在tpo层从左到右遍历赋值
A[t][i]=num++;
}t++;//最上层遍历后，以倒数第二层为顶层
for (int i = t; i <=b ; i++) {//在r层从上到下遍历赋值
A[r][i]=num++;
}r--;//最右层遍历后以倒数第二右层为最右层
for (int i = r; i >=l ; i--) {//在b层从右到左遍历赋值
A[b][i]=num++;
}b--;//最底层遍历后以倒数第二底层为最底层
for (int i = b; i >=t ; i--) {//在l层从下到上遍历赋值
A[i][l]=num++;
}l++;//最左层遍历后以倒数第二左层为最左层
}
}
}
🎃题解分析：
（1）这个题目，博主也是第一次做，刚开始难免会有一些蒙蔽，后面去leetcode上参考了一下各路神仙的解法，瞬间就豁然开朗
（2）首先先定义一个二维数组A用来存储所有的数据，这样子当你想知道n行m列的值时就可以直接输出A[n-1][m-1]即可
（3）接下来我们分析一下怎么螺旋存储数据，如上图所示，我们结合代码来一起分析：
t++：当我遍历完第一行时，此时第二层变为最顶层
r--：当我们遍历完最右层时，倒数第二右层变为最右层
b--：当我们遍历完最底层时，倒数第二层变为最底层
l++：当我们遍历完最左层时，倒数第二左层变为最左层
哈哈哈，是不是有种“套娃”的感觉，我们其实每遍历存储一层数据，剩下未填数字的数组大小就缩水一圈，结合图形一起就会变得非常好理解。
🎈第五题
一棵二叉树有2021个结点。该树满足任意结点的左子树结点个数和右子树的结点个数之差最多为1。
定义根结点的深度为0，子结点的深度比父结点深度多1。
请问，树中深度最大的结点的深度最大可能是多少？
🎃题解分析：
这个题目有点难搞，由于博主数据结构这块学的不够深入，所以我在这里仅阐述我的两种思路，有会做的小伙伴，欢迎私信和留言✏️！
思路一：
将该题目看成一个完全二叉树（完全二叉树肯定满足题目条件）
公式：2^(n-1)-1<=2021<=2^(n)-1，算出n=11，因为第一层深度0，所以深度为10
不过我总感觉题目没有这么简单，下面来说一下思路二。
思路二：
将该题目看成一个平衡二叉树的题目来做，对于平衡二叉树博主掌握的不是很到位，详情可以参考这篇博客：
关于平衡二叉树的地推公式请参考这篇博客：
得到公式：S(h) = S(h-1) + S(h-2) + 1 ==>算出来是15层
package 模拟赛; /** * @author yx * @date 2022-03-23 14:16 */ public class 第五题 { public static void main(String[] args) { for (int i = 0; i < 20; i++) { if ( S(i + 1) >= 2021) { System.out.println(i); return; } } } static int S(int h) { if (h == 1) return 1; if (h == 2) return 2; return S(h - 1) + S(h - 2) + 1; } }
🎈第六题
🎯问题描述:
一个和尚要挑水，每次最多能挑 a 千克，水缸最多能装 t 千克，开始时水缸为空。
请问这个和尚最少要挑多少次可以将水缸装满？输入格式
输入一行包含两个整数 a, t，用一个空格分隔。
输出格式
输出一行包含一个整数，表示答案。
样例输入
20 2021
样例输出
102
评测用例规模与约定
对于所有评测用例，1 <= a <= 100，1 <= t <= 10000。
package 模拟赛;
import java.util.Scanner;
/**
* @author yx
* @date 2022-03-23 14:37
*/
//送分题
public class 第六题 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int a=scanner.nextInt();
int t=scanner.nextInt();
if(t%a==0){
System.out.println(t/a);
return;
}
System.out.println(t/a+1);
}
}
🎃题解分析：
这道题目直接白给，就不讲了哈！
🎈第七题
🎯问题描述:
在金融领域，通常将金额的百位和千位之间、十万位和百万位之间增加逗号（千分位分隔符），以方便阅读。一般从个位开始，每三位之前增加一个逗号。
例如：1234567890.00 通常写成 1,234,567,890.00。
注意小数点后固定保留 2 位。
给定一个包含千分位分隔符的数值，请读入后输出对应的不含千分位的数值，小数点仍然保留 2 位。输入格式
输入一行包含一个由千分位分隔符的数值，恰好有 2 位小数。
输出格式
输出不含千分位分隔符的数值，保留 2 位小数。
样例输入
1,234,567,890.00
样例输出
1234567890.00
评测用例规模与约定
对于所有评测用例，给定的数值整数部分不超过12位。
package 模拟赛;
import java.util.Scanner;
/**
* @author yx
* @date 2022-03-23 14:40
*/
//字符数组转字符串的两种方法
// String string1 = new String(str);
// String string2 = String.valueOf(str);
// String s1=new String(B);
// System.out.println(s1);
/**
* 一、创建Stringbuilder对象
* StringBuilder strB = new StringBuilder();
* 1、append(String str)/append(Char c)：字符串连接
* System.out.println(“StringBuilder:”+strB.append(“ch”).append(“111”).append(‘c’));
* //return “StringBuilder:ch111c”
*/
public class 第七题 {
public static void main(String[] args) {
/*
写法1、
*/
// Scanner scanner = new Scanner(System.in);
// String s=scanner.next();
// char []A=s.toCharArray();
// char []B=new char[A.length];
// int j=0;
// for (int i = 0; i <A.length; i++) {
// if(A[i]!=','){
// B[j]=A[i];
// j++;
// }
// }
// for (int i = 0; i <j; i++) {
// System.out.print(B[i]);
// }
/*
写法2、
*/
Scanner scanner = new Scanner(System.in);
StringBuilder s=new StringBuilder();
char[]A=scanner.next().toCharArray();
for (int i = 0; i < A.length; i++) {
if(A[i]!=','){
s.append(A[i]);
}
}
System.out.println(s);
}
}
🎃题解分析：
（1）这个题目暂时想到有两种写法
写法一：
将输入进来的字符串直接转字符数组，然后把‘，’给去掉，存入另外一个字符数组中，最后输出
写法二：（参考了执梗的题解：）
主要是利用StringBuilder将字符/字符串连接成字符串，用法如下：
StringBuilder strB = new StringBuilder();
append(String str)/append(Char c)：字符串连接
System.out.println(“StringBuilder:”+strB.append(“ch”).append(“111”).append(‘c’));
//return “StringBuilder:ch111c”
🎈第八题
🎯问题描述:
小蓝有一个插板，形状用一个 n * m 的01矩阵表示，0 表示板面，1 表示插孔。
小蓝还有一个插头，形状用一个 r * c 的01矩阵表示，0 表示没有伸出的部分，1 表示伸出的部分。插头伸出的部分必须插在插孔里面。
为了安全，插头插到面板上不能有任何部分超过插板边界（包括没有伸出的部分）。
插头和插板都不能旋转，也不能翻转。请求出插头插入插板的合理位置。输入格式
输入的第一行包含两个整数 n, m。
接下来 n 行，每行一个长度为 m 的01串，表示插板的形状。
接下来一行包含两个整数 r, c。
接下来 r 行，每行一个长度为 c 的01串，表示插头的形状。输出格式
如果插头没办法安全插入插板中，输出“NO”。否则输出两个数 a, b，表示插头的第 1 行第 1 列对应插板的第 a 行第 b 列。如果有多种情况满足要求，输出 a 最小的方案，如果 a 最小的方案有多个，输出在 a 最小的前提下 b 最小的方案。
样例输入
3 4
0110
0000
0000
3 3
000
010
000样例输出
NO
样例说明
在插头不超出范围的前提下无法插入。
样例输入
4 7
1110100
1101111
0001111
0000011
2 3
111
011样例输出
2 4
评测用例规模与约定
对于 50% 的评测用例，2 <= n, m, r, c <= 20。
对于所有评测用例，2 <= n, m, r, c <= 100。
package 模拟赛;
import java.util.*;
/**
* @author yx
* @date 2022-03-24 21:14
*/
public class 第八题 {
static class Node{
int x,y;
public Node(int x,int y){
this.x=x;
this.y=y;
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n=scanner.nextInt();
int m=scanner.nextInt();
char A[][]=new char[n][m];
for (int i = 0; i <n ; i++) {
String s=scanner.next();
for (int j = 0; j <m ; j++) {
A[i][j]=s.charAt(j);
}
}
int r=scanner.nextInt();
int c=scanner.nextInt();
if (r > n || c > m) {
System.out.println("NO");
return;
}
char [][]B=new char[r][c];
ArrayList<Node> list=new ArrayList<>() ;//用来存插座的坐标值
for (int i = 0; i <r ; i++) {
String s1=scanner.next();
for (int j = 0; j <c ; j++) {
B[i][j]=s1.charAt(j);
if(B[i][j]=='1'){
list.add(new Node(i,j));
}
}
}
for (int i = 0; i <n ; i++) {
for (int j = 0; j <m ; j++) {
if(A[i][j]=='1'&&i-list.get(0).x>=0&&j-list.get(0).y>=0){//判断(i,j)是否为插头对应的插板的起始位置
boolean isTrue=true;
for (int k = 1; k <list.size() ; k++) {//判断以(i,j)为起始位置是否符合要求
if(j+(list.get(k).y -list.get(0).y)<m&&i+(list.get(k).x -list.get(0).x)<n&&A[i+(list.get(k).x -list.get(0).x)][j+(list.get(k).y -list.get(0).y)]!='1'){
isTrue=false;
break;
}
}
if(isTrue){
System.out.print(i+1+" ");
System.out.print(j+1);
return;
}
}
}
}
System.out.println("NO");
}
}
🎃题解分析：
（1）首先就是先接收输入的数据了，用A和B数组分别存储插座和插头
（2）如果插头的大小大于插座那就直接PASS输出“NO”
（3）我们定义一个Node类用来存储插头伸出部分的坐标（x,y）
（4）使用Node类型的List集合 将插头深处部分的坐标全部都存储进去
（5）遍历插座的数组，从第一个出现的‘1’伸出部分开始，判断该点是否为插头对应插板的起始位置
（6）对该位置进行遍历
if(j+(list.get(k).y -list.get(0).y)<m&&i+(list.get(k).x -list.get(0).x)<n&&A[i+(list.get(k).x -list.get(0).x)][j+(list.get(k).y -list.get(0).y)]!='1')我解释一下这行代码，将插头的每一个相对位置（相对于第一个伸出位置），加在当前 插板的起始位置上，判断是否他们是否插座的头与插座的空两两对其，并且还要保证不会照成插排数组越界
🎈第九题
🎯问题描述:
给定正整数 a, b, c，请问有多少个正整数，是其中至少两个数的约数。
输入格式
输入一行包含三个正整数 a, b, c。
输出格式
输出一行包含一个整数，表示答案。
样例输入
30 70 35
样例输出
6
样例说明
1、2、5、7、10、35满足条件。
评测用例规模与约定
对于 50% 的评测用例，1 <= a, b, c <= 1000000。
对于所有评测用例，a, b, c 不超过 10**12（10的12次方）。
package 模拟赛;
import java.util.HashMap;
import java.util.Scanner;
/**
* @author yx
* @date 2022-03-24 22:49
*/
/**
* hashmap不能使用基本数据类型,即int==>Integer、long==>Long
*/
public class 第九题 {
static int ans=0;
static HashMap<Long,Long> map=new HashMap<>();
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
long a=scanner.nextInt();//注意abc的取值是long型
long b=scanner.nextInt();
long c=scanner.nextInt();
A(a);
A(b);
A(c);
System.out.println(ans);
}
static void A(long n){
for (long i = 1; i <n/i ; i++) {//求约数采用两边夹的方法，减小了时间复杂度
if(n%i==0) {//判断是否是约数
if (!map.containsKey(i)) {
map.put(i, 1L);
}
if (!map.containsKey(n/i)) {
map.put(n / i, 1L);
}
if (map.containsKey(i)) {
map.put(i, map.get(i)+1);
if(map.get(i)==2){
ans++;
}
}
if (map.containsKey(n/i)) {
map.put(i, map.get(n/i)+1);
if(map.get(n/i)==2){
ans++;
}
}
}
}
}
}
🎃题解分析：
（1）这个题目虽然放在第九题，但不是很难，听博主细细道来
（2）我们使用HashMap将a,b,c的所有约数都存进去，key值为约数，value值为该约数出现的次数，我们定义一个ans记录答案，当约数出现了两次时我们就将它视为符合题目要求的约数，ans++
（3）求约数的快速方法，两端往中间夹，可以优化一半的时间复杂度
🎉写在最后
博主最近看到一段话，感触颇深，送给大家：
“人生就是这样，你想得到就必须要付出
付出了还需要学会坚持，任何人的成功都不是偶然
它装满了那些人拼搏，坚持的痕迹。”
各位有志青年，加油！！
- 点赞
- 收藏
- 关注作者
评论（0）