第十四届蓝桥杯大赛软件赛省赛JavaB组解析

╰+攻爆jí腚メ 2023-09-27 17:13 250阅读 0赞

目录

说在前面

试题 A: 阶乘求和

代码：

题目分析：

试题 B: 幸运数字

代码：

题目分析：

试题 D: 矩形总面积

代码：

题目分析：

试题 G: 买二赠一

代码：

题目分析：

试题 H: 合并石子

代码：

题目思路：

说在最后

说在前面

比赛结束啦，可能这是本科生涯的最后一次蓝桥杯啦！赛前也刷了一部分的题，不管最后能不能相约北京，还是要感谢我执梗举办的三十天打卡活动，辛苦啦！

我把这段时间刷的题也也整理成了一个小专栏：《23年蓝桥杯刷题30天打卡》

关于这次蓝桥杯，比赛的时候没有看D题，G和H花了好长时间，呜呜….，等比赛结束的时候边走边看题才知道是送分题，考后相当于是补题了，好遗憾，痛失10分，也许人生就是这样，十之八九是遗憾，但这又有何妨呢，前方康庄大道，还有很多美好的事情等着我呢！！！

下面就把这次我看过的并且感觉能做的题目写一下吧，如有错误，欢迎评论区指正！！

试题 A: 阶乘求和

【问题描述】

令 S = 1! + 2! + 3! + … + 202320232023! ，求 S 的末尾 9 位数字。

提示：答案首位不为 0 。

【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一

个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

代码：

  1. /**
  2.  * @author yx
  3.  * @date 2023-04-08 9:11
  4.  */
  5. public class t1 {
  6.     public static void main(String[] args) {
  7. //        420940313
  8.         long ans=0;
  9.         long temp=1000000000;
  10.         long temp1=1;
  11.         for (long i = 1; i <= 202320232023L ; i++) {
  12.             temp1=((temp1%temp)*(i%temp))%temp;
  13.             ans=(ans%temp+temp1%temp)%temp;
  14.             System.out.println("temp1是："+temp1+"  ans是："+ans+"   i是："+i);
  15.         }
  16. //        System.out.println("答案是："+ans);
  17.     }
  18. }

题目分析：

答案是：420940313

  1. 这道题目最后给的是202320232023的阶乘，这玩意要是用电脑暴力解，估计要很长时间（我一开始也是无脑暴力，但是感觉要好久）
  2. 这题完全不需要开到202320232023，因为从39！开始，后面阶乘和的末尾9位数字就不发生改变了

39d024b0d8ad4e7894b26d6125545a4c.png

试题 B: 幸运数字

试题 B: 幸运数字

本题总分： 5 分

【问题描述】

哈沙德数是指在某个固定的进位制当中，可以被各位数字之和整除的正整

数。例如 126 是十进制下的一个哈沙德数，因为 (126) 10 mod (1+2+6) = 0 ； 126

也是八进制下的哈沙德数，因为 (126) 10 = (176) 8 ， (126) 10 mod (1 + 7 + 6) = 0 ；

同时 126 也是 16 进制下的哈沙德数，因为 (126) 10 = (7 e ) 16 ， (126) 10 mod (7 +

e ) = 0 。小蓝认为，如果一个整数在二进制、八进制、十进制、十六进制下均为

哈沙德数，那么这个数字就是幸运数字，第 1 至第 10 个幸运数字的十进制表示

为： 1 , 2 , 4 , 6 , 8 , 40 , 48 , 72 , 120 , 126 . . . 。现在他想知道第 2023 个幸运数

字是多少？你只需要告诉小蓝这个整数的十进制表示即可。

【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一

个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

代码：

  1. import java.awt.*;
  3. /**
  4.  * @author yx
  5.  * @date 2023-04-08 9:13
  6.  */
  7. public class t2 {
  8.     public static void main(String[] args) {
  9.         int ans=0;
  10.         int i=0;
  11.         while (true){
  12.             i++;
  13.             if(isCheck(i)){
  14.                 ans++;
  15.                 System.out.println(i+"为第"+ans+"个");
  16.             }
  17.             if(ans==2023){
  18.                 break;
  19.             }
  20.         }
  21.         System.out.println("答案是："+i);
  22.     }
  23.     static boolean isCheck(int n){
  24.         String temp1=Integer.toString(n,2);
  25.         String temp2=Integer.toString(n,8);
  26.         String temp3=n+"";
  27.         String temp4=Integer.toString(n,16);
  28.         int temp_1=0;
  29.         int temp_2=0;
  30.         int temp_3=0;
  31.         int temp_4=0;
  32.         for (int i = 0; i < temp1.length(); i++) {
  33.             temp_1+=Integer.parseInt(temp1.substring(i,i+1));
  34.         }
  35.         if(n%temp_1!=0){
  36.             return false;
  37.         }
  38.         for (int i = 0; i < temp2.length() ;i++) {
  39.             temp_2+=Integer.parseInt(temp2.substring(i,i+1));
  40.         }
  41.         if(n%temp_2!=0){
  42.             return false;
  43.         }
  44.         for (int i = 0; i < temp3.length(); i++) {
  45.             temp_3+=Integer.parseInt(temp3.substring(i,i+1));
  46.         }
  47.         if(n%temp_3!=0){
  48.             return false;
  49.         }
  50.         for (int i = 0; i < temp4.length(); i++) {
  51.             if((temp4.substring(i,i+1)).toCharArray()[0]>='a'){
  52.                 temp_4 += (temp4.substring(i,i+1)).toCharArray()[0]-'a'+10;
  53.             }else {
  54.                 temp_4 += Integer.parseInt(temp4.substring(i, i + 1));
  55.             }
  56.         }
  57.         if(n%temp_4!=0){
  58.             return false;
  59.         }
  60.         return true;
  61.     }
  62. }

题目分析：

答案是：215040

  1. 直接把数先进制转换，然后求数位和，判读能否整除数位和就好了
  2. 这题本质考一个进制转换，如果会用Java的API就很简单,前两天我在算法组会分享的时候刚好讲过，还写了题解，还上了热榜，哈哈哈，下面链接的第五题

蓝桥杯最后一战_小羊不会飞的博客-CSDN博客分巧克力_二分题目描述输入格式输出格式输入输出样例说明/提示代码：巧克力 - 优先队列题目描述输入格式输出格式输入输出样例说明/提示代码：思路分析：秘密行动_dp蓝桥杯算法提高-秘密行动题目描述输入格式输出格式样例输入样例输出代码：思路分析：合并果子_优先队列题目描述输入格式输出格式输入输出样例说明/提示代码：思路分析：回文平方数_进制转换API题目描述输入格式输出格式favicon32.icohttps://blog.csdn.net/m0\_55858611/article/details/129960460?spm=1001.2014.3001.5501

6d71c2f9a683481e879f3f96fd27881e.png

试题 D: 矩形总面积

【问题描述】

平面上有个两个矩形 R 1 和 R 2 ，它们各边都与坐标轴平行。设 ( x 1 , y 1 ) 和

( x 2 , y 2 ) 依次是 R 1 的左下角和右上角坐标， ( x 3 , y 3 ) 和 ( x 4 , y 4 ) 依次是 R 2 的左下

角和右上角坐标，请你计算 R 1 和 R 2 的总面积是多少？

注意：如果 R 1 和 R 2 有重叠区域，重叠区域的面积只计算一次。

【输入格式】

输入只有一行，包含 8 个整数，依次是： x 1 ， y 1 ， x 2 ， y 2 ， x 3 ， y 3 ， x 4 和 y 4 。

【输出格式】

一个整数，代表答案。

【样例输入】

2 1 7 4 5 3 8 6

【样例输出】

22

【样例说明】

样例中的两个矩形如图所示：

f88948b32c65454487325c1679df9086.png

【评测用例规模与约定】

对于 20 % 的数据， R 1 和 R 2 没有重叠区域。

对于 20 % 的数据，其中一个矩形完全在另一个矩形内部。

对于 50 % 的数据，所有坐标的取值范围是 [0 , 10 ^3 ] 。

对于 100 % 的数据，所有坐标的取值范围是 [0 , 10^ 5 ] 。

代码：

  1. import java.io.*;
  3. /**
  4.  * @author yx
  5.  * @date 2023-04-08 13:57
  6.  */
  7. public class D {
  8.     static PrintWriter out =new PrintWriter(System.out);
  9.     static BufferedReader ins=new BufferedReader(new InputStreamReader(System.in));
  10.     static StreamTokenizer in=new StreamTokenizer(ins);
  11.     public static void main(String[] args) throws IOException {
  12.         String[] sp=ins.readLine().split(" ");
  13.         int x1=Integer.parseInt(sp[0]);
  14.         int y1=Integer.parseInt(sp[1]);
  15.         int x2=Integer.parseInt(sp[2]);
  16.         int y2=Integer.parseInt(sp[3]);
  17.         int x3=Integer.parseInt(sp[4]);
  18.         int y3=Integer.parseInt(sp[5]);
  19.         int x4=Integer.parseInt(sp[6]);
  20.         int y4=Integer.parseInt(sp[7]);
  21.         long ans=0;
  22.         int max_X=Math.max(Math.max(x1,x2),Math.max(x3,x4));
  23.         int max_Y=Math.max(Math.max(y1,y2),Math.max(y3,y4));
  24.         int max=Math.max(max_X,max_Y);
  25.         int[][] Map=new int[max+1][max+1];
  26.         for (int i = y1; i <= y2-1 ; i++) {
  27.             for (int j = x1; j <= x2-1 ; j++) {
  28.                 Map[i][j]+=1;
  29.             }
  30.         }
  31.         for (int i = y3; i <= y4-1 ; i++) {
  32.             for (int j = x3; j <= x4-1 ; j++) {
  33.                 Map[i][j]+=1;
  34.             }
  35.         }
  36.         for (int i = 0; i <= max_X ; i++) {
  37.             for (int j = 0; j <= max_Y ; j++) {
  38. //                System.out.print(Map[j][i]+" ");
  39.                 if(Map[j][i]>=1){
  40.                     ans++;
  41.                 }
  42.             }
  43. //            System.out.println();
  44.         }
  45.         System.out.println(ans);
  46.     }
  47. }

题目分析：

  1. 这题就是直接暴力模拟（比赛的时候看了一眼题目就直接跳过了，哭死），赛后十分钟解决
  2. 先定义一个int[][]Map，然后遍历两块矩阵，把它们的覆盖的区域全部+1，属于矩阵区域但是不重合的地方Map值为1,重合的地方加了两次其Map值会变成2，不属于矩阵区间的范围当然为0
  3. 最后遍历二维数组Map，统计Map值>=1的个数就是答案

7772d601b1a84e5b8ab0323de8334494.png

试题 G: 买二赠一

【问题描述】

某商场有 N 件商品，其中第 i 件的价格是 A i 。现在该商场正在进行 “ 买二

赠一 ” 的优惠活动，具体规则是：

每购买 2 件商品，假设其中较便宜的价格是 P （如果两件商品价格一样，

则 P 等于其中一件商品的价格），就可以从剩余商品中任选一件价格不超过 P

2

的商品，免费获得这一件商品。可以通过反复购买 2 件商品来获得多件免费商

品，但是每件商品只能被购买或免费获得一次。

小明想知道如果要拿下所有商品（包含购买和免费获得），至少要花费多少

钱？

【输入格式】

第一行包含一个整数 N 。

第二行包含 N 个整数，代表 A 1 , A 2 , A 3 , . . . ， A N 。

【输出格式】

输出一个整数，代表答案。

【样例输入】

7

1 4 2 8 5 7 1

【样例输出】

25

试题 G: 买二赠一

13 第十四届蓝桥杯大赛软件赛省赛 Java 大学 B 组

【样例说明】

小明可以先购买价格 4 和 8 的商品，免费获得一件价格为 1 的商品；再后

买价格为 5 和 7 的商品，免费获得价格为 2 的商品；最后单独购买剩下的一件

价格为 1 的商品。总计花费 4 + 8 + 5 + 7 + 1 = 25 。不存在花费更低的方案。

【评测用例规模与约定】

对于 30 % 的数据， 1 ≤ N ≤ 20 。

对于 100 % 的数据， 1 ≤ N ≤ 5 × 10 5 ， 1 ≤ A i ≤ 10 9 。

代码：

  1. import java.io.*;
  2. import java.util.ArrayList;
  3. import java.util.Collections;
  5. /**
  6.  * @author yx
  7.  * @date 2023-04-08 11:31
  8.  */
  9. public class G3 {
  10.     static PrintWriter out = new PrintWriter(System.out);
  11.     static BufferedReader ins = new BufferedReader(new InputStreamReader(System.in));
  12.     static StreamTokenizer in = new StreamTokenizer(ins);
  14.     public static void main(String[] args) throws IOException {
  15.         String s = ins.readLine();
  16.         int N = Integer.parseInt(s);
  17.         String[] sp = ins.readLine().split(" ");
  18.         ArrayList<Integer> list = new ArrayList<>();
  19.         long ans = 0;
  20.         for (int i = 0; i < N; i++) {
  21.             list.add(Integer.parseInt(sp[i]));
  22.         }
  23.         Collections.sort(list);
  24.         for (int i = 0; list.size()>0 ; i++) {
  25.             int a1 = 0;
  26.             int a2 = 0;
  27.             a1 = list.get(list.size()  - 1);
  28.             list.remove(list.size()  - 1);
  29.             if(list.size() - 1>=0) {
  30.                 a2 = list.get(list.size()  - 1);
  31.                 list.remove(list.size()  - 1);
  32.                 int mid = a2 / 2;
  33.                 int length=list.size();
  34.                 for (int j = length-1; j >= 0; j--) {
  35.                     if (list.get(j) <= mid) {
  36.                         list.remove(j);
  37.                         break;
  38.                     }
  39.                 }
  40.             }
  41.             ans += (a1 + a2);
  42.         }
  43.         out.println(ans);
  44.         out.flush();
  45.     }
  46. }

题目分析：

用队列的思想，不过我用的是ArrayList实现

  1. 首先用链表接收数据，对其进行排序，从大的开始买，才能让P/2尽可能大，然后才能让自己收益尽可能大
  2. 从最大的元素的开始遍历，取最大的两个元素A1、A2（A1>A2）计入总花费，然后把这两个元素出队，找队列中小于等于A2/2的最大元素，它可以白嫖，然后把它出队
  3. 找A2/2元素可以用二分优化，不过我当时神经有点紧绷，二分报错，所以直接从A2开始往后遍历了，复杂度会高一点

试题 H: 合并石子

【问题描述】

在桌面从左至右横向摆放着 N 堆石子。每一堆石子都有着相同的颜色，颜

色可能是颜色 0 ，颜色 1 或者颜色 2 中的其中一种。

现在要对石子进行合并，规定每次只能选择位置相邻并且颜色相同的两堆

石子进行合并。合并后新堆的相对位置保持不变，新堆的石子数目为所选择的

两堆石子数目之和，并且新堆石子的颜色也会发生循环式的变化。具体来说：

两堆颜色 0 的石子合并后的石子堆为颜色 1 ，两堆颜色 1 的石子合并后的石子

堆为颜色 2 ，两堆颜色 2 的石子合并后的石子堆为颜色 0 。本次合并的花费为所

选择的两堆石子的数目之和。

给出 N 堆石子以及他们的初始颜色，请问最少可以将它们合并为多少堆石

子？如果有多种答案，选择其中合并总花费最小的一种，合并总花费指的是在

所有的合并操作中产生的合并花费的总和。

【输入格式】

第一行一个正整数 N 表示石子堆数。

第二行包含 N 个用空格分隔的正整数，表示从左至右每一堆石子的数目。

第三行包含 N 个值为 0 或 1 或 2 的整数表示每堆石头的颜色。

【输出格式】

一行包含两个整数，用空格分隔。其中第一个整数表示合并后数目最少的

石头堆数，第二个整数表示对应的最小花费。

【样例输入】

5

5 10 1 8 6

1 1 0 2 2

试题 H: 合并石子

15 第十四届蓝桥杯大赛软件赛省赛 Java 大学 B 组

【样例输出】

2 44

【样例说明】

11c724aac9a547f7b2fc5bc5a65c342b.png

上图显示了两种不同的合并方式。其中节点中标明了每一堆的石子数目，

在方括号中标注了当前堆石子的颜色属性。左图的这种合并方式最终剩下了两

堆石子，所产生的合并总花费为 15 + 14 + 15 = 44 ；右图的这种合并方式最终

也剩下了两堆石子，但产生的合并总花费为 14 + 15 + 25 = 54 。综上所述，我

们选择合并花费为 44 的这种方式作为答案。

【评测用例规模与约定】

对于 30 % 的评测用例， 1 ≤ N ≤ 10 。

对于 50 % 的评测用例， 1 ≤ N ≤ 50 。

对于 100 % 的评测用例， 1 ≤ N ≤ 300 , 1 ≤ 每堆石子的数目 ≤ 1000 。

代码：

  1. import java.io.*;
  2. import java.util.ArrayList;
  3. import java.util.Collections;
  4. import java.util.LinkedList;
  5. import java.util.Queue;
  7. /**
  8.  * @author yx
  9.  * @date 2023-04-08 12:04
  10.  */
  11. public class H1 {
  12.     static class Node implements Comparable<Node>{
  13.         int count;
  14.         int color;
  16.         Node(int count, int color) {
  17.             this.count = count;
  18.             this.color = color;
  19.         }
  21.         @Override
  22.         public int compareTo(Node o) {
  23.             if(this.color==o.color){
  24.                 return this.count-o.count;
  25.             }else {
  26.                 return 0;
  27.             }
  28.         }
  29.     }
  31.     static PrintWriter out = new PrintWriter(System.out);
  32.     static BufferedReader ins = new BufferedReader(new InputStreamReader(System.in));
  33.     static StreamTokenizer in = new StreamTokenizer(ins);
  35.     public static void main(String[] args) throws IOException {
  36.         String s = ins.readLine();
  37.         int n = Integer.parseInt(s);
  38.         String[] strings1 = ins.readLine().split(" ");
  39.         String[] strings2 = ins.readLine().split(" ");
  40.         Node[] nodes = new Node[n];
  41.         int count = 0;
  42.         int color = 0;
  43.         long ans=0;
  44.         ArrayList<Node>list=new ArrayList<>();
  45.         for (int i = 0; i < n; i++) {
  46.             count = Integer.parseInt(strings1[i]);
  47.             color = Integer.parseInt(strings2[i]);
  48.             Node node = new Node(count, color);
  49.             list.add(node);
  50.         }
  51.         Collections.sort(list);
  52. //        for (int i = 0; i < n; i++) {
  53. //            System.out.println(list.get(i).count);
  54. //        }
  55. //        System.out.println(list.size());
  56.         int length=list.size();
  57.         for (int j = 0; j < length; j++) {
  58.             for (int i = 1; i < list.size(); i++) {
  59.                 if (list.get(i).color == list.get(i - 1).color) {
  60.                     Node node1 = list.get(i);
  61.                     Node node2 = list.get(i - 1);
  62.                     Node node3 = new Node(0, 0);
  63.                     if (node1.color == 0) {
  64.                         node3 = new Node(node1.count + node2.count, 1);
  65.                     } else if (node1.color == 1) {
  66.                         node3 = new Node(node1.count + node2.count, 2);
  67.                     } else {
  68.                         node3 = new Node(node1.count + node2.count, 0);
  69.                     }
  70.                     list.get(i-1).count = node3.count;
  71.                     list.get(i-1).color = node3.color;
  72.                     ans += node3.count;
  73.                     list.remove(i);
  74. //                    i--;
  75.                 }
  76.             }
  77.         }
  78.         out.println(list.size()+" "+ans);
  79.         out.flush();
  80.     }
  81. }

题目思路：

  1. 分堆问题，前两天刚做过，简单的分堆问题可以用优先队列，前天写的题解第四题合并果子但是很显然这题是加强版分堆问题，具体体现如下：

    • 只有同一类的堆才能合并
    • 堆合并之后会进化(堆号为0合并后—->堆号变为1……..)

蓝桥杯最后一战_小羊不会飞的博客-CSDN博客分巧克力_二分题目描述输入格式输出格式输入输出样例说明/提示代码：巧克力 - 优先队列题目描述输入格式输出格式输入输出样例说明/提示代码：思路分析：秘密行动_dp蓝桥杯算法提高-秘密行动题目描述输入格式输出格式样例输入样例输出代码：思路分析：合并果子_优先队列题目描述输入格式输出格式输入输出样例说明/提示代码：思路分析：回文平方数_进制转换API题目描述输入格式输出格式favicon32.icohttps://blog.csdn.net/m0\_55858611/article/details/129960460?spm=1001.2014.3001.5501

  1. 这题我用局部优先队列的思想，用ArrayList实现，自定义一个Node，然后重写排序，局部堆号相同的按堆数count递增排序（count小的先合，并保证count数大的堆重复合并次数最少）
  2. 从头节点开始往下遍历，判断下一个堆是否能合并，如果能合并，更新当前节点，删除下一个节点,ans+=当前节点的count+下一个节点的count
  3. 最后list的节点个数就是最小堆数

说在最后

趁着刚比完赛，思路还是比价清晰的，终于写完了题解，相比去年我感觉自己面对算法变得更加从容了一些(虽然还是算法小菜鸡)，这段时间因为要备战考研，所以每天也就只能在上课的时候练算法题，考研之余写写算法有时会放松心情有时会增加焦虑，不管怎样，这一个月都坚持下来了，接下来就是安心备战考研啦，可能会很长一段时间不更文，各位uu尽情谅解⏲️

最后希望正在看这篇文章的uu，蓝桥都能取得好成绩！！！

蓝桥杯，咱们有缘江湖再见呀！

09ce6822505246a4a43965a935da4660.png

发表评论

表情：
评论列表 （有 0 条评论，250人围观）

还没有评论，来说两句吧...

相关阅读

    相关 第十届蓝桥杯省赛

    这是个悲伤的故事 今天，第十届蓝桥杯比赛成绩公布了，我是第一次参加蓝桥杯（校内选拔不算），个人觉得，这次比赛的题目大都不难，甚至有部分真的太容易了， 　　但是我的成绩

    Dear 丶Dear 丶/ 0 赞/ 487 阅读