本篇博客旨在记录自已打卡蓝桥杯3月份刷题集训，同时会有自己的思路及代码解答希望可以给小伙伴一些帮助。本人也是算法小白，水平有限，如果文章中有什么错误之处，希望小伙伴们可以在评论区指出来，共勉????。
集训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 五个字母，右下角的那个格空着。如下图所示。
和空格子相邻的格子中的字母可以移动到空格中，比如，图中的 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 个人的出列顺序。
要求一：采用循环链表解决。
要求二：可以使用模拟法，模拟循环链表。
要求三：可以不使用循环链表类的定义使用方式。
输入格式：
输入只有一行且为用空格隔开的三个正整数 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);
}
}
}
}
最后
有帮助的话，希望可以点赞❤️+收藏⭐，谢谢各位大佬~~????????????