本篇博客旨在记录自已打卡蓝桥杯3月份刷题集训,同时会有自己的思路及代码解答希望可以给小伙伴一些帮助。本人也是算法小白,水平有限,如果文章中有什么错误之处,希望小伙伴们可以在评论区指出来,共勉💪。
文章目录
- 集训A
- A1、约数个数
- A2、质数拆分
- 集训B
- B1、路径之谜
- B2、分考场
- 集训C
- C1、修改数组
- C2、通电
- 最后
集训A
A1、约数个数
题目
:
本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果输出即可。
1200000 有多少个约数(只计算正约数)。
运行限制:
- 最大运行时间:1s
- 最大运行内存: 128M
解题代码:
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {public static void main(String[] args) {int n = 1200000;int count = 0;for (int i = 1;i <= 1200000; i++) {if (n % i == 0) {count++;}}System.out.println(count);}
}
A2、质数拆分
题目
:本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果输出即可。
将 2019 拆分为若干个两两不同的质数之和,一共有多少种不同的方法?
注意交换顺序视为同一种方法,例如2+2017=2019 与 2017+2=2019 视为同一种方法。
运行限制:
- 最大运行时间:1s
- 最大运行内存: 128M
解题代码:
import java.util.*;/*** @Descrption 填空题 2019 国赛* @version 质数拆分* @author QIA27* @date 2023年4月2日 上午12:41:33*/
public class Main {public static void main(String[] args) {int n = 2019;boolean[] f = new boolean[n + 1];ArrayList<Integer> primes = new ArrayList<>();for (int i = 2; i <= n; i++) {if (!f[i]) {primes.add(i);for (int j = i + i; j <= n; j += i) {f[j] = true;}}}long[] dp = new long[n+1];dp[0] = 1;for(int i = 0; i < primes.size(); i++){int a = primes.get(i);for(int j = n; j >= a; j--){dp[j] += dp[j - a];}}System.out.println(dp[n]);}
}
集训B
B1、路径之谜
题目
:小明冒充 X 星球的骑士,进入了一个奇怪的城堡。
城堡里边什么都没有,只有方形石头铺成的地面。
假设城堡地面是 n×n 个方格。如下图所示。
按习俗,骑士要从西北角走到东南角。可以横向或纵向移动,但不能斜着走,也不能跳跃。每走到一个新方格,就要向正北方和正西方各射一箭。(城堡的西墙和北墙内各有 n 个靶子)同一个方格只允许经过一次。但不必走完所有的方格。如果只给出靶子上箭的数目,你能推断出骑士的行走路线吗?有时是可以的,比如上图中的例子。
本题的要求就是已知箭靶数字,求骑士的行走路径(测试数据保证路径唯一)
输入格式:
第一行一个整数 N (0≤N≤20),表示地面有 N×N 个方格。
第二行 N 个整数,空格分开,表示北边的箭靶上的数字(自西向东)
第三行 N 个整数,空格分开,表示西边的箭靶上的数字(自北向南)
输出格式:
输出一行若干个整数,表示骑士路径。
为了方便表示,我们约定每个小格子用一个数字代表,从西北角开始编号: 0,1,2,3 ⋯⋯
比如,上图中的方块编号为:
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
输入输出样例:
输入
4
2 4 3 4
4 3 3 3
输出
0 4 5 1 2 3 7 11 10 9 13 14 15
运行限制:
- 最大运行时间:5s
- 最大运行内存: 256M
解题代码:
import java.util.Scanner;
import java.util.ArrayList;/*** @Descrption DFS 2016 国赛* @version 路径之谜* @author QIA27* @date 2023年4月2日 上午1:20:29*/
public class Main {static int row[];//x轴各箭靶上的箭static int col[];//y轴各箭靶上的箭static int n;static int flag[][];//判断有没有走过static int dir[][]={{0,1},{1,0},{-1,0},{0,-1}};//控制方向static ArrayList<Integer> path = new ArrayList<>();//记录路径public static void main(String[] args) {Scanner sc = new Scanner(System.in);n = sc.nextInt();flag = new int[n][n];row = new int[n];col = new int[n];for(int i=0;i<n;i++){row[i] = sc.nextInt();}for(int i=0;i<n;i++){col[i] = sc.nextInt();}int k = 0;row[0]--;col[0]--;flag[0][0] = 1;path.add(0);//先存入0dfs(0,0);}private static void dfs(int x,int y){if(check(x,y)){//检查是否到达终点且各箭靶上的箭均为0return;}else{for(int k =0;k<4;k++){int nx = x +dir[k][0];int ny = y +dir[k][1];if(pd(nx,ny)) {//判断是否,下标越界、已经走过、箭靶数为负数row[nx] --;col[ny] --;//拔出箭flag[nx][ny] = 1;//标记为1path.add(ny*n +nx);//将对应路径记录dfs(nx,ny);path.remove(path.size()-1);//恢复,删除记录最后一个flag[nx][ny] = 0;row[nx] ++;col[ny] ++;}}}}public static boolean check(int x,int y){if(x !=n-1 || y!=n-1){//没到终点,退出return false;}for(int i=0;i<n;i++){//箭靶有不为0的,退出if(row[i]!= 0 || col[i] != 0){return false;}}for(int i =0;i<path.size();i++){//输出路径System.out.print(path.get(i) +" ");}System.out.println();return false;//成功终止、}public static boolean pd(int x2,int y2){if(x2>=n || x2<0 || y2>=n ||y2<0){return false;}if(flag[x2][y2] ==1||row[x2]<=0 || col[y2]<=0){return false;}return true;}
}
B2、分考场
题目
:n 个人参加某项特殊考试。
为了公平,要求任何两个认识的人不能分在同一个考场。
求最少需要分几个考场才能满足条件。
输入格式:
输入格式:
第一行,一个整数 n (1≤n≤100),表示参加考试的人数。
第二行,一个整数 m,表示接下来有 m 行数据。
以下 m 行每行的格式为:两个整数 a,b,用空格分开 ( 1≤a,b≤n )表示第 a 个人与第 b 个人认识。
输出格式:
输出一行一个整数,表示最少分几个考场。
输入输出样例:
输入
5
8
1 2
1 3
1 4
2 3
2 4
2 5
3 4
4 5
输出
4
运行限制:
- 最大运行时间:1s
- 最大运行内存: 256M
解题代码:
测试用例:4/5
import java.util.Scanner;/*** @Descrption 搜索 2017 国赛* @version 分考场* @author QIA27* @date 2023年4月2日 上午2:14:44*/
public class Main {static int n,m,num=0,min=140;static boolean[][] arr; // 存储学生关系static int[][] con; public static void main(String[] args){Scanner scanner = new Scanner(System.in);n = scanner.nextInt();m = scanner.nextInt();arr = new boolean[105][105];con = new int[105][105];for (int i=0; i<m; i++) {int a = scanner.nextInt();int b = scanner.nextInt();arr[a][b]=true;arr[b][a]=true;}dfs(1); // 当前学生System.out.println(min);}public static void dfs(int s) { // 考虑的第S个学生if (num>min)return; // 剪枝 num 表示当前方案所需要的房间数,if (s>n){min = min>num ? num : min;return;}boolean flag=false;for (int i=1; i<=num; i++) {// 遍历当前已分配的房间,贪心的加入到已分配的房间flag=false;for (int j=1; j<=con[i][0]; j++) {int x = con[i][j];if (arr[x][s]) {flag=true;break;}}if (!flag) {// 如果可以加到iint ax = ++con[i][0];con[i][ax]= s;dfs(s+1);con[i][0]--;}} // 开设一个新房间num++;con[num][++con[num][0]] = s;dfs(s+1);con[num][0]--;num--;}
}
集训C
C1、修改数组
题目
:给定一个长度为 N 的数组 A = [A1,A2,⋅⋅⋅,AN],数组中有可能有重复出现的整数。
现在小明要按以下方法将其修改为没有重复整数的数组。小明会依次修改A*2,A3,⋅⋅⋅,*AN。
当修改 Ai 时,小明会检查 A*i* 是否在 A1 ~ *Ai*−1 中出现过。如果出现过,则小明会给 Ai 加上 1 ;如果新的 Ai 仍在之前出现过,小明会持续给 Ai 加 1 ,直 到 Ai 没有在 A1 ~ *Ai*−1 中出现过。
当 AN 也经过上述修改之后,显然 A 数组中就没有重复的整数了。
现在给定初始的 A 数组,请你计算出最终的 A 数组。
输入格式:
第一行包含一个整数 N。
第二行包含 N 个整数 A*1,A2,⋅⋅⋅,AN。
其中,1≤N≤105,1≤*Ai*≤106。
输出格式:
输出 N 个整数,依次是最终的 A*1,A2,⋅⋅⋅,AN。
输入输出样例:
输入
5
2 1 1 3 4
输出
2 1 3 4 5
运行限制:
- 最大运行时间:1s
- 最大运行内存: 256M
解题代码:
暴力解法 测试用例:4/10
import java.util.Scanner;/*** @Descrption 并查集 2019 省赛* @version 修改数组* @author QIA27* @date 2023年4月2日 上午2:20:31*/
public class Main {static int[] arr;public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();arr = new int[n+1];for (int i = 1; i < arr.length; i++) {arr[i] = sc.nextInt();}for (int i = 1; i < arr.length; i++) {find(i);}for (int i = 1; i < arr.length; i++) {System.out.print(arr[i]+" ");}}private static void find(int i) {boolean f = false;for (int j = 0; j < i; j++) {if(arr[j] == arr[i]) {f = true;break;}}if(f) {// 存在重复元素arr[i]++;find(i);}}
}
并查集
import java.util.Scanner;public class Main{static int[] f = new int[2000000]; // 存放1~n个节点public static void main(String[] args) {// 输入Scanner sc = new Scanner(System.in);int n = sc.nextInt();int[] arr = new int[n];// 初始化ffor (int i = 1; i < f.length; i++) {f[i] = i;}// 优化的部分for (int i = 0; i < arr.length; i++) {arr[i] = sc.nextInt();// 将当前元素的根节点赋值给当前元素arr[i] = find(arr[i]);// 将当前元素的根节点往后移动一位f[arr[i]] = find(arr[i]+1);}// 输出for (int i = 0; i < arr.length; i++) {System.out.print(arr[i]+" ");}}/*** 获取x的根节点* @param x* @return*/static int find(int x) {if(f[x] == x) {return x;}f[x] = find(f[x]);return f[x];}
}
C2、通电
题目
:2015 年,全中国实现了户户通电。作为一名电力建设者,小明正在帮助一带一路上的国家通电。
这一次,小明要帮助 n 个村庄通电,其中 1 号村庄正好可以建立一个发电站,所发的电足够所有村庄使用。
现在,这 n 个村庄之间都没有电线相连,小明主要要做的是架设电线连接这些村庄,使得所有村庄都直接或间接的与发电站相通。
小明测量了所有村庄的位置(坐标)和高度,如果要连接两个村庄,小明需要花费两个村庄之间的坐标距离加上高度差的平方,形式化描述为坐标为(x*1,y1) 高度为 ℎ1h1 的村庄与坐标为 (x2,y2) 高度为 ℎ2* 的村庄之间连接的费用为
(x1−x2)2+(y1−y2)2\sqrt{(x_1−x_2)^2 + (y_1−y_2)^2}(x1−x2)2+(y1−y2)2+(h1−h2)2
高度的计算方式与横纵坐标的计算方式不同。
由于经费有限,请帮助小明计算他至少要花费多少费用才能使这 n 个村庄都通电。
输入格式:
输入的第一行包含一个整数 n ,表示村庄的数量。
接下来 n 行,每个三个整数 x , y , h ,分别表示一个村庄的横、纵坐标和高度,其中第一个村庄可以建立发电站。
其中,1 ≤ n ≤ 1000,0 ≤ x,y,h ≤ 10000。
输出格式:
输出一行,包含一个实数,四舍五入保留 2 位小数,表示答案。
输入输出样例:
输入
4
1 1 3
9 9 7
8 8 6
4 5 4
输出
17.41
运行限制:
语言 | 最大运行时间 | 最大运行内存 |
---|---|---|
C++ | 1s | 256M |
C | 1s | 256M |
Java | 2s | 256M |
Python3 | 3s | 256M |
解题代码:
import java.util.Arrays;
import java.util.Scanner;
/*** @Descrption 最小生成树 2020 省模拟赛* @version 通电* @author QIA27* @date 2023年4月2日 上午2:28:44*/
public class Main {static Scanner in = new Scanner(System.in);static boolean[] vis = new boolean[1005];static double[] dis = new double[1005];static double[][] e = new double[1005][1005];static int INF = 0x7f7f7f7f;static int n;//顶点数static int m;//边数static Node[] nodes = new Node[1002];static void init(){for(int i=0;i<n;i++)Arrays.fill(e[i],INF);}static void prim(){double cnt = 0.0;for(int i=0;i<n;i++){dis[i] = e[0][i];//从下标为0的点开始遍历}vis[0] = true;for(int i=0;i<n-1;i++){double min = INF;int index = -1;for(int j=0;j<n;j++){if(!vis[j]&&min>dis[j]){min = dis[j];index = j;}}vis[index] = true;cnt += dis[index];//更新dis数组for(int j=0;j<n;j++){if(!vis[j]&&dis[j]>e[index][j]){dis[j] = e[index][j];}}}System.out.printf("%.2f",cnt);}static void getMap(){for(int i=0;i<n;i++){nodes[i] = new Node();nodes[i].x = in.nextInt();nodes[i].y = in.nextInt();nodes[i].h = in.nextInt();}for(int i=0;i<n;i++){for(int j=i+1;j<n;j++){double x = (nodes[i].x-nodes[j].x)*(nodes[i].x-nodes[j].x);double y = (nodes[i].y-nodes[j].y)*(nodes[i].y-nodes[j].y);double h = (nodes[i].h-nodes[j].h)*(nodes[i].h-nodes[j].h);double temp = Math.sqrt(x+y)+h;e[i][j] = temp;e[j][i] = e[i][j];}}}public static void main(String[] args) {n = in.nextInt();init();getMap();prim();}
}
class Node
{int x;//x坐标int y;//y坐标int h;//高度
}
最后
有帮助的话,希望可以点赞❤️+收藏⭐,谢谢各位大佬~~🙌🙌🙌