2021第十二届蓝桥杯省赛JAVA B组 题目+答案（复现赛）

• A：ASC
• B：卡片
• C：直线
• D：货物摆放
• E：路径
• • Floyed
  • Dijkstra
• F：时间显示
• G：最少砝码
• H：杨辉三角形
• I：双向排序
• J：括号序列

A：ASC

【问题描述】已知大写字母 A 的 ASCII 码为 65，请问大写字母 L 的 ASCII 码是多少？【答案】76

签到题(*^▽^*)

public class Main {public static void main(String[] args) {System.out.println((int) 'L');}}

B：卡片

【问题描述】​ 小蓝有很多数字卡片，每张卡片上都是数字 0 到 9。​ 小蓝准备用这些卡片来拼一些数，他想从 1 开始拼出正整数，每拼一个，就保存起来，卡片就不能用来拼其它数了。​ 小蓝想知道自己能从 1 拼到多少。​ 例如，当小蓝有 30 张卡片，其中 0 到 9 各 3 张，则小蓝可以拼出 1 到 10，但是拼 11 时卡片 1 已经只有一张了，不够拼出 11。​ 现在小蓝手里有 0 到 9 的卡片各 2021 张，共 20210 张，请问小蓝可以从 1 拼到多少？【答案】3181

用一个长度为 10 的数组存储 0 到 9 剩余的卡片，每一个数字分别对每一位的卡片减1，如果某一卡片剩余为 0 就代表不能拼出当前卡片，然后输出上一个卡片就好了

分析：从1开始遍历，判断遍历到的数可否用目前的卡片拼出来，可以的话，继续遍历，否则输出答案（答案为现在遍历到的数减1）。

Cpp

#includeusing namespace std;#include#includetypedef long long int ll;int arr[10];bool check (ll x){ll s;while (x > 0) {arr[x % 10]--;if (arr[x % 10] < 0)return 0;x /= 10;}return 1;}int main () {fill(arr, arr+10, 2021);for (int i = 1; i <= 5000; i++) {if (!check(i)) {cout << i-1 << endl;break;}}}

Java

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']--;}}}}

大佬API玩得很⑥！

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 = k x + b y=kx+b 计算出斜率 k 和 b，然后去重。不过 k还有可能是小数，用double 处理，精度爆炸了！最后的实现方法是用 String 表示分数，Set去重，然后还要做些细节的处理。

import java.util.*;class Line {String k;String b;@Overridepublic boolean equals(Object o) {Line line = (Line) o;return Objects.equals(k, line.k) && Objects.equals(b, line.b);}@Overridepublic 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());}}

思路2：

分析：枚举两个不同的点，两点确定一条直线。具体的，直线由y=kx+b表示，看有多少种（k,b）的组合。但由于k和b都是浮点数，Java中是不能够通过==直接判断两个浮点数是否相等的，为此我们用"(b2 - b1) / (a2 - a1) (b1 * (a2 - a1) - a1 * (b2 - b1) / (a2 - a1))"字符串的形式表示一根直线。然后通过Set集合去重，自定义的类需要通过重写equals()方法和hashCode()方法才能被Set集合去重。

import java.util.*;public class Main {public static void main(String[] args) {Set<String> ans = new HashSet<String>();for(int a1 = 0; a1 <= 19; a1++) {for(int b1 = 0; b1 <= 20; b1++) {for(int a2 = 0; a2 <= 19; a2++) {for(int b2 = 0; b2 <= 20; b2++) {// 斜率不存在和斜率为0的特殊情况，我们可以手动计算无需特殊判断if(a1 == a2 || b1 == b2) {continue;}// 以分子/分母的形式表达斜率k和截距b时，分子和分母需要是最简的形式StringBuilder sb = new StringBuilder();int up = b2 - b1;int down = a2 - a1;int r = gcd(up, down);sb.append(up / r + " ");sb.append(down / r + " ");up = b1 * down - a1 * up;r = gcd(up, down);sb.append(up / r + " ");sb.append(down / r);ans.add(sb.toString());}}}}// 斜率不存在的直线20根，斜率为0的直线21根System.out.println(ans.size() + 20 + 21);}static int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);}}

D：货物摆放

【问题描述】​小蓝有一个超大的仓库，可以摆放很多货物。​ 现在，小蓝有 n 箱货物要摆放在仓库，每箱货物都是规则的正方体。小蓝规定了长、宽、高三个互相垂直的方向，每箱货物的边都必须严格平行于长、宽、高。​ 小蓝希望所有的货物最终摆成一个大的立方体。即在长、宽、高的方向上分别堆 L、W、H 的货物，满足 n = L × W × H。​ 给定 n，请问有多少种堆放货物的方案满足要求。​ 例如，当 n = 4 时，有以下 6 种方案：1×1×4、1×2×2、1×4×1、2×1×2、2×2×1、4×1×1。​ 请问，当 n = 2021041820210418 （注意有 16 位数字）时，总共有多少种方案？【答案】2430

遍历这个大数的所有因数，然后对这些因数进行全排序，找到所有三个相乘为大数的排序，要注意的一点是得对大数取个平方根，加快速度。

枚举2021041820210418的约数即可，对约数进行多重循环枚举，对枚举出来的三个数字进行全排列。即可得出答案。

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(1);System.out.println(count);}static void dfs(long now) {if (temp.size() == 3) {if (now == n) {count++;}return;}for (int i = 0; i < yn.size(); i++) {temp.addLast(yn.get(i));dfs(now * yn.get(i));temp.removeLast();}}}

全排列及去重代码值得学习！

思路2：

分析：给出一个数n，求多少个三元组（L，W，H）使得L x W x H等于n。同时三元组是考虑顺序的，L，W，H是n的因数，即n % L == 0 && n % W == 0 && n % H == 0，为此，我们可以先将n的所有因数求出来，然后三重循环遍历L,W,H，若它们相乘等于n，则找到了一种方案。（暴力）

import java.util.*;public class Main {public static void main(String[] args) {// 常数默认值为int，告诉编译器它是long型常量long n = 2021041820210418l;int ans = 0;List<Long> l = new ArrayList<>();for(long i = 1; i <= Math.sqrt(n); i++){if(n % i == 0){l.add(i);if(i != n / i){// 实现上面的去重操作l.add(n / i);}}}for(int i = 0; i < l.size(); i++){for(int j = 0; j < l.size(); j++){if(l.get(i) * l.get(j) > n){// 剪枝操作continue;}for(int k = 0; k < l.size(); k++){if(l.get(i) * l.get(j) * l.get(k) == n){ans++;}}}}System.out.println(ans);}}

E：路径

【问题描述】​ 小蓝学习了最短路径之后特别高兴，他定义了一个特别的图，希望找到图中的最短路径。​ 小蓝的图由 2021 个结点组成，依次编号 1 至 2021。​ 对于两个不同的结点 a, b，如果 a 和 b 的差的绝对值大于 21，则两个结点之间没有边相连；如果 a 和 b 的差的绝对值小于等于 21，则两个点之间有一条长度为 a 和 b 的最小公倍数的无向边相连。​ 例如：结点 1 和结点 23 之间没有边相连；结点 3 和结点 24 之间有一条无向边，长度为 24；结点 15 和结点 25 之间有一条无向边，长度为 75。​ 请计算，结点 1 和结点 2021 之间的最短路径长度是多少。【答案】10266837

直接建图（最大公约数GCD，最小公倍数）然后 floyd 或 dijkstra，暴力即可求出！

Floyed

#includeusing namespace std;#include#includetypedef long long int ll;int arr[2022][2022];int gcd(int a, int b) {return b ? gcd(b, a%b) : a;}int gcd2(int a, int b) {int c = 0;while (b > 0) {c = a % b;a = b;b = c;}return a;}int get(int a, int b) {return a*b/gcd(a, b);}int maxn = (int)1e9;int main () {int res;for (int i = 1; i <= 2021; i++) {for (int j = 1; j <= 2021; j++) {arr[i][j] = abs(i-j) > 21 ? maxn : get(i, j);}}for (int k = 1; k <= 2021; k++) {for (int i = 1; i <= 2021; i++) {for (int j = 1; j <= 2021; j++) {arr[i][j] = min(arr[i][j], arr[i][k] + arr[k][j]);}}}cout << arr[1][2021] << endl;}

Dijkstra

分析：题目意思很明确，求源点到某个点的最短路径。最短路问题有两个常见的算法，Dijkstra算法和Floyed算法。本题适合用Dijkstra算法，为此我们先建图，图用二维矩阵e存储，dist数组表示源点到某个点的最短距离。最后输出dist[2021]的值。

import java.util.*;public class Main {public static void main(String[] args) {int[][] e = new int[2022][2022];int[] dist = new int[2022];boolean[] visit = new boolean[2022];Arrays.fill(dist, Integer.MAX_VALUE);for(int i = 1; i <= 2021; i++){for(int j = 1; j <= 2021; j++){if(i == j){e[i][j] = 0;}else{if(Math.abs(i - j) <= 21){e[i][j] = i * j / gcd(i, j);}else{e[i][j] = Integer.MAX_VALUE;}}}}dist[1] = 0;for(int i = 1; i <= 2021; i++){int u = 0, min = Integer.MAX_VALUE;for(int j = 1; j <= 2021; j++){if(!visit[j] && dist[j] < min){min = dist[j];u = j;}}visit[u] = true;for(int j = 1; j <= 2021; j++){if(e[u][j] != Integer.MAX_VALUE && dist[u] + e[u][j] < dist[j]){dist[j] = dist[u] + e[u][j];}}}System.out.println(dist[2021]);}static int gcd(int a, int b){return b == 0 ? a : gcd(b, a % b);}}

F：时间显示

【问题描述】​ 小蓝要和朋友合作开发一个时间显示的网站。在服务器上，朋友已经获取了当前的时间，用一个整数表示，值为从 1970 年 1 月 1 日 00:00:00 到当前时刻经过的毫秒数。​ 现在，小蓝要在客户端显示出这个时间。小蓝不用显示出年月日，只需要显示出时分秒即可，毫秒也不用显示，直接舍去即可。给定一个用整数表示的时间，请将这个时间对应的时分秒输出。【输入格式】输入一行包含一个整数，表示时间。【输出格式】​ 输出时分秒表示的当前时间，格式形如 HH:MM:SS，其中 H H HHHH 表示时，值为0到23，M表示分，值为0到59，S表示秒，值为 0 到 59 。时、分、秒不足两位时补前导 0。【样例输入1】46800999【样例输出1】13:00:00【样例输入2】1618708103123【样例输出2】01:08:23

一看到 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));}}

模拟过程：

Java:

import java.util.Scanner;public class Main {public static String tos(long x){if(x<10)return "0"+x;else return ""+x;}public static void main(String[] args) {Scanner sc=new Scanner(System.in);long n=sc.nextLong();n%=(1000*60*60*24);n/=1000;System.out.println(tos(n/3600)+":"+tos((n/60)%60)+":"+tos(n%60));}}

Cpp:

#includeusing namespace std;#includestring get(long x) {std::string xx = std::to_string(x); // 整数变字符串int y = std::stoi("1");// 字符串变整型if (x < 10) {return "0"+xx;} else {return ""+xx;}}int main(){cout << get(101) << endl;long s;cin >> s; s %= (1000*60*60*24);s /= 1000;cout << get(s/3600) << ":" << get((s/60)%60) << ":" << get(s%60) << endl;}

又一：

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scan = new Scanner(System.in);//在此输入您的代码...long n = scan.nextLong();n /= 1000;// 1s = 1000ms// 1min = 60s = 60000ms// 1h = 60min = 3600s = 3600000msSystem.out.printf("%02d:%02d:%02d", (n % (3600 * 24)) / 3600,(n % 3600) / 60,n % 60);scan.close();}}

秒啊！

G：最少砝码

【问题描述】​ 你有一架天平。现在你要设计一套砝码，使得利用这些砝码可以称出任意小于等于 N 的正整数重量。​ 那么这套砝码最少需要包含多少个砝码？​ 注意砝码可以放在天平两边。【输入格式】输入包含一个正整数 N。【输出格式】输出一个整数代表答案。【样例输入】7【样例输出】3【样例说明】3 个砝码重量是 1、4、6，可以称出 1 至 7 的所有重量。1 = 1；2 = 6 − 4 (天平一边放 6，另一边放 4)；3 = 4 − 1；4 = 4；5 = 6 − 1；6 = 6；7 = 1 + 6；少于 3 个砝码不可能称出 1 至 7 的所有重量。【评测用例规模与约定】对于所有评测用例，1 ≤ N NN ≤ 1000000000。

分析：手动枚举发现符合三进制规律，所以直接三进制计算即可。

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);}}

分析：思维题吧，如果以前没做过的话估计是想不到的，反正我看到之后第一反应是懵的。看到有的文章是这样推理的，称取质量1只需一个砝码1，第二个需要称取质量2，这时添加一个砝码1可以和第一个1组成2，添加砝码2除了可以组成2之外还可以组成3，添加砝码3可以组成2,3,4，添加砝码4的话就不能得到质量2因此不行，由贪心的思想第二个砝码还是选取砝码3好，然后可以依次退出规律。

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：双向排序

【样例输入】3 30 31 20 2【样例输出】3 1 2

J：括号序列

【问题描述】​ 给定一个括号序列，要求尽可能少地添加若干括号使得括号序列变得合法，当添加完成后，会产生不同的添加结果，请问有多少种本质不同的添加结果。​ 两个结果是本质不同的是指存在某个位置一个结果是左括号，而另一个是右括号。​ 例如，对于括号序列 ((()，只需要添加两个括号就能让其合法，有以下几种不同的添加结果：()()()、()(())、(())()、(()()) 和 ((()))。【输入格式】输入一行包含一个字符串 s，表示给定的括号序列，序列中只有左括号和右括号。【输出格式】输出一个整数表示答案，答案可能很大，请输出答案除以 1000000007 (即10^9+7)的余数。【样例输入】((()【样例输出】5【评测用例规模与约定】对于 40% 的评测用例，|s| ≤ 200。对于所有评测用例，1 ≤ |s| ≤ 5000。

参考：Link Link Link

加油!

感谢!

努力!