蓝桥杯最后一战

目录

分巧克力_二分

题目描述

输入格式

输出格式

输入输出样例

说明/提示

代码:

巧克力 - 优先队列

题目描述

输入格式

输出格式

输入输出样例

说明/提示

代码:

思路分析:

秘密行动_dp

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

题目描述

输入格式

输出格式

样例输入

样例输出

代码:

思路分析:

合并果子_优先队列

题目描述

输入格式

输出格式

输入输出样例

说明/提示

代码:

思路分析:

回文平方数_进制转换API

题目描述

输入格式

输出格式

输入输出样例

说明/提示

代码:

说在最后


分巧克力_二分

题目描述

儿童节那天有 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;
        }
    }
}

巧克力 - 优先队列

题目描述

小蓝很喜欢吃巧克力,他每天都要吃一块巧克力。

一天小蓝到超市想买一些巧克力。超市的货架上有很多种巧克力,每种巧克力有自己的价格、数量和剩余的保质期天数,小蓝只吃没过保质期的巧克力,请问小蓝最少花多少钱能买到让自己吃 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();
    }
}

思路分析:

秘密行动_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();
    }
}

思路分析:

合并果子_优先队列

题目描述

在一个果园里,多多已经将所有的果子打了下来,而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。

每一次合并,多多可以把两堆果子合并到一起,消耗的体力等于两堆果子的重量之和。可以看出,所有的果子经过 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();
    }
}

思路分析:

回文平方数_进制转换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;
    }
}

说在最后

祝大家都能取得好成绩!!!

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

 

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
分享
二维码
< <上一篇

)">
下一篇>>