蓝桥杯|2021年第12届蓝桥杯 Java B组省赛真题详解及小结【第1场省赛 2021.04.18】 java|算法|图搜索算法|数据结构

蓝桥杯 Java B组省赛决赛真题详解及小结汇总【题目下载、2013年(第4届)~2020年(第11届)】

CSDN 蓝桥杯专栏

2013年第04届蓝桥杯 Java B组省赛真题详解及小结

2014年第05届蓝桥杯 Java B组省赛真题详解及小结

2015年第06届蓝桥杯 Java B组省赛真题详解及小结

2016年第07届蓝桥杯 Java B组省赛真题详解及小结

2017年第08届蓝桥杯 Java B组省赛真题详解及小结

2018年第09届蓝桥杯 Java B组省赛真题详解及小结

2019年第10届蓝桥杯 Java B组省赛真题详解及小结

2020年第11届蓝桥杯第1次模拟赛真题详解及小结【Java版】（校内模拟）// 官方讲解视频

2020年第11届蓝桥杯第2次模拟赛真题详解及小结【Java版】// 官方讲解视频

2020年第11届蓝桥杯 C/C++ B组省赛真题详解及小结【第1场省赛 2020.07.05】【Java版】

2020年第11届蓝桥杯 Java B组省赛真题详解及小结【第1场省赛 2020.07.05】

2020年第11届蓝桥杯 Java B组省赛真题详解及小结【第2场省赛 2020.10.17】

2020年第11届蓝桥杯 Java C组省赛真题详解及小结【第1场省赛 2020.07.05】

2021年第12届蓝桥杯 Java B组省赛真题详解及小结【第1场省赛 2021.04.18】

2021年第12届蓝桥杯 Java B组省赛真题详解及小结【第2场省赛 2021.05.09】

2022年第13届蓝桥杯 Java B组省赛真题详解及小结【第1场省赛 2022.04.09】

2015年第06届蓝桥杯 Java B组决赛真题详解及小结

2016年第07届蓝桥杯 Java B组决赛真题详解及小结

2017年第08届蓝桥杯 Java B组决赛真题详解及小结

2018年第09届蓝桥杯 Java B组决赛真题详解及小结

2019年第10届蓝桥杯 Java B组决赛真题详解及小结

2020年第11届蓝桥杯 Java B组决赛真题详解及小结【2020.11.14】

2021年第12届蓝桥杯 Java B组决赛真题详解及小结【2021.06.05】

2022年第13届蓝桥杯 Java B组决赛真题详解及小结【2022.00.00】

目录
一、试题A：ASC
解法一：ASCII计算求解
解法二：类的调用
二、试题B：卡片
解法一：枚举
解法二：朴素解法
解法三：弯道超车
三、试题C：直线
解法一：直线方程集合
解法二：分式消除误差
解法三：平面几何
四、试题D：货物摆放
解法一：暴力搜索
解法二：缩放质因子
五、试题E：路径
解法一：搜索
解法二：搜索-枝剪广搜
解法三：单源最短路径-Dijkstra
解法四：单源最短路径-Floyd
六、试题F：时间显示
解法一：模拟计算
解法二：直接计算
解法三：Java-日期类API
七、试题G：最少砝码
【蓝桥杯|2021年第12届蓝桥杯 Java B组省赛真题详解及小结【第1场省赛 2021.04.18】】解法一：三进制
解法二：变种三进制
八、试题H：杨辉三角形
解法一：类比单调数列
九、试题I：双向排序
解法一：去冗
解法二：填数游戏
解法三：Chtholly Tree
十、试题J：括号序列
解法一
小结

参考博客：

2021第十二届蓝桥杯第一场省赛JAVA B组真题解析（带源码及解析）_王跃坤的博客-CSDN博客

第十二届蓝桥杯 2021年省赛真题 (Java 大学B组) 第一场_NOW I GOT ONE WAY-CSDN博客_蓝桥杯12届java

仅供参考，欢迎指正！部分为个人想法和解题思路，如有错误或不足，欢迎指正。

文章图片
???????
文章图片

一、试题A：ASC

本题总分：5 分

【问题描述】
已知大写字母 A 的 ASCII 码为 65，请问大写字母 L 的 ASCII 码是多少？
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

【答案】：76

解法一：ASCII计算求解

【解析】：从A往后数。

package provincialGames_12_2021_1_JavaB; public class A01_ASC { // 76 public static void main(String[] args) { System.out.println('A' - 0); // 65 System.out.println('B' - 0); // 66 System.out.println('L' - 0); // 76 System.out.println('Z' - 0); // 90 System.out.println(65 + 'L' - 'A'); // 76 System.out.println((int) 'L'); // 76 } }

解法二：类的调用

package provincialGames_12_2021_1_JavaB; public class A01_ASC2 { // 76 public static void main(String[] args) { new A01_ASC2().run(); } void run() { System.out.println(65 + 'L' - 'A'); // 76 System.out.println((int) 'L'); // 76 } }

二、试题B：卡片

本题总分：5 分

【问题描述】
小蓝有很多数字卡片，每张卡片上都是数字 0 到 9。
小蓝准备用这些卡片来拼一些数，他想从 1 开始拼出正整数，每拼一个，就保存起来，卡片就不能用来拼其它数了。
小蓝想知道自己能从 1 拼到多少。
例如，当小蓝有 30 张卡片，其中 0 到 9 各 3 张，则小蓝可以拼出 1 到 10，
但是拼 11 时卡片 1 已经只有一张了，不够拼出 11。
现在小蓝手里有 0 到 9 的卡片各 2021 张，共 20210 张，请问小蓝可以从 1 拼到多少？
提示：建议使用计算机编程解决问题。
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

【答案】：3181

解法一：枚举

【解析】：从1往后枚举即可。

package provincialGames_12_2021_1_JavaB; public class B02_卡片 { // 3181 public static int arr[] = new int[10]; public static boolean del(int x) { while (x != 0) { arr[x % 10]--; if (arr[x % 10] < 0) return false; x /= 10; } return true; } public static void main(String[] args) { for (int i = 0; i < 10; i++) arr[i] = 2021; for (int i = 1; i < 5000; i++) { if (!del(i)) { System.out.println(i - 1); // 3181 break; } } } }

解法二：朴素解法

package provincialGames_12_2021_1_JavaB; public class B02_卡片2 { // 3181 public static void main(String[] args) { new B02_卡片2().run(); } void run() { System.out.println(calc(2021)); // 3181 } int calc(int upper) { int[] count = new int[10]; for (int n = 1, k = 1; ; k = ++n) do { if (++count[k % 10] > upper) return n - 1; } while ((k /= 10) > 0); } }

解法三：弯道超车

【解析】：观察[1,9]这个区间中，[0,9]的出现情况。在[1,9] 中，1至9各出现1次。
把观察的范围扩大到[1,99]，十位的1出现[10,19] 共10次，十位的2出现[20,29]共10次，? ，十位的9出现[90,99]共10次，低位[0,9]重复出现10次，1至9各出现20次，0出现9次。
将这个观察范围继续扩大，会发现1 的使用次数总是不小于0、 2至9，也就是说统计0、2至9是没有意义的。

package provincialGames_12_2021_1_JavaB; public class B02_卡片3 { // 3181 public static void main(String[] args) { new B02_卡片3().run(); } void run() { System.out.println(calc(20)); // 99 } int calc(int upper) { int count = 0; for (int n = 1, k = 1; ; k = ++n) { do if (k % 10 == 1) count++; while ((k /= 10) > 0); if (count > upper) return n - 1; } } }

三、试题C：直线

本题总分：10 分

【问题描述】
在平面直角坐标系中，两点可以确定一条直线。如果有多点在一条直线上，那么这些点中任意两点确定的直线是同一条。
给定平面上 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一旦确定，即直线确定。统计所有数据去重即可。
一种朴素的想法，是将所有点连接起来，去掉重复的线，然后统计。
为了方便表示，这里采用斜截式方程y=kx+b来表示每一条直线，其中k为直线斜率，b为直线在y轴上的截距，并统一不处理斜率不存在的线，将结果加上一个20。
注意！这段程序的结果是不准确的。

package provincialGames_12_2021_1_JavaB; import java.util.HashSet; import java.util.Set; public class C03_直线 { // 40257 public static void main(String[] args) { new C03_直线().run(); } int X = 20, Y = 21; void run() { Set set = new HashSet(); for (int x1 = 0; x1 < X; x1++) for (int y1 = 0; y1 < Y; y1++) for (int x2 = x1; x2 < X; x2++) for (double y2 = 0; y2 < Y; y2++) if (x1 != x2) { double k = (y2 - y1) / (x2 - x1); double b = -x1 * k + y1; set.add(new Line(k, b)); } System.out.println(set.size() + X); // 41255 } class Line { double k, b; Line(double b, double k) { this.k = k; this.b = b; }@Override public boolean equals(Object obj) { return k == ((Line) obj).k && b == ((Line) obj).b; }@Override public int hashCode() { return (int) k ^ (int) b; } } }

解法二：分式消除误差

【解析】：斜率在浮点数表示下，精度那是参差不齐，诚然可以将误差限制在一个范围内，当绝对差落入当中时，我们就将其视为值相同。但是对于这种需要可表示的范围小的时候，我们可以定义分式来做到无误差，而不是控制精度。

package provincialGames_12_2021_1_JavaB; import java.util.HashSet; import java.util.Set; public class C03_直线2 { // 40257 public static void main(String[] args) { new C03_直线2().run(); } int X = 20, Y = 21; void run() { Set set = new HashSet(); for (int x1 = 0; x1 < X; x1++) for (int y1 = 0; y1 < Y; y1++) for (int x2 = x1; x2 < X; x2++) for (int y2 = 0; y2 < Y; y2++) if (x1 != x2) { Fraction k = new Fraction(y2 - y1, x2 - x1); Fraction b = new Fraction(y1 * (x2 - x1) - x1 * (y2 - y1), x2 - x1); set.add(new Line(k, b)); } System.out.println(set.size() + X); // 40257 } class Fraction { int numerator, denominator; Fraction(int numerator, int denominator) { int gcd = gcd(numerator, denominator); this.denominator = denominator / gcd; this.numerator = numerator / gcd; }int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }@Override public boolean equals(Object obj) { return this.numerator == ((Fraction) obj).numerator && this.denominator == ((Fraction) obj).denominator; } } class Line { Fraction k, b; Line(Fraction b, Fraction k) { this.k = k; this.b = b; }@Override public boolean equals(Object obj) { return this.k.equals(((Line) obj).k) && this.b.equals(((Line) obj).b); }@Override public int hashCode() { return k.denominator; } } }

解法三：平面几何

【解析】：这是一个平面直角坐标系，原点与(1,2)连成一条线段。

文章图片

我们将经过这两点的直线，以及这条直线经过的点与该点于横竖轴的垂线标记出来。

文章图片

显然，若直线经过(x1 , y1)、(x2 , y2)两点，那么它必然也经过(x1 + k(x1 ? x2), y1 + k(y1 ? y2))，k∈Z。
若在连接一条直线时，将所有直线经过的点标记起来，在下次遇到已经标记过的两点，我们便可直接跳过。

package provincialGames_12_2021_1_JavaB; public class C03_直线3 { // 40257 public static void main(String[] args) { new C03_直线3().run(); } int X = 20, Y = 21; void run() { int count = 0; boolean[][][][] marked = new boolean[X][Y][X][Y]; for (int x1 = 0; x1 < X; x1++) for (int y1 = 0; y1 < Y; y1++) { marked[x1][y1][x1][y1] = true; for (int x2 = 0; x2 < X; x2++) for (int y2 = 0; y2 < Y; y2++) { if (marked[x1][y1][x2][y2]) continue; int x = x1, y = y1, xOffset = x - x2, yOffset = y - y2; while (x >= 0 && x < X && y >= 0 && y < Y) { x += xOffset; y += yOffset; } x -= xOffset; y -= yOffset; while (x >= 0 && x < X && y >= 0 && y < Y) { for (int i = x - xOffset, j = y - yOffset; i >= 0 && i < X && j >= 0 && j < Y; i -= xOffset, j -= yOffset) { marked[x][y][i][j] = marked[i][j][x][y] = true; } x -= xOffset; y -= yOffset; } count++; } } System.out.println(count); // 40257 } }

四、试题D：货物摆放

本题总分：10 分

【问题描述】
小蓝有一个超大的仓库，可以摆放很多货物。
现在，小蓝有 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的约数，对约数进行多重循环枚举；对枚举出来的三个数字进行全排列，即可得出答案。
每届必考的基本算术定理。
直接套两 for 也不是不行，但这么写出来的程序，通常到比赛结束都跑不完。
因此我们要避免无效因子的判断，这里统计的为质因子分成三份，可能的组合个数，它与原命题等价。
没什么好讲的。只用套两 for 是因为一个数的因子只能成对出现，扫一下数盲。

package provincialGames_12_2021_1_JavaB; import java.util.ArrayDeque; import java.util.ArrayList; import java.util.List; public class D04_货物摆放 { // 2430 public static void main(String[] args) { new D04_货物摆放().run(); } long n = 2021041820210418L; void run() { List exps0 = new ArrayList(); ArrayDeque exps1 = new ArrayDeque(); for (int k = 2; k <= n; k++) if (n % k == 0) { int e = 0; while (n % k == 0) { n /= k; e++; } exps0.add(e); } System.out.println(dfs(exps0, exps1, 0)); // 2430 } int dfs(List exps0, ArrayDeque exps1, int cur) { if (cur == exps0.size()) { int comb = 1; for (int exp : exps1) comb *= exp + 1; return comb; } int ans = 0; for (int i = exps0.get(cur); i >= 0; i--) { exps1.push(i); ans += dfs(exps0, exps1, cur + 1); exps1.pop(); } return ans; } }

解法二：缩放质因子

【解析】：举个例子，
当n=9时，有6种方案：1×1×9、1×3×3、1×9×1、3×1×3、3×3×1、9×1×1；
当n=25时，有6种方案：1×1×25、1×5×5、?；
当n=p^2时，有6种方案：1×1×p^2、1×p×p、?；其中，p为质数。
其实上例解法当中，我们就能发现，组合的个数与其具体的值无关，它只与质因数指数挂钩。
2021041820210418 = 2 × 3^3 × 17 × 131 × 2857 × 5882353
如果我们找最小的几个质数来代替它们，得到的新数字 2^3 × 3 × 5 × 7 × 11 × 13 = 120120 与 2021041820210418 在这个命题下等价。而 120120的大小就足够我们真暴搜把它的全部因数组合找到了。

package provincialGames_12_2021_1_JavaB; import java.util.ArrayList; import java.util.List; public class D04_货物摆放2 { // 2430 public static void main(String[] args) { new D04_货物摆放2().run(); } long N = 2021041820210418L; void run() { List exps = new ArrayList(); for (int k = 2; k <= N; k++) if (N % k == 0) { int e = 0; while (N % k == 0) { N /= k; e++; } exps.add(e); } exps.sort((a, b) -> (b - a)); int n = 1, p = 2, ans = 0; for (int exp : exps) { for (int i = 2; i * i <= p; i++) if (p % i == 0) { i = 1; p++; } while (exp-- > 0) n *= p; p++; } for (int a = 1; a <= n; a++) if (n % a == 0) for (int b = 1; b <= n; b++) if (n / a % b == 0) ans++; System.out.println(ans); // 2430 } }

五、试题E：路径

本题总分：15 分

【问题描述】
小蓝学习了最短路径之后特别高兴，他定义了一个特别的图，希望找到图中的最短路径。
小蓝的图由 2021 个结点组成，依次编号 1 至 2021。
对于两个不同的结点 a, b，如果 a 和 b 的差的绝对值大于 21，则两个结点之间没有边相连；如果 a 和 b 的差的绝对值小于等于 21，则两个点之间有一条长度为 a 和 b 的最小公倍数的无向边相连。
例如：结点 1 和结点 23 之间没有边相连；结点 3 和结点 24 之间有一条无向边，长度为 24；结点 15 和结点 25 之间有一条无向边，长度为 75。
请计算，结点 1 和结点 2021 之间的最短路径长度是多少。
提示：建议使用计算机编程解决问题。
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

【答案】：10266837

解法一：搜索

【解析】：DP思想，从2开始到2021，每个位置分别从他之前的21个位置走过来，对21个数据求最小值即可。
题目已经说的够清楚了，建一个有2021个顶点
文章图片
条边的无向图，跑图上的算法就完事了。
还有，细节就是整形是否会溢出，我们取(1,2021]中最大的质数2017与2021^2相乘，得到的结果还是有点夸张的，虽然经过测试，可能的线路权值合至多不会超过2^31-1，但毕竟是面向竞赛，考虑甄别的时间成本，直接使用长整形更为划算。
深度优先搜索：2021个顶点，绝大多数顶点都连有2×21条边，别深搜了，一搜就是compilaition completed successfully in 500ms(4 hour ago)就，电脑跟选手对着坐牢。
记忆化搜索：
深度优先搜索，在搜索最优结果时，通常需要完整的枚举全部可能的问题状态。
但在这个问题状态的集合中，所有可选方案的 “后缀” 都是相同，也就是所有可选的分支，它们都是以同一个节点结尾。
如果我们将已经搜索到的节点到目标节点间的最短路径保存下来，在再次搜索到这个 “后缀” 的分支时直接返回。
那么问题就可能在一个较短的时间内解决。这也是所谓的记忆化搜索。???????

package provincialGames_12_2021_1_JavaB; import java.util.ArrayList; import java.util.List; public class E05_路径 { // 10266837 public static void main(String[] args) { new E05_路径().run(); } int N = 2021; int[] weight = new int[N + 1]; List[] graph = new List[N + 1]; boolean[] visited = new boolean[N + 1]; void run() { for (int i = 1; i <= N; i++) graph[i] = new ArrayList(); for (int v = 1; v < N; v++) for (int w = v + 1; w <= min(v + 21, N); w++) { graph[v].add(new Edge(w, lcm(v, w))); graph[w].add(new Edge(v, lcm(v, w))); } visited[1] = true; System.out.println(dfs(1)); // 10266837 } int dfs(int v) { if (v == N) return 0; if (weight[v] != 0) return weight[v]; int min = 0x7FFFFFFF; for (Edge edge : graph[v]) { if (visited[edge.w]) continue; visited[edge.w] = true; min = min(min, dfs(edge.w) + edge.weight); visited[edge.w] = false; } return weight[v] = min; } int min(int a, int b) { return a < b ? a : b; } int lcm(int a, int b) { return a * b / gcd(a, b); } int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } class Edge { int w, weight; Edge(int w, int weight) { this.weight = weight; this.w = w; } } }

解法二：搜索-枝剪广搜

【解析】：其实朴素的去搜索，不论深搜还是广搜，在竞赛里都是很冒进的行为，影响这两个算法执行效率的因素太多。
当然，要是没有其他的思路，也只能死马当活马医了。幸运的是，只需简单的枝剪，就能在很短的时间计算出结果。

package provincialGames_12_2021_1_JavaB; import java.util.PriorityQueue; import java.util.ArrayList; import java.util.Arrays; import java.util.Queue; import java.util.List; public class E05_路径2 { // 10266837 public static void main(String[] args) { new E05_路径2().run(); } int N = 2021; void run() { List[] graph = new List[N + 1]; long[] visited = new long[N + 1]; for (int i = 1; i <= N; i++) graph[i] = new ArrayList(); for (int v = 1; v < N; v++) for (int w = v + 1; w <= min(v + 21, N); w++) { graph[v].add(new Edge(w, lcm(v, w))); graph[w].add(new Edge(v, lcm(v, w))); } Queue queue = new PriorityQueue(); Arrays.fill(visited, Long.MAX_VALUE); queue.offer(new Vertex(1, 0)); Vertex V = null; while (queue.size() > 0) { V = queue.poll(); if (V.v == N) break; if (V.weight >= visited[V.v]) continue; visited[V.v] = V.weight; for (Edge edge : graph[V.v]) queue.offer(new Vertex(edge.w, edge.weight + V.weight)); } System.out.println(V.weight); // 10266837 } int min(int a, int b) { return a < b ? a : b; } int lcm(int a, int b) { return a * b / gcd(a, b); } int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } class Edge { int w, weight; Edge(int w, int weight) { this.weight = weight; this.w = w; } } class Vertex implements Comparable { int v; long weight; Vertex(int v, long weight) { this.weight = weight; this.v = v; }@Override public int compareTo(Vertex V) { return Long.compare(this.weight, V.weight); } } }

解法三：单源最短路径-Dijkstra

【解析】：题目给出的图显然是个边加权，权重非负的无向图，跑遍Dijkstra就完事了。

package provincialGames_12_2021_1_JavaB; import java.util.PriorityQueue; import java.util.ArrayList; import java.util.Queue; import java.util.List; public class E05_路径3 { // 10266837 public static void main(String[] args) { new E05_路径3().run(); } int N = 2021; void run() { boolean[] marked = new boolean[N + 1]; List[] graph = new List[N + 1]; long[] distTo = new long[N + 1]; for (int i = 1; i <= N; i++) { graph[i] = new ArrayList(); distTo[i] = Long.MAX_VALUE; } for (int v = 1; v < N; v++) for (int w = v + 1; w <= min(v + 21, N); w++) { graph[v].add(new Edge(w, lcm(v, w))); graph[w].add(new Edge(v, lcm(v, w))); } Queue queue = new PriorityQueue(); queue.offer(new Vertex(1, distTo[1] = 0)); while (queue.size() > 0) { Vertex V = queue.poll(); if (marked[V.v]) continue; marked[V.v] = true; for (Edge edge : graph[V.v]) if (distTo[edge.w] > distTo[V.v] + edge.weight) queue.offer(new Vertex(edge.w, distTo[edge.w] = distTo[V.v] + edge.weight)); } System.out.println(distTo[N]); // 10266837 } int min(int a, int b) { return a < b ? a : b; } int lcm(int a, int b) { return a * b / gcd(a, b); } int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } class Edge { int w, weight; Edge(int w, int weight) { this.weight = weight; this.w = w; } } class Vertex implements Comparable { int v; long dist; Vertex(int v, long dist) { this.dist = dist; this.v = v; }@Override public int compareTo(Vertex V) { return Long.compare(this.dist, V.dist); } } }

解法四：单源最短路径-Floyd

【解析】：如果是一道最短路径的结果题。竞赛时限内能运行完 O(n^3)的程序。那其实无脑套Floyd就行。

package provincialGames_12_2021_1_JavaB; public class E05_路径4 { // 10266837 public static void main(String[] args) { new E05_路径4().run(); } int N = 2021; void run() { long[][] floyd = new long[N + 1][N + 1]; for (int v = 1; v < N; v++) for (int w = v + 1; w <= min(N, v + 21); w++) floyd[v][w] = floyd[w][v] = lcm(v, w); for (int k = 1; k <= N; k++) for (int v = 1; v <= N; v++) if (floyd[v][k] == 0) continue; else for (int w = 1; w <= N; w++) if (floyd[k][w] == 0) continue; else if (floyd[v][w] == 0 || floyd[v][k] + floyd[k][w] < floyd[v][w]) floyd[v][w] = floyd[v][k] + floyd[k][w]; System.out.println(floyd[1][N]); // 10266837 } long min(int a, int b) { return a < b ? a : b; } int lcm(int a, int b) { return a * b / gcd(a, b); } int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } }

六、试题F：时间显示

时间限制: 1.0s 内存限制: 512.0MB 本题总分：15 分

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

解法一：模拟计算

【解析】：按照题目所说模拟过程即可。

文章图片

文章图片

package provincialGames_12_2021_1_JavaB; import java.util.Scanner; public class F06_时间显示 { 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)); } }

解法二：直接计算

文章图片

文章图片

package provincialGames_12_2021_1_JavaB; import java.util.Scanner; public class F06_时间显示3 { public static void main(String[] args) { new F06_时间显示3().run(); } void run() { long t = new Scanner(System.in).nextLong(); System.out.printf("%02d:%02d:%02d", t / 3600000 % 24, t / 60000 % 60, t / 1000 % 60); } }

解法三：Java-日期类API

文章图片

package provincialGames_12_2021_1_JavaB; import java.util.Scanner; import java.time.LocalTime; import java.time.format.DateTimeFormatter; public class F06_时间显示3 { public static void main(String[] args) { new F06_时间显示3().run(); } void run() { System.out.println(LocalTime.MIDNIGHT.plusSeconds(new Scanner(System.in).nextLong() / 1000) .format(DateTimeFormatter.ISO_LOCAL_TIME)); Scanner sc = new Scanner(System.in); long n = sc.nextLong(); System.out.println(LocalTime.MIDNIGHT.plusSeconds(n / 1000).format(DateTimeFormatter.ISO_LOCAL_TIME)); } }

七、试题G：最少砝码

时间限制: 1.0s 内存限制: 512.0MB 本题总分：20 分

【问题描述】
你有一架天平。现在你要设计一套砝码，使得利用这些砝码可以称出任意小于等于 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 ≤ 1000000000。

解法一：三进制

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

package provincialGames_12_2021_1_JavaB; import java.util.Scanner; public class G07_最少砝码 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); long x = sc.nextLong(); long sum = 1, cur = 1; while (sum < x) { sum += Math.pow(3, cur); cur++; } System.out.println(cur); } }

解法二：变种三进制

【解析】：规律题。第十二届蓝桥杯 2021年省赛真题 (Java 大学B组) 第一场

文章图片

package provincialGames_12_2021_1_JavaB; import java.util.Scanner; public class G07_最少砝码2 { public static void main(String[] args) { new G07_最少砝码2().run(); } void run() { long N = new Scanner(System.in).nextLong(), ans = 1; for (long pow3 = 1; pow3 < N; pow3 = pow3 * 3 + 1, ans++) ; System.out.println(ans); } }

八、试题H：杨辉三角形

时间限制: 5.0s 内存限制: 512.0MB 本题总分：20 分

【问题描述】
下面的图形是著名的杨辉三角形：
如果我们按从上到下、从左到右的顺序把所有数排成一列，可以得到如下数列：

文章图片

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。

解法一：类比单调数列

【解析】：按照题目所说模拟过程即可。
杨辉三角最外层全部是1，第二层则是自然数序列。

文章图片

因为杨辉三角是左右对称的，因此我们可以忽略右边(左边的数字总是比右边先出现)，并将数字按层分成若干序列。

文章图片

由于序列都是从上置下单调递增的，我们可以在每一个这种序列上，二分查找N的位置，特别的，N=1时直接输出1。
此外，杨辉三角第n行m列=
文章图片
，这个数字增长的非常快。
文章图片
。
也就至多在14条(除去最外两层)这样的序列中查找N的位置，因为序列的单调性不允许N的出现。

package provincialGames_12_2021_1_JavaB; import java.util.Scanner; public class H08_杨辉三角形 { public static void main(String[] args) { new H08_杨辉三角形().run(); } int N; void run() { N = new Scanner(System.in).nextInt(); if (N == 1) System.out.println(1); else { long ans = (N + 1L) * N / 2 + 2; for (int m = 2; m < 16; m++) { int start = m * 2, end = N; while (start <= end) { int mid = start + end >> 1; if (C(mid, m) == N) { ans = min(ans, (mid + 1L) * mid / 2 + m + 1); break; } if (C(mid, m) > N) end = mid - 1; else start = mid + 1; } } System.out.println(ans); } } long min(long a, long b) { return a < b ? a : b; } long C(int n, int m) { long num = 1; for (int nm = 1; nm <= m; n--, nm++) if ((num = num * n / nm) > N) return num; return num; } }

九、试题I：双向排序

时间限制: 5.0s 内存限制: 512.0MB 本题总分：25 分

【问题描述】
给定序列 (a1, a2, · · · , an) = (1, 2, · · · , n)，即 ai = i。
小蓝将对这个序列进行 m 次操作，每次可能是将 a1, a2, · · · , aqi 降序排列，或者将 aqi , aqi+1, · · · , an 升序排列。
请求出操作完成后的序列。
【输入格式】
输入的第一行包含两个整数 n, m，分别表示序列的长度和操作次数。
接下来 m 行描述对序列的操作，其中第 i 行包含两个整数 pi , qi 表示操作类型和参数。当 pi = 0 时，表示将 a1, a2, · · · , aqi 降序排列；当 pi = 1 时，表示将 aqi , aqi+1, · · · , an 升序排列。
【输出格式】输出一行，包含 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 ≤ ai ≤ 1，1 ≤ bi ≤ n。

解法一：去冗

【解析】：暴力CMP
第十二届蓝桥杯 2021年省赛真题 (Java 大学B组) 第一场???????

?package provincialGames_12_2021_1_JavaB; import java.io.*; import java.util.*; public class I09_双向排序 { public static void main(String[] args) { new I09_双向排序().run(); } void run() { InputReader in = new InputReader(System.in); PrintWriter out = new PrintWriter(System.out); int n = in.readInt(), m = in.readInt(); Deque deque = new ArrayDeque(); deque.push(new Step(1, 1)); while (m-- > 0) { int p = in.readInt(); int q = in.readInt(); while (deque.size() > 0 && deque.peek().p == p) if (p == 0) q = max(q, deque.pop().q); else q = min(q, deque.pop().q); deque.push(new Step(p, q)); } Integer[] ans = new Integer[n]; for (int i = 0; i < n; i++) ans[i] = i + 1; deque.pollLast(); while (deque.size() > 0) { Step step = deque.pollLast(); if (step.p == 0) Arrays.sort(ans, 0, step.q, (a, b) -> (b - a)); else Arrays.sort(ans, step.q - 1, n); } for (int i = 0; i < n; i++) { out.print(ans[i]); out.print(' '); } out.flush(); } int max(int a, int b) { return a > b ? a : b; } int min(int a, int b) { return a < b ? a : b; } class Step { int p, q; Step(int p, int q) { this.p = p; this.q = q; } } class InputReader { BufferedReader reader; StringTokenizer token; InputReader(InputStream in) { this.reader = new BufferedReader(new InputStreamReader(in)); }String read() { while (token == null || !token.hasMoreTokens()) { try { token = new StringTokenizer(reader.readLine()); } catch (IOException e) { e.printStackTrace(); } } return token.nextToken(); }int readInt() { return Integer.parseInt(read()); } } }

解法二：填数游戏

package provincialGames_12_2021_1_JavaB; import java.io.*; import java.util.*; public class I09_双向排序2 { public static void main(String[] args) { new I09_双向排序2().run(); } void run() { InputReader in = new InputReader(System.in); PrintWriter out = new PrintWriter(System.out); int n = in.readInt(), m = in.readInt(), top; Step[] stack = new Step[m + 1]; for (top = 0; m-- > 0; ) { int p = in.readInt(); int q = in.readInt(); if (p == 0) { while (top > 0 && stack[top].p == p) q = max(q, stack[top--].q); while (top > 1 && stack[top - 1].q <= q) top -= 2; stack[++top] = new Step(p, q); } else if (top > 0) { while (top > 0 && stack[top].p == p) q = min(q, stack[top--].q); while (top > 1 && stack[top - 1].q >= q) top -= 2; stack[++top] = new Step(p, q); } } int[] ans = new int[n + 1]; int a = n, l = 0, r = n - 1; for (int i = 1; i <= top; i++) if (stack[i].p == 0) while (r >= stack[i].q && l <= r) ans[r--] = a--; else while (l + 1 < stack[i].q && l <= r) ans[l++] = a--; if ((top & 1) == 1) while (l <= r) ans[l++] = a--; else while (l <= r) ans[r--] = a--; for (int i = 0; i < n; i++) { out.print(ans[i]); out.print(' '); } out.flush(); } int max(int a, int b) { return a > b ? a : b; } int min(int a, int b) { return a < b ? a : b; } class Step { int p, q; Step(int p, int q) { this.p = p; this.q = q; } } class InputReader { BufferedReader reader; StringTokenizer token; InputReader(InputStream in) { this.reader = new BufferedReader(new InputStreamReader(in)); }String read() { while (token == null || !token.hasMoreTokens()) { try { token = new StringTokenizer(reader.readLine()); } catch (IOException e) { e.printStackTrace(); } } return token.nextToken(); }int readInt() { return Integer.parseInt(read()); } } }

解法三：Chtholly Tree

package provincialGames_12_2021_1_JavaB; import java.io.*; import java.util.*; public class I09_双向排序3 { public static void main(String[] args) { new I09_双向排序3().run(); } void run() { InputReader in = new InputReader(System.in); int n = in.readInt(), m = in.readInt(); Node[] root = new Node[n + 1]; int[] P = new int[n + 1]; Range lower, temp, now; lower = now = new Range(0); for (int i = 1; i <= n; i++) { now = now.next = new Range(i); root[i] = build(1, n, i); } now.next = new Range(n + 1); while (m-- > 0) { int p = in.readInt(); int L = in.readInt(); int R = n; if (p == 0) { R = L; L = 1; } now = lower; while (now.next.L <= L) now = now.next; if (L > now.L) { root[L] = split(root[now.L], L - now.L, P[now.L]); now = now.next = new Range(L, now.next); } temp = now; Node pq = null; while (now.L <= R) { if (now.next.L > R + 1) root[R + 1] = split(root[now.L], R + 1 - now.L, P[R + 1] = P[now.L]); pq = merge(pq, root[now.L]); now = now.next; } if (now.L == R + 1) temp.next = now; else temp.next = new Range(R + 1, now); root[L] = pq; P[L] = p; } StringBuilder ans = new StringBuilder(); while ((lower = lower.next).L <= n) buildAns(ans, root[lower.L], 1, n, P[lower.L]); System.out.println(ans); } Node split(Node tree, int k, int p) { if (tree == null) return null; Node split = new Node(0); if (p == 0) { int K = K(tree.right); if (k <= K) { if (k != K) split.right = split(tree.right, k, p); split.left = tree.left; tree.left = null; } else split.left = split(tree.left, k - K, p); } else { int K = K(tree.left); if (k <= K) { if (k != K) split.left = split(tree.left, k, p); split.right = tree.right; tree.right = null; } else split.right = split(tree.right, k - K, p); } split.k = tree.k - k; tree.k = k; return split; } Node merge(Node tree1, Node tree2) { if (tree1 == null) return tree2; if (tree2 != null) { tree1.k += K(tree2); tree1.left = merge(tree1.left, tree2.left); tree1.right = merge(tree1.right, tree2.right); } return tree1; } Node build(int L, int R, int k) { if (L == R) return new Node(1); Node node = new Node(1); int mid = L + R >> 1; if (k <= mid) node.left = build(L, mid, k); else node.right = build(mid + 1, R, k); return node; } void buildAns(StringBuilder builder, Node root, int L, int R, int p) { if (root == null) return; if (L == R) builder.append(L).append(' '); else { int mid = L + R >> 1; if (p == 0) { buildAns(builder, root.right, mid + 1, R, p); buildAns(builder, root.left, L, mid, p); } else { buildAns(builder, root.left, L, mid, p); buildAns(builder, root.right, mid + 1, R, p); } } } int K(Node node) { return node == null ? 0 : node.k; } class Range { int L; Range next; Range(int L) { this(L, null); }Range(int L, Range next) { this.L = L; this.next = next; } } class Node { int k = 1; Node left, right; Node(int k) { this.k = k; } } class InputReader { BufferedReader reader; StringTokenizer token; InputReader(InputStream in) { this.reader = new BufferedReader(new InputStreamReader(in)); }String read() { while (token == null || !token.hasMoreTokens()) { try { token = new StringTokenizer(reader.readLine()); } catch (IOException e) { e.printStackTrace(); } } return token.nextToken(); }int readInt() { return Integer.parseInt(this.read()); } } }

十、试题J：括号序列

时间限制: 5.0s 内存限制: 512.0MB 本题总分：25 分

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

解法一

【解析】：按照题目所说模拟过程即可。

文章图片

package provincialGames_12_2021_1_JavaB; import java.util.Scanner; public class J10_括号序列 { public static void main(String[] args) { new J10_括号序列().run(); } int mod = 1000000007; void run() { byte[] line = new byte[5555]; try { int n = System.in.read(line, 1, 5050) - 1; System.out.println(calc(line, n, false) * calc(line, n, true) % mod); } catch (java.io.IOException e) { e.fillInStackTrace(); } } long calc(byte[] str, int n, boolean turn) { if (turn) reverse(str, n); int[][] dp = new int[n + 1][n + 2]; int opening = 0; dp[0][0] = 1; for (int i = 1; i <= n; i++) { if (str[i] == '(') { for (int j = 1; j <= n; j++) dp[i][j] = dp[i - 1][j - 1]; opening++; } else { dp[i][0] = (dp[i - 1][0] + dp[i - 1][1]) % mod; for (int j = 1; j <= n; j++) dp[i][j] = (dp[i][j - 1] + dp[i - 1][j + 1]) % mod; if (opening > 0) opening--; } } return dp[n][opening]; } void reverse(byte[] arr, int n) { for (int i = 1, j = n; i <= j; i++, j--) { byte temp = (byte) (arr[i] ^ 1); arr[i] = (byte) (arr[j] ^ 1); arr[j] = temp; } } }

小结