2021第十二届蓝桥杯省赛java b组 题目+答案
2021/6/8
嗯…混了个国二
2021/4/28
这都能省一。。。好水啊。。。
A：ASC
【问题描述】
已知大写字母 A 的 ASCII 码为 65，请问大写字母 L 的 ASCII 码是多少？
【答案】
76
签到题😃
public class Main {
public static void main(String[] args) {
System.out.println((int) 'L');
}
}B：卡片
【问题描述】
基于上述设定问题转化为求解在这种情况下他最多能连续拼出哪些正整数？
【答案】
3181
创建一个长度为10的数组，并将其中索引从0到9的位置初始化为表示可用卡片的数量；随后遍历每个数字，并将其转换为对应的字符串形式；当某个位置上的值为零时，则表示该数字无法被拼出；此时应返回前一位置对应的可用卡片。
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] chs = new int[10];
Arrays.fill(chs, 2021);
for (int i = 1; ; i++) {
for (char c : String.valueOf(i).toCharArray()) {
if (chs[c - '0'] == 0) {
System.out.println(i-1);
return;
}
chs[c - '0']--;
}
}
}
}C：直线
【问题描述】
在平面直角坐标系中，两点可以确定一条直线。如果有多点在一条直线上，那么这些点中任意两点确定的直线是同一条。
给定平面上 2 × 3 个整点 {(x,y)|0 ≤ x < 2,0 ≤ y < 3, x ∈ Z,y ∈ Z}，即横坐标是 0 到 1 (包含 0 和 1) 之间的整数、纵坐标是 0 到 2 (包含 0 和 2) 之间的整数的点。这些点一共确定了 11 条不同的直线。
给定平面上 20 × 21 个整点 {(x,y)|0 ≤ x < 20,0 ≤ y < 21, x ∈ Z,y ∈ Z}，即横坐标是 0 到 19 (包含 0 和 19) 之间的整数、纵坐标是 0 到 20 (包含 0 和 20) 之间的整数的点。请问这些点一共确定了多少条不同的直线。
【答案】
40257
思路是对每一个起点和终点进行枚举，并利用公式 y=kx+b 来计算斜率k和截距b进而求得重复次数。需要注意的是，在这种情况下k可能会出现小数值就需要采用双精度变量double来处理以提高计算效率。测试后发现由于浮点运算的精度问题导致结果偏差较大。。
最后的实现方法是以 String 表示分数，并通过集合去重进行一些细节处理。
import java.util.*;
class Line {
String k;
String b;
@Override
public boolean equals(Object o) {
Line line = (Line) o;
return Objects.equals(k, line.k) && Objects.equals(b, line.b);
}
@Override
public int hashCode() {
int result = k != null ? k.hashCode() : 0;
result = 31 * result + (b != null ? b.hashCode() : 0);
return result;
}
}
class Point {
int x;
int y;
}
public class Main {
static int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
public static void main(String[] args) {
Set<Line> lines = new HashSet<>();
List<Point> points = new ArrayList<>();
for (int i = 0; i < 20; i++) {
for (int j = 0; j < 21; j++) {
Point p = new Point();
p.x = i;
p.y = j;
points.add(p);
}
}
for (int i = 0; i < points.size(); i++) {
Point p1 = points.get(i);
for (int j = 0; j < points.size(); j++) {
if (i != j) {
Point p2 = points.get(j);
Line l = new Line();
if (p2.x == p1.x) {
l.b = String.valueOf(p1.x);
} else {
int kt = p2.y - p1.y;
int kd = p2.x - p1.x;
int gcd = gcd(kt, kd);
kt /= gcd;
kd /= gcd;
if (kt == 0) {
l.k = String.valueOf(0);
l.b = String.valueOf(p1.y);
lines.add(l);
continue;
}
if ((kt < 0) ^ (kd < 0)) {
l.k = -Math.abs(kt) + "/" + Math.abs(kd);
} else {
l.k = Math.abs(kt) + "/" + Math.abs(kd);
}
kt = p1.y * kd - kt * p1.x;
gcd = gcd(kt, kd);
kt /= gcd;
kd /= gcd;
if (kt == 0) {
l.b = "0";
lines.add(l);
continue;
}
if ((kt < 0) ^ (kd < 0)) {
l.b = -Math.abs(kt) + "/" + Math.abs(kd);
} else {
l.b = Math.abs(kt) + "/" + Math.abs(kd);
}
}
lines.add(l);
}
}
}
System.out.println(lines.size());
}
}D：货物摆放
【问题描述】
小蓝拥有一个极大容量的仓库，并可容纳大量货物。
目前有 n 箱货物需要放置于仓库内。
为了实现整齐存储的目标，
我们为长方体方向上分别堆叠 L 层（层）、W 列（列）和 H 个（个）货箱。
小蓝希望所有货箱最终排列成一个大立方体。
即在长方体方向上分别堆叠 L 层（层）、W 列（列）和 H 个（个）货箱，
满足总数量 n = L × W × H 的条件。
给定具体的数值 n，
我们需要计算满足条件的不同排列组合方式数目。
例如，
当 n = 4 时，
存在以下六种排列方式：
1×1×4，
1×2×2，
1×4×1，
2×1×2，
2 × 2 × 1 和 4 × 1 × 1。
请问当 n = 2021041820210418时，
总共有多少种排列组合方式？
【答案】
2430
哎呀，在参加考试时脑子有点懵不知道怎么解题呢。好长时间一直想也没弄明白怎么办呀。后来知道原来是全排序的时候一下子明白了。
不过因数这部分赛前不是很清楚，估计就算知道是全排序也做不出
最终方案还是相对简单的做法就是列举这个大数的所有因数，并对其进行系统性排列组合。通过这种方式我们可以找出所有可能的三元组组合使得它们的乘积等于该大数值
要注意的一点是得对大数取个平方根，不然得跑到猴年马月
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
import java.util.stream.Collectors;
public class Main {
static Deque<Long> temp = new LinkedList<>();
static List<Long> yn = new ArrayList<>();
static long count = 0;
static long n = 2021041820210418L;
public static void main(String[] args) {
for (long i = 1, end = (long) Math.sqrt(n); i <= end; i++) {
if (n % i == 0) {
yn.add(i);
yn.add(n / i);
}
}
// 去重
yn = yn.stream().distinct().collect(Collectors.toList());
dfs(0, 1);
System.out.println(count);
}
static void dfs(int be, long now) {
if (temp.size() == 3) {
if (now == n) {
count++;
}
return;
}
for (int i = be; i < yn.size(); i++) {
temp.addLast(yn.get(i));
dfs(be, now * yn.get(i));
temp.removeLast();
}
}
}E：路径
【问题描述】
小蓝学完最短路径之后感到非常开心，在此基础上他构造了一个独特的图，并致力于找出该图中的最短路径。
这个图由共计2021个节点构成，并按照编号顺序排列为节点1至节点2021。
对于任意两个不同的节点a和b：
- 如果它们之间的差值绝对值超过21，则这两端没有连接；
- 若它们之间的差值绝对值不超过21，则这两个节点之间将存在一条无向边，并且该边的长度等于a与b的最小公倍数。
以上述实例说明： - 结点1与结点23之间没有连接；
- 结点3与结点24之间有一条无向边其长度为最小公倍数为48；
- 结点15与结点66之间有一条无向边其长度为75。
问题：计算从节点1到节点2021之间的最短路径长度是多少？
【答案】
10266837
直接建图然后 floyd 或 dijkstra，可惜我并没记😅
import java.util.*;
public class Main {
static int gcd(int x, int y) {
return y == 0 ? x : gcd(y, x % y);
}
static int lcm(int x, int y) {
return x * y / gcd(x, y);
}
public static void main(String[] args) {
int[][] map = new int[2100][2100];
for (int i = 1; i <= 2021; i++) {
for (int j = i; j <= i + 21; j++) {
map[i][j] = lcm(i, j);
}
}
// 是否最短
boolean[] bj = new boolean[2100];
// 到其他顶点的路径
int[] dis = new int[2100];
for (int i = 1; i <= 22; i++) {
dis[i] = map[1][i];
}
while (!bj[2021]) {
int minIdx = 0, min = Integer.MAX_VALUE;
// 找到不能确实是最短路径的最短边的点
for (int i = 2; i <= 2021; i++) {
if (!bj[i] && dis[i] != 0 && dis[i] < min) {
min = dis[i];
minIdx = i;
}
}
// 标记为已经找到
bj[minIdx] = true;
// 遍历该点的所有边,看看是否顶点能否通过该点,来获取到更短的点
for (int i = minIdx + 1; i <= minIdx + 21; i++) {
// 这不是一个不能到达的点
if (map[minIdx][i] != 0) {
// 通过这个点可以达到一个不能到达的点
if (dis[i] == 0) {
dis[i] = dis[minIdx] + map[minIdx][i];
} else {
// 虽然已经可以到达了,但是通过这个点可能可以缩短距离
dis[i] = Math.min(dis[i], dis[minIdx] + map[minIdx][i]);
}
}
}
}
System.out.println(dis[2021]);
}
}F：时间显示
【问题描述】
小蓝与朋友共同开发了一个基于时间显示功能的网站。服务器端的朋友已经成功获取了当前系统时间并将其以整数值的形式记录下来其中该数值代表自1970年1月1日零时起至当前时刻所经历的毫秒数。
为了在客户端界面清晰展示实时信息小蓝决定仅需显示当前的时间信息而不呈现日期部分。
具体来说小蓝只需关注小时分钟以及秒钟的部分而无需理会分钟以下的时间单位即毫秒部分可以直接忽略不计。
当系统提供了一个以整数值形式记录的时间数据时请将其转换并输出对应的时间小时、分钟及秒钟部分。
【输入格式】
输入一行包含一个整数，表示时间。
【输出格式】
记录当前时间时采用时分秒格式（Format: HH:MM:SS），其中 HH 代表小时（取值范围为 0 到 23）、MM 表示分钟（取值范围为 0 到 59）、SS 是秒钟（取值范围也为 0 到 59）。当小时、分钟或秒钟数值不足两位时，在前面添加零以确保时间表示的完整性
【样例输入 1】
46800999
【样例输出 1】
13:00:00
【样例输入 2】
1618708103123
【样例输出 2】
01:08:23
【评测用例规模与约定】
对于所有评测用例，给定的时间为不超过 10^{18} 的正整数。
立刻意识到一看到 1970/1/1 就会联想到 Unix 时间戳后就想着想到了相关的时间工具类。自然倾向于采用模拟的方法来处理此类问题。。
import java.time.LocalDateTime;
import java.time.ZoneOffset;
import java.time.format.DateTimeFormatter;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long time = sc.nextLong();
sc.close();
LocalDateTime t = LocalDateTime.ofEpochSecond(time/1000, 0, ZoneOffset.UTC);
DateTimeFormatter format = DateTimeFormatter.ofPattern("HH:mm:ss");
System.out.println(format.format(t));
}
}G：最少砝码
【问题描述】
拥有一架天平。为了达到目的, 你需要配置一套磅秤系统, 通过合理配置这些磅秤能够衡量所有不大于 N 的正整数重量. 那么如何配置这套磅秤系统才能使所用的磅秤数量最少? 特别地, 在使用时允许将磅秤放置在天平的任一侧.
【输入格式】
输入包含一个正整数 N。
【输出格式】
输出一个整数代表答案。
【样例输入】
7
【样例输出】
3
【样例说明】
采用重量为1、4、6的三个砝码，则能够测量从1到7的所有整数值范围内的物体质量。具体组合如下：
- 单个砝码可直接对应其自身质量：即m=1\text{g}。
- 当被测物与质量为4\text{g}的砝码放在同一侧时，则需在另一侧放置质量为6\text{g}的砝码以平衡：即m=|6-4|=2\text{g}。
- 将较重的6\text{g}与较轻的1\text{g}放在不同侧时，则被测物的质量等于两者的差值：即m=|6-1|=5\text{g}。
- 同理可得其他数值：
- m=3\text{g}=|4-1|；
- m=4\text{g}=| \cdot |
- m=5\text{g}=|
- m=7\text{g}=|
仅使用两个或更少数量的砝码则无法覆盖所需的所有质量范围
【评测用例规模与约定】
对于所有评测用例，1 ≤ N ≤ 1000000000。
这题想了半小时也只知道用dp做，但是没思路。。。
这个答案是三进制模拟的方法做的
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long n = sc.nextLong();
sc.close();
int i, ans;
for (i = 1, ans = 1; ans < n; i++) {
ans += Math.pow(3, i);
}
System.out.println(i);
}
}H：杨辉三角形
【问题描述】
下面的图形是著名的杨辉三角形：
如果我们按从上到下、从左到右的顺序把所有数排成一列，可以得到如下数列：
1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 1, ...
给定一个正整数 N，请你输出数列中第一次出现 N 是在第几个数？
【输入格式】
输入一个整数 N。
【输出格式】
输出一个整数代表答案。
【样例输入】
6
【样例输出】
13
【评测用例规模与约定】
对于 20% 的评测用例，1 ≤ N ≤ 10；
对于所有评测用例，1 ≤ N ≤ 1000000000。
没啥好说的。。。骗分就完事了😋
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
sc.close();
if (n == 1) {
System.out.println(1);
return;
}
int[] dp = new int[100005];
dp[0] = 1;
dp[1] = 1;
int idx = 3, temp = 1;
for (int i = 2;; i++) {
idx++;
for (int j = 1; j < i; j++) {
int t = dp[j];
dp[j] = temp + dp[j];
temp = t;
if (dp[j] == n) {
System.out.println(idx+1);
return;
}
idx++;
}
dp[i] = 1;
idx++;
}
}
}I：双向排序
【问题描述】
确定一个序列 (a_1,a_2,…, a_n) = (1, 2,…, n) ，其中每个a_i等于i。小蓝计划对该序列执行m次操作，在每一次操作中他可以选择以下两种不同的排序方式中的一种：一种是对前q_i个元素进行降序排列；另一种是对从第q_i个元素开始一直到末尾的所有元素进行升序排列。希望确定经过这些操作后最终的序列状态。
【输入格式】
输入的第一行包括两个整数n, m, 分别代表序列的长度与操作次数。随后m行详细描述了对序列的操作。每条操作记录具体说明如下：第i(1 ≤ i≤ m})行为每条操作记录包括两个参数：操作类型pi(取值范围为{0, 1})以及指定位置qi(取值范围为正整数)。当pi= 0时, 表示需要将前qi}个元素进行降序排列; 当$pi= 1时, 则是从位置$qi}$开始一直到末尾的所有元素进行升序排列。
【输出格式】
输出一行内容由 n 个整数组成，并以一个空格分隔相邻的整数来表示操作完成后所形成的序列
【样例输入】
3 3
0 3
1 2
0 2
【样例输出】
3 1 2
【样例说明】
原数列为 (1,2,3)。
第 1 步后为 (3,2,1)。
第 2 步后为 (3,1,2)。
第 3 步后为 (3,1,2)。与第 2 步操作后相同，因为前两个数已经是降序了。
【评测用例规模与约定】
对于 30% 的评测用例，n , m ≤ 1000；
对于 60% 的评测用例，n , m ≤ 5000；
对于所有评测用例，1 ≤ n , m ≤ 100000，0 ≤ a_i ≤ 1，1 ≤ b_i ≤ n。
思路大概是lazy？可惜我没有想出来，无脑排序骗分，代码太丢人就不放了😅
J：括号序列
【问题描述】
考虑任意一个由圆括号构成的序列，在不增加多余字符的前提下，请问有多少种本质不同的方式可以通过适当补充使其成为一个合法的表达式？如果在某一特定位置上一个方案使用左括号而另一方案使用右括号，则称这两个方案的本质不同。举例而言，在((()的情况下仅需补充两个字符即可使其成为一个合法的表达式，并且有五种本质不同的补充方式：(())(()), (()(())), (()()), ()(()()), 以及 ((())).
【输入格式】
从标准输入读取一行数据，并将其赋值给变量 s；该变量表示由左括号和右括号组成的序列，在此过程中仅涉及左括弧与右括弧两种类型的字符。
【输出格式】
输出一个整数表示答案，答案可能很大，请输出答案除以 1000000007 (即
10^9 + 7) 的余数。
【样例输入】
((()
【样例输出】
5
【评测用例规模与约定】
对于 40\% 的评测用例，|s| ≤ 200 。
对于所有评测用例，1 ≤ |s| ≤ 5000 。
啊，是dp😨，我死了