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

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

**目录**

说在前面

试题 A: 阶乘求和

代码：

题目分析：

试题 B: 幸运数字

代码：

题目分析：

试题 D: 矩形总面积

代码：

题目分析：

试题 G: 买二赠一

代码：

题目分析：

试题 H: 合并石子

代码：

题目思路：

说在最后

--------------------

## 说在前面 ##

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

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

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

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

## 试题 **A:** 阶乘求和 ##

> 【问题描述】 
> 
> 令  *S*  = 1! + 2! + 3! +  ...  \+ 202320232023! ，求  *S*  的末尾  9  位数字。 
> 
> 提示：答案首位不为  0 。 
> 
> 【答案提交】 
> 
> 这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一 
> 
> 个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

#### 代码： ####

/**
     * @author yx
     * @date 2023-04-08 9:11
     */
    public class t1 {
        public static void main(String[] args) {
    //        420940313
            long ans=0;
            long temp=1000000000;
            long temp1=1;
            for (long i = 1; i <= 202320232023L ; i++) {
                temp1=((temp1%temp)*(i%temp))%temp;
                ans=(ans%temp+temp1%temp)%temp;
                System.out.println("temp1是："+temp1+"  ans是："+ans+"   i是："+i);
            }
    //        System.out.println("答案是："+ans);
        }
    }

#### 题目分析： ####

> **答案是：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  个幸运数 
> 
> 字是多少？你只需要告诉小蓝这个整数的十进制表示即可。 
> 
> 【答案提交】 
> 
> 这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一 
> 
> 个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

#### 代码： ####

import java.awt.*;
    
    /**
     * @author yx
     * @date 2023-04-08 9:13
     */
    public class t2 {
        public static void main(String[] args) {
            int ans=0;
            int i=0;
            while (true){
                i++;
                if(isCheck(i)){
                    ans++;
                    System.out.println(i+"为第"+ans+"个");
                }
                if(ans==2023){
                    break;
                }
            }
            System.out.println("答案是："+i);
        }
        static boolean isCheck(int n){
            String temp1=Integer.toString(n,2);
            String temp2=Integer.toString(n,8);
            String temp3=n+"";
            String temp4=Integer.toString(n,16);
            int temp_1=0;
            int temp_2=0;
            int temp_3=0;
            int temp_4=0;
            for (int i = 0; i < temp1.length(); i++) {
                temp_1+=Integer.parseInt(temp1.substring(i,i+1));
            }
            if(n%temp_1!=0){
                return false;
            }
            for (int i = 0; i < temp2.length() ;i++) {
                temp_2+=Integer.parseInt(temp2.substring(i,i+1));
            }
            if(n%temp_2!=0){
                return false;
            }
            for (int i = 0; i < temp3.length(); i++) {
                temp_3+=Integer.parseInt(temp3.substring(i,i+1));
            }
            if(n%temp_3!=0){
                return false;
            }
            for (int i = 0; i < temp4.length(); i++) {
                if((temp4.substring(i,i+1)).toCharArray()[0]>='a'){
                    temp_4 += (temp4.substring(i,i+1)).toCharArray()[0]-'a'+10;
                }else {
                    temp_4 += Integer.parseInt(temp4.substring(i, i + 1));
                }
            }
            if(n%temp_4!=0){
                return false;
            }
            return true;
        }
    }

#### 题目分析： ####

> **答案是：215040**
> 
> 1.  直接把数先进制转换，然后求数位和，判读能否整除数位和就好了
> 2.  这题本质考一个进制转换，如果会用Java的API就很简单,前两天我在算法组会分享的时候刚好讲过，还写了题解，还上了热榜，哈哈哈，下面链接的第五题
> 
> [蓝桥杯最后一战\_小羊不会飞的博客-CSDN博客分巧克力\_二分题目描述输入格式输出格式输入输出样例说明/提示代码：巧克力 - 优先队列题目描述输入格式输出格式输入输出样例说明/提示代码：思路分析：秘密行动\_dp蓝桥杯算法提高-秘密行动题目描述输入格式输出格式样例输入样例输出代码：思路分析：合并果子\_优先队列题目描述输入格式输出格式输入输出样例说明/提示代码：思路分析：回文平方数\_进制转换API题目描述输入格式输出格式![favicon32.ico][]https://blog.csdn.net/m0\_55858611/article/details/129960460?spm=1001.2014.3001.5501][-CSDN_ - _dp_-_API_favicon32.ico_https_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  \] 。

#### 代码： ####

import java.io.*;
    
    /**
     * @author yx
     * @date 2023-04-08 13:57
     */
    public class D {
        static PrintWriter out =new PrintWriter(System.out);
        static BufferedReader ins=new BufferedReader(new InputStreamReader(System.in));
        static StreamTokenizer in=new StreamTokenizer(ins);
        public static void main(String[] args) throws IOException {
            String[] sp=ins.readLine().split(" ");
            int x1=Integer.parseInt(sp[0]);
            int y1=Integer.parseInt(sp[1]);
            int x2=Integer.parseInt(sp[2]);
            int y2=Integer.parseInt(sp[3]);
            int x3=Integer.parseInt(sp[4]);
            int y3=Integer.parseInt(sp[5]);
            int x4=Integer.parseInt(sp[6]);
            int y4=Integer.parseInt(sp[7]);
            long ans=0;
            int max_X=Math.max(Math.max(x1,x2),Math.max(x3,x4));
            int max_Y=Math.max(Math.max(y1,y2),Math.max(y3,y4));
            int max=Math.max(max_X,max_Y);
            int[][] Map=new int[max+1][max+1];
            for (int i = y1; i <= y2-1 ; i++) {
                for (int j = x1; j <= x2-1 ; j++) {
                    Map[i][j]+=1;
                }
            }
            for (int i = y3; i <= y4-1 ; i++) {
                for (int j = x3; j <= x4-1 ; j++) {
                    Map[i][j]+=1;
                }
            }
            for (int i = 0; i <= max_X ; i++) {
                for (int j = 0; j <= max_Y ; j++) {
    //                System.out.print(Map[j][i]+" ");
                    if(Map[j][i]>=1){
                        ans++;
                    }
                }
    //            System.out.println();
            }
            System.out.println(ans);
        }
    }

#### 题目分析： ####

> 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 。

#### 代码： ####

import java.io.*;
    import java.util.ArrayList;
    import java.util.Collections;
    
    /**
     * @author yx
     * @date 2023-04-08 11:31
     */
    public class G3 {
        static PrintWriter out = new PrintWriter(System.out);
        static BufferedReader ins = new BufferedReader(new InputStreamReader(System.in));
        static StreamTokenizer in = new StreamTokenizer(ins);
    
        public static void main(String[] args) throws IOException {
            String s = ins.readLine();
            int N = Integer.parseInt(s);
            String[] sp = ins.readLine().split(" ");
            ArrayList<Integer> list = new ArrayList<>();
            long ans = 0;
            for (int i = 0; i < N; i++) {
                list.add(Integer.parseInt(sp[i]));
            }
            Collections.sort(list);
            for (int i = 0; list.size()>0 ; i++) {
                int a1 = 0;
                int a2 = 0;
                a1 = list.get(list.size()  - 1);
                list.remove(list.size()  - 1);
                if(list.size() - 1>=0) {
                    a2 = list.get(list.size()  - 1);
                    list.remove(list.size()  - 1);
                    int mid = a2 / 2;
                    int length=list.size();
                    for (int j = length-1; j >= 0; j--) {
                        if (list.get(j) <= mid) {
                            list.remove(j);
                            break;
                        }
                    }
                }
                ans += (a1 + a2);
            }
            out.println(ans);
            out.flush();
        }
    }

#### 题目分析： ####

> **用队列的思想，不过我用的是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 。

#### 代码： ####

import java.io.*;
    import java.util.ArrayList;
    import java.util.Collections;
    import java.util.LinkedList;
    import java.util.Queue;
    
    /**
     * @author yx
     * @date 2023-04-08 12:04
     */
    public class H1 {
        static class Node implements Comparable<Node>{
            int count;
            int color;
    
            Node(int count, int color) {
                this.count = count;
                this.color = color;
            }
    
            @Override
            public int compareTo(Node o) {
                if(this.color==o.color){
                    return this.count-o.count;
                }else {
                    return 0;
                }
            }
        }
    
        static PrintWriter out = new PrintWriter(System.out);
        static BufferedReader ins = new BufferedReader(new InputStreamReader(System.in));
        static StreamTokenizer in = new StreamTokenizer(ins);
    
        public static void main(String[] args) throws IOException {
            String s = ins.readLine();
            int n = Integer.parseInt(s);
            String[] strings1 = ins.readLine().split(" ");
            String[] strings2 = ins.readLine().split(" ");
            Node[] nodes = new Node[n];
            int count = 0;
            int color = 0;
            long ans=0;
            ArrayList<Node>list=new ArrayList<>();
            for (int i = 0; i < n; i++) {
                count = Integer.parseInt(strings1[i]);
                color = Integer.parseInt(strings2[i]);
                Node node = new Node(count, color);
                list.add(node);
            }
            Collections.sort(list);
    //        for (int i = 0; i < n; i++) {
    //            System.out.println(list.get(i).count);
    //        }
    //        System.out.println(list.size());
            int length=list.size();
            for (int j = 0; j < length; j++) {
                for (int i = 1; i < list.size(); i++) {
                    if (list.get(i).color == list.get(i - 1).color) {
                        Node node1 = list.get(i);
                        Node node2 = list.get(i - 1);
                        Node node3 = new Node(0, 0);
                        if (node1.color == 0) {
                            node3 = new Node(node1.count + node2.count, 1);
                        } else if (node1.color == 1) {
                            node3 = new Node(node1.count + node2.count, 2);
                        } else {
                            node3 = new Node(node1.count + node2.count, 0);
                        }
                        list.get(i-1).count = node3.count;
                        list.get(i-1).color = node3.color;
                        ans += node3.count;
                        list.remove(i);
    //                    i--;
                    }
                }
            }
            out.println(list.size()+" "+ans);
            out.flush();
        }
    }

#### 题目思路： ####

> 1.  分堆问题，前两天刚做过，简单的分堆问题可以用优先队列，前天写的题解第四题合并果子但是很显然这题是加强版分堆问题，**具体体现如下：**
> 
>  *  只有同一类的堆才能合并
>  *  堆合并之后会进化(堆号为0合并后--->堆号变为1........)
> 
> [蓝桥杯最后一战\_小羊不会飞的博客-CSDN博客分巧克力\_二分题目描述输入格式输出格式输入输出样例说明/提示代码：巧克力 - 优先队列题目描述输入格式输出格式输入输出样例说明/提示代码：思路分析：秘密行动\_dp蓝桥杯算法提高-秘密行动题目描述输入格式输出格式样例输入样例输出代码：思路分析：合并果子\_优先队列题目描述输入格式输出格式输入输出样例说明/提示代码：思路分析：回文平方数\_进制转换API题目描述输入格式输出格式![favicon32.ico][]https://blog.csdn.net/m0\_55858611/article/details/129960460?spm=1001.2014.3001.5501][-CSDN_ - _dp_-_API_favicon32.ico_https_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][]

[23_30]: https://blog.csdn.net/m0_55858611/category_12231255.html?spm=1001.2014.3001.5482
[39d024b0d8ad4e7894b26d6125545a4c.png]: https://img-blog.csdnimg.cn/39d024b0d8ad4e7894b26d6125545a4c.png
[favicon32.ico]: https://g.csdnimg.cn/static/logo/favicon32.ico
[-CSDN_ - _dp_-_API_favicon32.ico_https_blog.csdn.net_m0_55858611_article_details_129960460_spm_1001.2014.3001.5501]: https://blog.csdn.net/m0_55858611/article/details/129960460?spm=1001.2014.3001.5501
[6d71c2f9a683481e879f3f96fd27881e.png]: https://img-blog.csdnimg.cn/6d71c2f9a683481e879f3f96fd27881e.png
[f88948b32c65454487325c1679df9086.png]: https://img-blog.csdnimg.cn/f88948b32c65454487325c1679df9086.png
[7772d601b1a84e5b8ab0323de8334494.png]: https://img-blog.csdnimg.cn/7772d601b1a84e5b8ab0323de8334494.png
[11c724aac9a547f7b2fc5bc5a65c342b.png]: https://img-blog.csdnimg.cn/11c724aac9a547f7b2fc5bc5a65c342b.png
[09ce6822505246a4a43965a935da4660.png]: https://img-blog.csdnimg.cn/09ce6822505246a4a43965a935da4660.png