蓝桥杯最后一战

骑猪看日落 2023-09-27 17:11 7阅读 0赞

**目录**

分巧克力\_二分

题目描述

输入格式

输出格式

输入输出样例

说明/提示

代码：

巧克力 - 优先队列

题目描述

输入格式

输出格式

输入输出样例

说明/提示

代码：

思路分析：

秘密行动\_dp

蓝桥杯算法提高-秘密行动

题目描述

输入格式

输出格式

样例输入

样例输出

代码：

思路分析：

合并果子\_优先队列

题目描述

输入格式

输出格式

输入输出样例

说明/提示

代码：

思路分析：

回文平方数\_进制转换API

题目描述

输入格式

输出格式

输入输出样例

说明/提示

代码：

说在最后

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

## [分巧克力\_二分][Link 1] ##

> ### 题目描述 ###
> 
> 儿童节那天有 KK 位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。
> 
> 小明一共有 NN 块巧克力，其中第 ii 块是 Hi×WiHi×Wi 的方格组成的长方形。
> 
> 为了公平起见，小明需要从这 NN 块巧克力中切出 KK 块巧克力分给小朋友们。切出的巧克力需要满足：
> 
> 1.  形状是正方形，边长是整数。
> 2.  大小相同。
> 
> 例如一块 6×56×5 的巧克力可以切出 66 块 2×22×2 的巧克力或者 22 块 3×33×3 的巧克力。
> 
> 当然小朋友们都希望得到的巧克力尽可能大，你能帮小 HiHi 计算出最大的边长是多少么？
> 
> ### 输入格式 ###
> 
> 第一行包含两个整数 NN 和 KK。(1≤N,K≤105)(1≤N,K≤105)。
> 
> 以下 NN 行每行包含两个整数 HiHi 和 WiWi。(1≤Hi,Wi≤105)(1≤Hi,Wi≤105)。
> 
> 输入保证每位小朋友至少能获得一块 1×11×1 的巧克力。
> 
> ### 输出格式 ###
> 
> 输出切出的正方形巧克力最大可能的边长。
> 
> ### 输入输出样例 ###
> 
> **输入 \#1**
> 
>     2 10  
>     6 5  
>     5 6
> 
> **输出 \#1**
> 
>     2
> 
> ### 说明/提示 ###
> 
> 蓝桥杯 2022 省赛 A 组 I 题。

### 代码： ###

package 第十四届蓝桥杯三月真题刷题训练.自由刷题;
    
    import java.io.*;
    
    /**
     * @author yx
     * @date 2023-04-03 18:11
     */
    public class 分巧克力_二分 {
        static PrintWriter out = new PrintWriter(System.out);
        static BufferedReader ins = new BufferedReader(new InputStreamReader(System.in));
        static StreamTokenizer in = new StreamTokenizer(ins);
        static int[] H;
        static int[] W;
        static int K;
        static int N;
        /**
         * 输入
         * in.nextToken()
         * int a= (int)in.nval;
         * <p>
         * 输出
         * out.print();
         * out.flush();
         * <p>
         * 读文件：
         * BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("C:\\Users\\yx\\Desktop\\primes.txt")));
         * String s = br.readLine();s读取每一行数据
         * if (s == null)break;读取文件终止的语句
         **/
        public static void main(String[] args) throws IOException {
            String[] sp = ins.readLine().split(" ");
            N = Integer.parseInt(sp[0]);
            K = Integer.parseInt(sp[1]);
            H = new int[N];
            W = new int[N];
            for (int i = 0; i < N; i++) {
                String[] sp1 = ins.readLine().split(" ");
                H[i] = Integer.parseInt(sp1[0]);
                W[i] = Integer.parseInt(sp1[1]);
            }
            int l = 1;
            int r = 100001;
            int ans = 0;
            while (l <= r) {
                //二分
                int mid = (l + r) / 2;
                if (check(mid)) {
                    ans = mid;
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
            System.out.print(ans);
        }
    
        static boolean check(int n) {
            int temp=0;
            for (int i = 0; i < N; i++) {
                temp+=(H[i]/n)*(W[i]/n);
            }
            if(temp>=K){
                return true;
            }else {
                return false;
            }
        }
    }

![efbe163a0e63478d8e2f4dda7c6df270.png][]

## [巧克力 - 优先队列][-] ##

> ### 题目描述 ###
> 
> 小蓝很喜欢吃巧克力，他每天都要吃一块巧克力。
> 
> 一天小蓝到超市想买一些巧克力。超市的货架上有很多种巧克力，每种巧克力有自己的价格、数量和剩余的保质期天数，小蓝只吃没过保质期的巧克力，请问小蓝最少花多少钱能买到让自己吃 xx 天的巧克力。
> 
> ### 输入格式 ###
> 
> 输入的第一行包含两个整数 xx，nn，分别表示需要吃巧克力的天数和巧克力的种类数。
> 
> 接下来 nn 行描述货架上的巧克力，其中第 ii 行包含三个整数 aiai，bibi，cici，表示第 ii 种巧克力的单价为 aiai，保质期还剩 bibi 天（从现在开始的 bibi 天可以吃），数量为 cici。
> 
> ### 输出格式 ###
> 
> 输出一个整数表示小蓝的最小花费。如果不存在让小蓝吃 xx 天的购买方案，输出 −1−1。
> 
> ### 输入输出样例 ###
> 
> **输入 \#1**
> 
>     10 3
>     1 6 5
>     2 7 3
>     3 10 10
> 
> **输出 \#1**
> 
>     18
> 
> ### 说明/提示 ###
> 
> **【样例说明】**
> 
> 一种最佳的方案是第 11 种买 55 块，第 22 种买 22 块，第 33 种买 33 块。前 55 天吃第 11 种，第 66、77 天吃第 22 种，第 88 至 1010 天吃第 33 种。
> 
> **【评测用例规模与约定】**
> 
> 对于 30%30% 的评测用例，n,x≤1000n,x≤1000。
> 
> 对于所有评测用例，1≤n,x≤1051≤n,x≤105，1≤ai,bi,ci≤1091≤ai,bi,ci≤109。
> 
> 蓝桥杯 2021 国赛 C 组 I 题。

### 代码： ###

package 第十四届蓝桥杯三月真题刷题训练.自由刷题;
    
    import java.io.*;
    import java.util.*;
    
    /**
     * @author yx
     * @date 2023-04-03 18:28
     */
    public class 巧克力_优先队列 {
        static PrintWriter out = new PrintWriter(System.out);
        static BufferedReader ins = new BufferedReader(new InputStreamReader(System.in));
        static StreamTokenizer in = new StreamTokenizer(ins);
    
        /**
         * 输入
         * in.nextToken()
         * int a= (int)in.nval;
         * <p>
         * 输出
         * out.print();
         * out.flush();
         * <p>
         * 读文件：
         * BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("C:\\Users\\yx\\Desktop\\primes.txt")));
         * String s = br.readLine();s读取每一行数据
         * if (s == null)break;读取文件终止的语句
         **/
        static class Node implements Comparable<Node> {
            int id;
            int price_a;
            int day_b;
            int number_c;
    
            Node(int id, int price_a, int day_b, int number_c) {
                this.id = id;
                this.price_a = price_a;
                this.day_b = day_b;
                this.number_c = number_c;
            }
    
            //按保质期从高到低进行排序
            @Override
            public int compareTo(Node o) {
                if (o.day_b > this.day_b) {
                    return 1;
                } else {
                    return -1;
                }
            }
        }
        static class Node1  {
            int id;
            int price_a;
            int day_b;
            int number_c;
    
            Node1(int id, int price_a, int day_b, int number_c) {
                this.id = id;
                this.price_a = price_a;
                this.day_b = day_b;
                this.number_c = number_c;
            }
        }
    
        public static void main(String[] args) throws IOException {
            String[] sp = ins.readLine().split(" ");
            int x = Integer.parseInt(sp[0]);
            int n = Integer.parseInt(sp[1]);
            Node[] nodes = new Node[n];
            int[] nums = new int[n];
            long ans = 0;
            for (int i = 0; i < n; i++) {
                String[] sp1 = ins.readLine().split(" ");
                nodes[i] = new Node(i, Integer.parseInt(sp1[0]), Integer.parseInt(sp1[1]), Integer.parseInt(sp1[2]));
            }
            //按保质期从高到低进行排序
            Arrays.sort(nodes);
            int j = 0;
    //        Prio<Node1> priority_queue = new LinkedList<>();
            PriorityQueue<Node1>priority_queue=new PriorityQueue<>(
                    new Comparator<Node1>() {
                        @Override
                        public int compare(Node1 o1, Node1 o2) {
                            return o1.price_a-o2.price_a;
                        }
                    }
            );
            for (int i = x; i >= 1; i--) {
                while (j < n && nodes[j].day_b >= i) {
                    priority_queue.offer(new Node1(nodes[j].id,nodes[j].price_a,nodes[j].day_b,nodes[j].number_c));
                    j++;
                }
                //如果出现空队列表示没有选择了
                if (priority_queue.size() == 0) {
                    out.println(ans);
                    out.println(-1);
                    out.flush();
                    return;
                }
                Node1 node = priority_queue.peek();
                //表示当前id的物品个数+1
                nums[node.id]++;
    //            System.out.println("id："+node.id+"价格："+node.price_a+"购买数量："+nums[node.id]);
                //加上当前物品的价格
                ans += node.price_a;
                //表示当前物品全部选完了
                if (node.number_c == nums[node.id]) {
    //                System.out.println("物品id:"+node.id+"出队");
                    //当前种类的物品已经全部选完了，所以当前物品出队
                    priority_queue.poll();
                }
            }
            out.println(ans);
            out.flush();
        }
    }

![21b83aca8d284c04a4dd19a69c8bb17c.png][]

### 思路分析： ###

## [秘密行动\_dp][dp] ##

> 题目 2250:
> 
> ## 蓝桥杯算法提高-秘密行动 ##
> 
> 时间限制: 1s 内存限制: 128MB 提交: 255 解决: 122
> 
> ### 题目描述 ###
> 
> 小D接到一项任务，要求他爬到一座n层大厦的顶端与神秘人物会面。这座大厦有一个神奇的特点，每层的高度都不一样，同时，小D也拥有一项特殊能力，可以一次向上跳跃一层或两层，但是这项能力无法连续使用。已知向上1高度消耗的时间为1，跳跃不消耗时间。由于事态紧急，小D想知道他最少需要多少时间到达顶层。
> 
> ### 输入格式 ###
> 
> 第一行包含一个整数n，代表楼的高度。  
> 接下来n行每行一个整数ai，代表i层的楼层高度（ai <= 100）。
> 
> ### 输出格式 ###
> 
> 输出1行，包含一个整数，表示所需的最短时间。
> 
> ### 样例输入 ###
> 
>     5
>     3
>     5
>     1
>     8
>     4
> 
> ### 样例输出 ###
> 
>     1

### 代码： ###

package 第十四届蓝桥杯三月真题刷题训练.自由刷题;
    
    import java.io.*;
    
    /**
     * @author yx
     * @date 2023-04-04 16:56
     */
    public class 秘密行动_dp {
        static PrintWriter out =new PrintWriter(System.out);
        static BufferedReader ins=new BufferedReader(new InputStreamReader(System.in));
        static StreamTokenizer in=new StreamTokenizer(ins);
        /**
         * 输入
         * in.nextToken()
         * int a= (int)in.nval;
         *
         * 输出
         * out.print();
         * out.flush();
         *
         * 读文件：
         * BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("C:\\Users\\yx\\Desktop\\primes.txt")));
         * String s = br.readLine();s读取每一行数据
         * if (s == null)break;读取文件终止的语句
         **/
        public static void main(String[] args) throws IOException {
            in.nextToken();
            int n=(int) in.nval;
            int[] nums=new int[n+1];
            for (int i = 1; i <= n; i++) {
                in.nextToken();
                nums[i]=(int) in.nval;
            }
            //n表示需要走n层
            //2表示两种下选择可以一步一步爬也可以直接跳跃
            //其中下标[][0]表示爬,[][1]表示跳跃
            int[][] dp=new int[n+1][2];
            dp[1][0]=nums[1];//直接赋初值
            for (int i = 2; i <= n; i++) {
                //从上一层爬上来,上一层可以是爬的也可以是跳跃的
                dp[i][0]=Math.min(dp[i-1][0],dp[i-1][1])+nums[i];
                //直接跳跃，但是只能从爬的开始跳跃,并且每次可以跳两层或者一层，因为不能连续跳跃
                dp[i][1]=Math.min(dp[i-1][0],dp[i-2][0]);
            }
            out.println(Math.min(dp[n][1],dp[n][0]));
            out.flush();
        }
    }

### 思路分析： ###

## [合并果子\_优先队列][Link 2] ##

> ### 题目描述 ###
> 
> 在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。
> 
> 每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过 n−1n−1 次合并之后， 就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。
> 
> 因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为 11 ，并且已知果子的种类 数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。
> 
> 例如有 33 种果子，数目依次为 11 ， 22 ， 99 。可以先将 11 、 22 堆合并，新堆数目为 33 ，耗费体力为 33 。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为 1212 ，耗费体力为 1212 。所以多多总共耗费体力 =3+12=15=3+12=15 。可以证明 1515 为最小的体力耗费值。
> 
> ### 输入格式 ###
> 
> 共两行。  
> 第一行是一个整数 n(1≤n≤10000)n(1≤n≤10000) ，表示果子的种类数。
> 
> 第二行包含 nn 个整数，用空格分隔，第 ii 个整数 ai(1≤ai≤20000)ai(1≤ai≤20000) 是第 ii 种果子的数目。
> 
> ### 输出格式 ###
> 
> 一个整数，也就是最小的体力耗费值。输入数据保证这个值小于 231231 。
> 
> ### 输入输出样例 ###
> 
> **输入 \#1**
> 
>     3 
>     1 2 9
> 
> **输出 \#1**
> 
>     15
> 
> ### 说明/提示 ###
> 
> 对于 30%30% 的数据，保证有 n≤1000n≤1000：
> 
> 对于 50%50% 的数据，保证有 n≤5000n≤5000；
> 
> 对于全部的数据，保证有 n≤10000n≤10000。

### 代码： ###

package 第十四届蓝桥杯三月真题刷题训练.自由刷题;
    
    import java.io.*;
    import java.util.PriorityQueue;
    
    /**
     * @author yx
     * @date 2023-04-04 17:59
     */
    public class 合并果子_优先队列 {
        static PrintWriter out =new PrintWriter(System.out);
        static BufferedReader ins=new BufferedReader(new InputStreamReader(System.in));
        static StreamTokenizer in=new StreamTokenizer(ins);
        /**
         * 输入
         * in.nextToken()
         * int a= (int)in.nval;
         *
         * 输出
         * out.print();
         * out.flush();
         *
         * 读文件：
         * BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("C:\\Users\\yx\\Desktop\\primes.txt")));
         * String s = br.readLine();s读取每一行数据
         * if (s == null)break;读取文件终止的语句
         **/
        public static void main(String[] args) throws IOException {
            in.nextToken();
            int n=(int) in.nval;
            //优先队列会自动排序
            PriorityQueue<Integer>queue=new PriorityQueue<>();
            for (int i = 0; i < n; i++) {
                in.nextToken();
                queue.offer((int)in.nval);
            }
            int a=0;
            int b=0;
            int ans=0;
            while (queue.size()!=1){
                if(!queue.isEmpty()){
                    a=queue.poll();
                }
                if(!queue.isEmpty()){
                    b=queue.poll();
                }
                queue.offer(a+b);
                ans+=(a+b);
            }
            out.println(ans);
            out.flush();
        }
    }

![9b1374ce09564da0af7aa08dfef9ffa6.png][]

### 思路分析： ###

## [回文平方数\_进制转换API][API] ##

> ### 题目描述 ###
> 
> 回文数是指从左向右念和从右向左念都一样的数。如 1232112321 就是一个典型的回文数。
> 
> 给定一个用十进制表示的正整数 BB，输出所有 \[1,300\]\[1,300\] 中，它的平方用 BB 进制表示时是回文数的数。
> 
> ### 输入格式 ###
> 
> 共一行，一个单独的正整数 BB。
> 
> ### 输出格式 ###
> 
> 每行两个 BB 进制的符合要求的数字，第二个数是第一个数的平方，且第二个数是回文数。
> 
> 注意大于 99 的数，用字母表示。如用 `A` 表示 1010，`B` 表示 1111，用第 nn 个大写字母表示 n+9n+9。
> 
> ### 输入输出样例 ###
> 
> **输入 \#1**
> 
>     10
> 
> **输出 \#1**
> 
>     1 1
>     2 4
>     3 9
>     11 121
>     22 484
>     26 676
>     101 10201
>     111 12321
>     121 14641
>     202 40804
>     212 44944
>     264 69696
> 
> ### 说明/提示 ###
> 
> 【数据范围】  
> 对于 100%100% 的数据，2≤B≤202≤B≤20
> 
> 题目翻译来自NOCOW。
> 
> USACO Training Section 1.2

### 代码： ###

package 第十四届蓝桥杯三月真题刷题训练.自由刷题;
    
    import java.io.*;
    import java.util.Locale;
    
    /**
     * @author yx
     * @date 2023-04-04 16:33
     */
    public class P1206回文平方数 {
        static PrintWriter out =new PrintWriter(System.out);
        static BufferedReader ins=new BufferedReader(new InputStreamReader(System.in));
        static StreamTokenizer in=new StreamTokenizer(ins);
        /**
         * 输入
         * in.nextToken()
         * int a= (int)in.nval;
         *
         * 输出
         * out.print();
         * out.flush();
         *
         * 读文件：
         * BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("C:\\Users\\yx\\Desktop\\primes.txt")));
         * String s = br.readLine();s读取每一行数据
         * if (s == null)break;读取文件终止的语句
         **/
        public static void main(String[] args) throws IOException {
            //           1、把十进制A+B的结果转换为D进制
            //            Integer.toString(A+B,D)
            //           2、把D进制的字符串”s“转成十进制
            //            Integer.parseInt("s",D)
            //            int anInt1 = Integer.parseInt("1000100", 2);//68
            in.nextToken();
            int number=(int) in.nval;
            for (int i = 1; i <= 300; i++) {
                if(isHuiWen(Integer.toString(i*i,number))){
                    out.println(Integer.toString(i,number).toUpperCase()+" "+Integer.toString(i*i,number).toUpperCase(Locale.ROOT));
                }
            }
            out.flush();
        }
        static boolean isHuiWen(String s){
            char[] arr=s.toCharArray();
            int length=arr.length;
            for (int i = 0; i < length/2; i++) {
                if(arr[i]!=arr[length-i-1]){
                    return false;
                }
            }
            return true;
        }
    }

![3dda9e5034c042db9c5d0cb8682bb796.png][]

## 说在最后 ##

**祝大家都能取得好成绩！！！**

**也希望自己能取得一个满意的成绩！！！**

![75491fa8ac1c453f9303147690486fe4.png][]

[Link 1]: https://www.luogu.com.cn/problem/P8647
[efbe163a0e63478d8e2f4dda7c6df270.png]: https://img-blog.csdnimg.cn/efbe163a0e63478d8e2f4dda7c6df270.png
[-]: https://www.luogu.com.cn/problem/P8769
[21b83aca8d284c04a4dd19a69c8bb17c.png]: https://img-blog.csdnimg.cn/21b83aca8d284c04a4dd19a69c8bb17c.png
[dp]: https://www.dotcpp.com/oj/problem2250.html
[Link 2]: https://www.luogu.com.cn/problem/P1090
[9b1374ce09564da0af7aa08dfef9ffa6.png]: https://img-blog.csdnimg.cn/9b1374ce09564da0af7aa08dfef9ffa6.png
[API]: https://www.luogu.com.cn/problem/P1206
[3dda9e5034c042db9c5d0cb8682bb796.png]: https://img-blog.csdnimg.cn/3dda9e5034c042db9c5d0cb8682bb796.png
[75491fa8ac1c453f9303147690486fe4.png]: https://img-blog.csdnimg.cn/75491fa8ac1c453f9303147690486fe4.png