第十四届蓝桥杯三月真题刷题训练——第 11 天
目录
第 1 题：卡片
题目描述
运行限制
第 2 题：路径_dp+gcd
运行限制
第 3 题：字符统计
问题描述
输入格式
输出格式
样例输入
样例输出
评测用例规模与约定
运行限制
第 4 题：费用报销
第 1 题：卡片
题目描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
小蓝有很多数字卡片，每张卡片上都是数字 0 到 9。
小蓝准备用这些卡片来拼一些数，他想从 1 开始拼出正整数，每拼一个，就保存起来，卡片就不能用来拼其它数了。
小蓝想知道自己能从 1 拼到多少。
例如，当小蓝有 30 张卡片，其中 0 到 9 各 3 张，则小蓝可以拼出 1 到 10，
但是拼 11 时卡片 1 已经只有一张了，不够拼出11。
现在小蓝手里有 0 到 9 的卡片各 2021 张，共 20210 张，请问小蓝可以从 1 拼到多少？
提示：建议使用计算机编程解决问题。
运行限制
- 最大运行时间：1s
- 最大运行内存: 128M
代码：
package 第十四届蓝桥杯三月真题刷题训练.day11;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Arrays;
/**
* @author yx
* @date 2023-03-14 8:28
*/
public class 卡片 {
static PrintWriter out =new PrintWriter(System.out);
static BufferedReader ins=new BufferedReader(new InputStreamReader(System.in));
static StreamTokenizer in=new StreamTokenizer(ins);
/**
* 输入
* in.nextToken()
* int a= (int)in.nval;
*
* 输出
* out.print();
* out.flush();
*/
static int[] nums=new int[10];
static int i;
public static void main(String[] args) {
i=0;
while (true){
i++;
char[] num=(i+"").toCharArray();
int length=num.length;
for (int j = 0; j < length; j++) {
nums[num[j] - '0']++;
if(nums[num[j]-'0']==2021&&j==length-1) {
out.println(i);
out.flush();
return;
}else if(nums[num[j]-'0']==2021&&j!=length-1){
out.println(i-1);
out.flush();
return;
}
}
}
}
}
第 2 题：路径_dp+gcd
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
小蓝学习了最短路径之后特别高兴，他定义了一个特别的图，希望找到图 中的最短路径。
小蓝的图由 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
代码：
package 第十四届蓝桥杯三月真题刷题训练.day11;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
/**
* @author yx
* @date 2023-03-14 8:54
*/
public class 路径_01背包_gcd {
static PrintWriter out = new PrintWriter(System.out);
static BufferedReader ins = new BufferedReader(new InputStreamReader(System.in));
static StreamTokenizer in = new StreamTokenizer(ins);
/**
* 输入
* in.nextToken()
* int a= (int)in.nval;
*
* 输出
* out.print();
* out.flush();
*/
public static void main(String[] args) {
int[] nums = new int[2022];
for (int i = 1; i <= 2021; i++) {
//这个地方也比较细节，到i+21时为最大更新区间
for (int j = i+1; j <=i+21 ; j++) {
if (j == 2022) {
//当遍历到2022时，说明在此循环内已经完成了2021之前的更新
//2022超出最大范围2021，所以退出当前循环
//继续下一个i+1，更新从i+1~2021的最小路径
break;
}
//i*j的最小公倍数等于（i*j）/最大公约数
int temp = gcd(i, j);
if (nums[j] == 0) {//初始化
nums[j] = (int)(i * j / temp) + nums[i];
} else {//进行最优化迭代，选出最短路径
nums[j] = Math.min(nums[j], i * j / temp + nums[i]);
}
}
}
out.println(nums[2021]);
out.flush();
}
static int gcd(int m, int n) {
return n != 0 ? gcd(n, m % n) : m;
}
}
第 3 题：字符统计
问题描述
给定一个只包含大写字母的字符串 S, 请你输出其中出现次数最多的字符。如果有多个字母均出现了最多次, 按字母表顺序依次输出所有这些字母。
输入格式
一个只包含大写字母的字符串 S.
输出格式
若干个大写字母，代表答案。
样例输入
BABBACAC样例输出
AB评测用例规模与约定
对于 100%的评测用例, 1≤∣S∣≤10^6.
运行限制
- 最大运行时间：1s
- 最大运行内存: 512M
代码：
package 第十四届蓝桥杯三月真题刷题训练.day11;
import java.io.*;
import java.util.Arrays;
import java.util.HashMap;
/**
* @author yx
* @date 2023-03-14 9:53
*/
public class 字符统计 {
static PrintWriter out =new PrintWriter(System.out);
static BufferedReader ins=new BufferedReader(new InputStreamReader(System.in));
static StreamTokenizer in=new StreamTokenizer(ins);
/**
* 输入
* in.nextToken()
* int a= (int)in.nval;
*
* 输出
* out.print();
* out.flush();
*/
public static void main(String[] args) throws IOException {
char[] strings=ins.readLine().toCharArray();
int length1=strings.length;
int max=0;
int[] nums1=new int[26];
for (int i = 0; i < length1; i++) {
nums1[strings[i]-'A']++;
}
int length2=nums1.length;
int[]nums2= Arrays.copyOf(nums1,nums1.length);
Arrays.sort(nums1);
max=nums1[25];
for (int i = 0; i < length2; i++) {
if(nums2[i]==max){
System.out.print((char)('A'+i));
}
}
}
}
第 4 题：费用报销
晚上补题