蓝桥杯·3月份刷题集训Day01
本篇博客旨在记录自已打卡蓝桥杯3月份刷题集训，同时会有自己的思路及代码解答希望可以给小伙伴一些帮助。本人也是算法小白，水平有限，如果文章中有什么错误之处，希望小伙伴们可以在评论区指出来，共勉💪。
集训A
A1、成绩分析
题目：小蓝给学生们组织了一场考试，卷面总分为 100 分，每个学生的得分都是一个 0 到 100 的整数。
请计算这次考试的最高分、最低分和平均分。
输入格式：
输入的第一行包含一个整数 n (1≤n≤104)，表示考试人数。
接下来 n 行，每行包含一个 0 至 100 的整数，表示一个学生的得分。
输出格式：
输出三行。
第一行包含一个整数，表示最高分。
第二行包含一个整数，表示最低分。
第三行包含一个实数，四舍五入保留正好两位小数，表示平均分。
输入输出样例：
输入
7
80
92
56
74
88
99
10
输出
99
10
71.29
运行限制：
- 最大运行时间：1s
- 最大运行内存: 256M
解题代码：
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 输入
int n = sc.nextInt();
int[] score = new int[n];
for (int i = 0; i < n; i++) {
score[i] = sc.nextInt();
}
int max = score[0];
int min = score[0];
double avg = 0;
for (int i = 0; i < score.length; i++) {
if (score[i] > max) {
max = score[i];
}
if (score[i] < min) {
min = score[i];
}
avg += score[i];
}
System.out.println(max);
System.out.println(min);
System.out.println(String.format("%.2f",avg/n));
}
}
A2、饮料换购
题目：乐羊羊饮料厂正在举办一次促销优惠活动。乐羊羊 C 型饮料，凭 3 个瓶盖可以再换一瓶 C 型饮料，并且可以一直循环下去(但不允许暂借或赊账)。
请你计算一下，如果小明不浪费瓶盖，尽量地参加活动，那么，对于他初始买入的 n 瓶饮料，最后他一共能喝到多少瓶饮料。
输入格式：
输入一个整数 n(0<n<1000)，表示开始购买的饮料数量。
输出格式：
输出一个整数，表示实际得到的饮料数
输入输出样例：
输入
100
输出
149
运行限制：
- 最大运行时间：1s
- 最大运行内存: 256M
解题代码：
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int count = n;
while(n >= 3) {
count += n / 3;
n = n%3 + n/3;
}
System.out.println(count);
}
}
集训B
B1、分巧克力
题目：儿童节那天有 K 位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。
小明一共有 N 块巧克力，其中第 i 块是 Hi + Wi 的方格组成的长方形。为了公平起见，
小明需要从这 N 块巧克力中切出 K 块巧克力分给小朋友们。切出的巧克力需要满足：
- 形状是正方形，边长是整数;
- 大小相同;
例如一块 6x5 的巧克力可以切出 6 块 2x2 的巧克力或者 2 块 3x3 的巧克力。
当然小朋友们都希望得到的巧克力尽可能大，你能帮小明计算出最大的边长是多少么？
输入格式：
第一行包含两个整数 N,K (1≤N,K≤105)。
以下 N 行每行包含两个整数 Hi,Wi (1≤H*i*,Wi ≤ 105)。
输入保证每位小朋友至少能获得一块 1x1 的巧克力。
输出格式：
输出切出的正方形巧克力最大可能的边长。
输入输出样例：
输入
2 10
6 5
5 6
输出
2
运行限制：
- 最大运行时间：2s
- 最大运行内存: 256M
解题代码：
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
public static int arr[][],n;
public static long check(int k){
long ans=0;
for(int i=0;i<n;i++){
ans+=(arr[i][0]/k)*(arr[i][1]/k);
}
return ans;
}
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
n=sc.nextInt();
int k=sc.nextInt();
arr=new int [n][2];
for(int i=0;i<n;i++){
arr[i][0]=sc.nextInt();
arr[i][1]=sc.nextInt();
}
int bit[]=new int[20];
bit[0]=1;
for(int i=1;i<20;i++){
bit[i]=bit[i-1]*2;
}
int ans=bit[19];
int p=18;
long a=check(ans),b=check(ans+1);
while(!(a>=k&&b<k)){
if(a>=k&&b>=k){
ans+=bit[p];
}else if(a<k&&b<k){
ans-=bit[p];
}
p--;
a=check(ans);
b=check(ans+1);
}
System.out.println(ans);
}
}
B2、递增三元组
题目：给定三个整数数组
A = [A1，A2，⋯ AN],
B = [B1，B2，⋯ BN],
C = [C1，C2，⋯ CN]，
请你统计有多少个三元组 (i,j,k) 满足：
- 1 ≤ i , j , k ≤ N;
- Ai < Bj < Ck。
输入格式：
第一行包含一个整数 N。
第二行包含 N 个整数 A1，A2，⋯ AN。
第三行包含 N 个整数 B1，B2，⋯ BN。
第四行包含 N 个整数 C1，C2，⋯ CN。
其中，1 ≤ N ≤ 105 , 0 ≤ Ai , Bi , Ci ≤ 105。
输出格式：
输出一个整数表示答案。
输入输出样例：
输入
3
1 1 1
2 2 2
3 3 3
输出
27
运行限制：
- 最大运行时间：2s
- 最大运行内存: 256M
解题代码：
暴力解法，测试用例过了5/8
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
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();
}
int count = 0;
//暴力遍历
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
if (A[i] < B[j] && B[j] < C[k]) {
count++;
}
}
}
}
System.out.println(count);
}
}
B3、小明的衣服
这个题有点难，我也不会……，查了一下，有解法使用优先队列构建哈夫曼树做的。
集训C
C1、数字三角形
题目：
上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和。
路径上的每一步只能从一个数走到下一层和它最近的左边的那个数或者右 边的那个数。此外，向左下走的次数与向右下走的次数相差不能超过 1。
输入格式：
输入的第一行包含一个整数 N (1≤N≤100)，表示三角形的行数。
下面的 N 行给出数字三角形。数字三角形上的数都是 0 至 100 之间的整数。
输出格式：
输出一个整数，表示答案。
输入输出样例：
输入
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
输出
27
运行限制
- 最大运行时间：1s
- 最大运行内存: 256M
解题代码：
这个题的示例似乎有问题，7->3->8->7->5 结果出来是 30 示例是27
测试用例只过了2/10
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[][] a = new int[n+1][((1+n)*n)/2+1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
a[i][j] = sc.nextInt();
}
}
// 动规
for (int i = n; i >= 1; i--) {
for (int j = 1; j <= i-1; j++) {
a[i-1][j] += Math.max(a[i][j], a[i][j+1]);
}
}
System.out.println(a[1][1]);
}
}
C2、跳跃
题目：小蓝在一个 n 行 m 列的方格图中玩一个游戏。
开始时，小蓝站在方格图的左上角，即第 11 行第 11 列。
小蓝可以在方格图上走动，走动时，如果当前在第 r 行第 c 列，他不能走到行号比 r 小的行，也不能走到列号比 c 小的列。同时，他一步走的直线距离不超过 3。
例如，如果当前小蓝在第 33 行第 55 列，他下一步可以走到第 33 行第 66 列、第 33 行第 77 列、第 33 行第 88 列、第 44 行第 55 列、第 44 行第 66 列、第 44 行第 77 列、第 55 行第 55 列、第 55 行第 66 列、第 66 行第 55 列之一。
小蓝最终要走到第 n 行第 m 列。
在图中，有的位置有奖励，走上去即可获得，有的位置有惩罚，走上去就要接受惩罚。奖励和惩罚最终抽象成一个权值，奖励为正，惩罚为负。
小蓝希望，从第 11 行第 11 列走到第 n 行第 m 列后，总的权值和最大。请问最大是多少？
输入格式：
输入的第一行包含两个整数 n,m，表示图的大小。
接下来 n 行，每行 m 个整数，表示方格图中每个点的权值。
其中，1≤n≤100，−104 ≤ 权值 ≤ 104。
输出格式：
输出一个整数，表示最大权值和。
输入输出样例：
输入
3 5
-4 -5 -10 -3 1
7 5 -9 3 -10
10 -2 6 -10 -4
输出
15
运行限制：
- 最大运行时间：1s
- 最大运行内存: 128M
解题代码：
import java.util.Arrays;
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[][] nums = new int[n][m];
// 读取输入
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
nums[i][j] = sc.nextInt();
}
}
// 在 dp 前面和左边多加几条 方便计算 dp[i][j] 因为网上会有 dp[i-3][i] dp[i][j-3]
int[][] dp = new int[n+3][m+3];
// 为了不影响计算 dp[i][j] 把整个 dp 都填充最小值
for(int i = 0; i< dp.length; i++) {
Arrays.fill(dp[i] ,Integer.MIN_VALUE);
}
// nums 和 dp 的下标相差3，初始化只用给首个
dp[3][3] = nums[0][0];
for (int i = 3; i < dp.length; i++) {
for (int j = 3; j < dp[0].length; j++) {
// 如果是刚才初始化过 dp[3][3]就跳过
if(i == 3 && j == 3) continue;
/**
* 实现计算前面的max最大值，也就是前面思路的max中的一大堆
* 这里不太美观，嫌麻烦的可以用递归或者dfs
*/
int max = Integer.MIN_VALUE;
for (int k = 0; k <= 3; k++) {
for (int l = 3-k; l >= 0; l--) {
if (k == 0 && l == 0) continue;
max = Math.max(max, dp[i-k][j-l]);
}
}
// 递推公式
dp[i][j] = nums[i-3][j-3] + max;
}
}
System.out.println(dp[n+2][m+2]);
}
}
C3、蓝肽子序列
题目：L 星球上的生物由蛋蓝质组成，每一种蛋蓝质由一类称为蓝肽的物资首尾连接成一条长链后折叠而成。
生物学家小乔正在研究 L 星球上的蛋蓝质。她拿到两个蛋蓝质的蓝肽序列，想通过这两条蓝肽序列的共同特点来分析两种蛋蓝质的相似性。
具体的，一个蓝肽可以使用 11 至 55 个英文字母表示，其中第一个字母大写，后面的字母小写。一个蛋蓝质的蓝肽序列可以用蓝肽的表示顺序拼接而成。
在一条蓝肽序列中，如果选取其中的一些位置，把这些位置的蓝肽取出，并按照它们在原序列中的位置摆放，则称为这条蓝肽的一个子序列。蓝肽的子序列不一定在原序列中是连续的，中间可能间隔着一些未被取出的蓝肽。
如果第一条蓝肽序列可以取出一个子序列与第二条蓝肽序列中取出的某个子序列相等，则称为一个公共蓝肽子序列。
给定两条蓝肽序列，找出他们最长的那个公共蓝肽子序列的长度。
输入格式：
输入两行，每行包含一个字符串，表示一个蓝肽序列。字符串中间没有空格等分隔字符。
其中有 ，两个字符串的长度均不超过 1000。
输出格式：
输出一个整数，表示最长的那个公共蓝肽子序列的长度。
输入输出样例：
输入
LanQiaoBei
LanTaiXiaoQiao
输出
2
运行限制：
- 最大运行时间：1s
- 最大运行内存: 128M
解题代码：
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str1 = sc.next();
String str2 = sc.next();
// 将字符串分割
String[] split1 = splitStr(str1);
String[] split2 = splitStr(str2);
// 动态规划·初始化
int ans = 0;
int lens = split1.length, lent = split2.length;
int[][] dp = new int[lens + 1][lent + 1];
for (int i = 2; i <= lens; i++) {
for (int j = 2; j <= lent; j++) {
if (split1[i - 1].equals(split2[j - 1])) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i][j - 1],dp[i - 1][j]);
}
ans = Math.max(ans, dp[i][j]);
}
}
System.out.println(ans);
}
private static String[] splitStr(String str) {
// $0 表示匹配到的第一个字符（即该大写字母）
// _$0 表示在匹配到的大写字母前加一个下划线（作为分隔符使用）
String temp = str.replaceAll("[A-Z]", "_$0");
String[] split = temp.split("_");
return split;
}
}
最后
有帮助的话，希望可以点赞❤️+收藏⭐，谢谢各位大佬~~🙌🙌🙌
相关文章
- 蓝桥算法训练__提高组.Day1
- 蓝桥算法训练__普及组.Day12
- 蓝桥算法训练__普及组.Day10
- 蓝桥杯·3月份刷题集训Day02
- 蓝桥杯2022年第十三届决赛真题-小球称重
- C++│蓝桥杯省赛真题油漆面积问题
- python│蓝桥杯省赛真题方格分割问题
- 十四届蓝桥杯青少组选拔赛Python_2022.11.27
- 十四届蓝桥选拔赛Scratch-2023.02.12 试题解析
- 2012蓝桥杯决赛题
- 第十四届蓝桥杯三月真题刷题训练——第 22 天
- 第十四届蓝桥杯三月真题刷题训练——第 20 天
- 第十四届蓝桥杯三月真题刷题训练——第 18 天
- 第十四届蓝桥杯三月真题刷题训练——第 10 天
- 第十四届蓝桥杯三月真题刷题训练——第 8 天