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

蓝桥杯·3月份刷题集训Day06

news 来源：原创 2024/4/29 22:18:01

在这里插入图片描述

本篇博客旨在记录自已打卡蓝桥杯3月份刷题集训，同时会有自己的思路及代码解答希望可以给小伙伴一些帮助。本人也是算法小白，水平有限，如果文章中有什么错误之处，希望小伙伴们可以在评论区指出来，共勉💪。

文章目录

    • 集训A
      • A1、棋盘放麦子
      • A2、等差数列
      • A3、数数
    • 集训B
      • B1、移动字母
      • B2、全球变暖
    • 集训C
      • C1、路径
      • C2、约瑟夫环
    • 最后

集训A

A1、棋盘放麦子

题目：

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

你一定听说过这个故事。国王对发明国际象棋的大臣很佩服，问他要什么报酬，大臣说：请在第 11 个棋盘格放 11 粒麦子，在第 22 个棋盘格放 22 粒麦子，在第 33 个棋盘格放 44 粒麦子，在第 44 个棋盘格放 88 粒麦子，…后一格的数字是前一格的两倍，直到放完所有棋盘格（国际象棋共有 6464 格）。

国王以为他只是想要一袋麦子而已，哈哈大笑。

当时的条件下无法准确计算，但估算结果令人吃惊：即使全世界都铺满麦子也不够用！

请你借助计算机准确地计算，到底需要多少粒麦子。

运行限制：

  • 最大运行时间：1s
  • 最大运行内存: 128M
import java.math.BigInteger;
// 1:无需package
// 2: 类名必须Main, 不可修改
/**
前言
        在Java中，由CPU原生提供的整型最大范围是64位 long 型整数。使用 long 型整数可以直接通过CPU指令进行计算，速度非常快。
        但是如果我们使用的整数范围超过了 long 型怎么办？这个时候，就只能用软件来模拟一个大整数。 java.math.BigInteger 就是用来表示任意大小的整数。 BigInteger 内部用一个 int[] 数组来模拟一个非常大的整数。
        
        常用的两种定义方式
        BigInteger a=new BigInteger("123");        //没有参数为long的构造函数，用字符串来构造
        BigInteger b=BigInteger.valueOf(123);    //静态方法，返回val对应的BigInteger
        BigInteger类中定义了四则运算的方法，add,subtract,multiply,divide。对 BigInteger 做运算的时候，只能使用实例方法。
        如：
        a=a.add(b);
    */

public class Main {
        
    public static void main(String[] args) {
        BigInteger a =new BigInteger("0");
        BigInteger b = new BigInteger("2");
        for (int i = 0; i < 64; i++) {
            a = a.add(b.pow(i));
        }
        System.out.println(a);
    }
}

A2、等差数列

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

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

输入格式：

输入的第一行包含一个整数 N。

第二行包含 N 个整数 1,2,⋅⋅⋅,*A1,A2,⋅⋅⋅,*AN。(注意 A1 ~ AN 并不一定是按等差数列中的顺序给出)

其中，2≤N≤105，0≤*Ai*≤109。

输出格式：

输出一个整数表示答案。

输入输出样例：

输入

5
2 6 4 10 20

输出

10

样例说明： 包含 2、6、4、10、20 的最短的等差数列是 2、4、6、8、10、12、14、16、 18、20。

运行限制：

  • 最大运行时间：1s
  • 最大运行内存: 256M

解题代码：

测试用例过了6/10

import java.util.Arrays;
import java.util.Scanner;

/**
 * @Descrption  2019 GCD
 * @version 等差数列
 * @author QIA27
 * @date 2023年3月31日 上午9:36:09
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc =new Scanner(System.in);
        int n = sc.nextInt();
        int [] num = new int [n];            //输入的数
        int [] cha = new int [n-1];            //数组排序后，相邻的数字最小的差值
        for (int i = 0; i < num.length; i++) {
            num[i]=sc.nextInt();
        }
        Arrays.sort(num);                    //排序
        int min = Integer.MAX_VALUE;
        for (int i = 1; i < num.length; i++) {
            cha[i-1]=num[i]-num[0];            //相邻数字的差值  
            min=Math.min(cha[i-1], min);    //min就是相邻数字最小的差值
            
        }
        for (int i = 0; i < cha.length; i++) {
            if (cha[i]%min!=0) {            //看相邻数字的最小差值是不是能整除每一个相邻数字的差值
                min=1;                        //如果不能整除，则等差值为1
                break;
            }
            
        }
        int temp=0;                            //统计最短等差数列的个数
        for (int i = num[0]; i <= num[n-1]; i+=min) {    //i+=min   按照等差值进行上升，直到从最小的数到最大的数
            temp++;
            
        }
        
         
        System.out.println(temp);
    }
}

A3、数数

题目：任何一个大于 1 的正整数都能被分解为若干个质数相乘, 比如 28=2×2×728=2×2×7 被分解为了三个质数相乘。请问在区间 [2333333, 23333333] 中有多少个正整数 可以被分解为 12 个质数相乘?

答案提交：

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一 个整数, 在提交答案时只填写这个整数, 填写多余的内容将无法得分。

运行限制：

  • 最大运行时间：1s
  • 最大运行内存: 512M
/**
 * @Descrption  2022国赛
 * @version 数数
 * @author QIA27
 * @date 2023年3月31日 上午11:12:16
 */
public class Main {
	public static void main(String[] args) {
		int count = 0;
		for( long i = 2333333; i <= 23333333; i++) {
			if (chack(i)) {
				count++;
			}
		}
		System.out.println(count);
//		System.out.println(25606);
	}
	
	private static boolean chack(long n) {
		
		int ans = 0;
		// 只需要到sqrt(n)即可，因为如果有一个因数大于等于sqrt(n)
		// 那么必定有一个因数小于等于sqrt(n)
		for (int i = 2; i <= Math.sqrt(n); i++) {
			while (n % i == 0) {
				n /= i;
				// 更新数据
				ans++;
			}
		}
		/**
		 * 比如最后的 n 为 5 的时候，n % i != 0
		 * 但是5也是这里面的一个质数
		 * 所以这个质因子5不能漏掉
		 */
		if(n > 1) ans++;
		return ans == 12;
	}
}

集训B

B1、移动字母

题目：2x3=6 个方格中放入 ABCDE 五个字母，右下角的那个格空着。如下图所示。

img

和空格子相邻的格子中的字母可以移动到空格中，比如，图中的 C 和 E 就可以移动，移动后的局面分别是：

A B

D E C

A B C

D E

为了表示方便，我们把 6 个格子中字母配置用一个串表示出来，比如上边的两种局面分别表示为：

AB*DEC

ABCD*E

题目的要求是：请编写程序，由用户输入若干表示局面的串，程序通过计算，输出是否能通过对初始状态经过若干次移动到达该状态。可以实现输出 1,否则输出 0。初始状态为：ABCDE*。

输入格式：

先是一个整数 n，表示接下来有 n 行状态。

输出格式：

程序输出 n 行 1 或 0。

输入输出样例：

输入

3
ABCDE*
AB*DEC
CAED*B

输出

1
1
0

运行限制：

  • 最大运行时间：1s
  • 最大运行内存: 256M

解题代码：

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class main {

    static String end = "ABCDE*";//初始状态
    static int[] dir = { -3, -1, 1, 3 };

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        for (int i = 0; i < n; i++) {
            String start = scanner.next();
            bfs(start);
        }
    }

    private static void bfs(String start) {
        Queue<String> queue = new LinkedList<>();
        HashSet<String> set = new HashSet<>();
        queue.offer(start);
        set.add(start);
        while (!queue.isEmpty()) {
            int len = queue.size();
            while (len-- > 0) {
                String temp = queue.poll();
                // 出口
                if (temp.equals(end)) {
                    System.out.println(1);
                    return;
                }

                // 找空格位置
                int index = temp.indexOf('*');
                // 遍历四个方向
                for (int i = 0; i < 4; i++) {
                    int newIndex = index + dir[i];
                    // 判断是否越界
                    if (newIndex < 0 || newIndex > temp.length() - 1) {
                        continue;
                    }
                    // 只能上下左右四个方向移动
                    if ((newIndex % 3 == index % 3) || (newIndex / 3 == index / 3)) {
                        // 交换
                        char[] tempChar = temp.toCharArray();
                        tempChar[index] = temp.charAt(newIndex);
                        tempChar[newIndex] = temp.charAt(index);
                        String s = new String(tempChar);
                        // 判断该场景是否出现过
                        if (!set.contains(s)) {
                            set.add(s);
                            queue.offer(s);
                        }
                    }
                }
            }
        }
        System.out.println(0);
        return;
    }
}

B2、全球变暖

题目：你有一张某海域 NxN 像素的照片，".“表示海洋、”#"表示陆地，如下所示：

…

.##…

.##…

…##.

…####.

…###.

…

其中"上下左右"四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有 2 座岛屿。

由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)，它就会被淹没。

例如上图中的海域未来会变成如下样子：

…

…

…

…

…#…

…

…

请你计算：依照科学家的预测，照片中有多少岛屿会被完全淹没。

输入格式：

第一行包含一个整数 N (1≤N≤1000)。

以下 N 行 N 列代表一张海域照片。

照片保证第 1 行、第 1 列、第 N 行、第 N 列的像素都是海洋。、

输出一个整数表示答案。

输入输出样例：

输入

7
.......
.##....
.##....
....##.
..####.
...###.
.......

输出

1

运行限制：

  • 最大运行时间：1s
  • 最大运行内存: 256M
import java.io.*;
import java.util.LinkedList;

/**
 * @Descrption  DFS  2012 省赛
 * @version 全球变暖
 * @author QIA27
 * @date 2023年3月31日 下午12:12:11
 */
public class Main {
    static class Po{
        int x, y;
        public Po(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
    static int N = 1010;
    static char g[][] = new char[N][N];
    static boolean st[][] = new boolean[N][N];
    static int n;
    static int cnt, live;
    static int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        for(int i = 0; i < n; i++) g[i] = br.readLine().toCharArray();
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(g[i][j] == '#' && !st[i][j]){
                    cnt++; // 海岛数自增
                    bfs(new Po(i, j));
                }
            }
        }
        System.out.println(cnt - live);
        br.close();
    }
    public static void bfs(Po start){
        LinkedList<Po> q = new LinkedList<>();
        q.addLast(start);
        st[start.x][start.y] = true;
        int count = 0;
        boolean loop = false;
        while(!q.isEmpty()){
            Po t = q.removeFirst();
            if(count != 4){
                count = 0;
                for(int i = 0; i < 4; i++){
                    int x = t.x + dx[i], y = t.y + dy[i];
                    if(x < 0 || x >= n || y < 0 || y >= n || g[x][y] == '.') break;
                    count++;
                    if(count == 4) loop = true; // 只要在该岛屿内有一个海岛上下左右均不为海水，live++
                }
            }
            for(int i = 0; i < 4; i++){
                int x = t.x + dx[i], y = t.y + dy[i];
                if(x < 0 || x >= n || y < 0 || y >= n || g[x][y] == '.' || st[x][y]) continue;
                st[x][y] = true;
                q.addLast(new Po(x, y));
            } 
        }
        if(loop) live++; // 存活的岛屿数自增
    } 
}

集训C

C1、路径

题目：

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

小蓝学习了最短路径之后特别高兴，他定义了一个特别的图，希望找到图 中的最短路径。

小蓝的图由 2021 个结点组成，依次编号 1 至 2021。

对于两个不同的结点 a, b，如果 a 和 b 的差的绝对值大于 21，则两个结点 之间没有边相连；如果 a 和 b 的差的绝对值小于等于 21，则两个点之间有一条 长度为 a 和 b 的最小公倍数的无向边相连。

例如：结点 1 和结点 23 之间没有边相连；结点 3 和结点 24 之间有一条无 向边，长度为 24；结点 15 和结点 25 之间有一条无向边，长度为 75。

请计算，结点 1 和结点 2021 之间的最短路径长度是多少。

提示：建议使用计算机编程解决问题。

运行限制：

  • 最大运行时间：1s
  • 最大运行内存: 128M

解题代码：

import java.util.* ;

public class Main {
    public static void main(String[] args) {
        int n = 2022 ;
        int[] q = new int[n] ;
        q[1] = 0 ;
        for (int i =2; i<= 2021; i++) {
            q[i]= Integer.MAX_VALUE ;
        }
        //dp  
        //当前q[j] 表示 从 1~j的最短距离
        //q[j] 可以是 当前 1~j的最短距离 或者 前一状态 到 该点的最短距离
        for (int i = 1; i<= 2020; i++ )
            for (int j= i+1 ; j<=2021 && (j-i<=21); j++) {
                q[j] = Math.min(q[j], q[i] + le(i, j) ) ;
            }
            
        System.out.println(q[2021]) ;
    }
    
    public static int gcd(int a, int b ) {
        return b !=0 ? gcd(b, a%b): a ; 
    }
    
    public static int le(int a, int b) {
        return a*b/gcd(a,b) ;
    }
}

C2、约瑟夫环

题目：设有 n 个人围坐在圆桌周围，现从某个位置 k 上的人开始报数，报数到 m 的人就站出来。下一个人，即原来的第 +1m+1 个位置上的人，又从 11 开始报数，再报数到 m 的人站出来。依次重复下去，直到全部的人都站出来为止。试设计一个程序求出这 n 个人的出列顺序。

ss

要求一：采用循环链表解决。

要求二：可以使用模拟法，模拟循环链表。

要求三：可以不使用循环链表类的定义使用方式。

输入格式：

输入只有一行且为用空格隔开的三个正整数 n,k,m，其含义如上所述。

输出格式：

共 n 行，表示这 n 个人的出列顺序。

输入输出样例：

输入

3 5 8

输出

3
2
1

运行限制：

  • 最大运行时间：1s
  • 最大运行内存: 128M

解题代码：

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt(), k = scan.nextInt(), m = scan.nextInt();
        scan.close();
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 1; i <= n; i++) queue.offer(i); //初始哈
        for (int i = 1; i < k; i++) queue.offer(queue.poll()); //K位置开报
        int count = 0;
        while (! queue.isEmpty()) {
            Integer value = queue.poll();
            count++; //报数
            if (count != m) {
                queue.offer(value);
            } else {
                count = 0;
                System.out.println(value);
            }
        }
    }

}

最后

有帮助的话，希望可以点赞❤️+收藏⭐，谢谢各位大佬~~🙌🙌🙌

相关文章：

  • Fisher-Yates算法
  • 为什么一些人很瞧不起 Java？
  • 一个服务端同学的Vue框架入门及实践
  • Pod控制器之hpa
  • 头歌：Python开发技术—面向对象程序设计3 详细注释（第1关：工资结算系统+第2关：设计LFU缓存类）
  • jQuery一些问题和ajax操作
  • 自动驾驶模拟环境与测试 - 从Carla和AirSim开始
  • git revert 笔记
  • Scala包，样例类，样例对象
  • No.020＜软考＞《（高项）备考大全》【第05章】项目范围管理
  • SQVI快速报表
  • LeetCode练习八：动态规划下：背包问题
  • 常见汇编命令英文缩写
  • 【蓝桥杯】K倍区间
  • 前端计算文件 hash
  • Spring Boot集成简易规则引擎 easy-rules
  • Prometheus 普罗米修斯
  • 【网络安全工程师】从零基础到进阶，看这一篇就够了
  • c++ 一些常识 2
  • ［数据结构］直接插入排序、希尔排序