第十四届蓝桥杯三月真题刷题训练——第 12 天

喜欢ヅ旅行 2023-09-27 15:58 53阅读 0赞

**目录**

第 1 题：0的个数

问题描述

输入格式

输出格式

评测用例规模与约定

运行限制

代码：

第 2 题：超级质数

问题描述

答案提交

运行限制

代码：

分析：

第 3 题：卡牌\_二分\_快读

问题描述

输入格式

输出格式

样例输入

样例输出

样例说明

评测用例规模与约定

运行限制

代码：

分析：

第 4 题：染色时间

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

## 第 1 题：[0的个数][0] ##

> #### 问题描述 ####
> 
> 给定一个正整数 n ，请问 n 的十进制表示中末尾总共有几个 0 ？
> 
> #### 输入格式 ####
> 
> 输入一行包含一个正整数 nn。
> 
> #### 输出格式 ####
> 
> 输出一个整数，表示答案。
> 
> 样例输入
> 
>     20220000
> 
> 样例输出
> 
>     4
> 
> #### 评测用例规模与约定 ####
> 
> 对于所有评测用例，1 <= n <= 1000000000。
> 
> #### 运行限制 ####
> 
>  *  最大运行时间：1s
>  *  最大运行内存: 256M

### 代码： ###

package 第十四届蓝桥杯三月真题刷题训练.day12;
    
    import java.io.*;
    
    /**
     * @author yx
     * @date 2023-03-15 8:19
     */
    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();
         */
        public static void main(String[] args) throws IOException {
            in.nextToken();
            int n=(int) in.nval;
            int temp=0;
            int ans=0;
            while (true){
                temp=n%10;
                if(temp!=0){
                    break;
                }else {
                    ans++;
                }
                n/=10;
            }
            out.println(ans);
            out.flush();
        }
    }

![cd96e368cebc491090356fe5f8e8caa4.png][]

## 第 2 题：[超级质数][Link 1] ##

> #### 问题描述 ####
> 
> 如果一个质数 P 的每位数字都是质数, 而且每两个相邻的数字组成的两位 数是质数, 而且每三位相邻的数字组成的三位数是质数, 依次类推, 如果每相 邻的 k 位数字组成的 k 位数都是质数, 则 P 称为超级质数。
> 
> 如果把超级质数 P 看成一个字符串, 则这个超级质数的每个子串都是质 数。
> 
> 例如, 53 是一个超级质数。
> 
> 请问, 最大的超级质数是多少?
> 
> #### 答案提交 ####
> 
> 这是一道结果填空的题, 你只需要算出结果后提交即可。本题的结果为一 个整数, 在提交答案时只填写这个整数, 填写多余的内容将无法得分。
> 
> #### 运行限制 ####
> 
>  *  最大运行时间：1s
>  *  最大运行内存: 256M

### 代码： ###

package 第十四届蓝桥杯三月真题刷题训练.day12;
    
    import java.io.BufferedReader;
    import java.io.InputStreamReader;
    import java.io.PrintWriter;
    import java.io.StreamTokenizer;
    
    /**
     * @author yx
     * @date 2023-03-15 15:10
     */
    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();
         */
        public static void main(String[] args) {
            for (int i = 1000000; i>=2 ; i--) {
                if(isCheck(i)){
                    System.out.println(i);
                    return;
                }
            }
        }
    
        static boolean isCheck(int n){
            String s=n+"";
            int length=s.length();
            for (int i = 0; i < length ; i++) {
                for (int j = i+1; j <= length ; j++) {
                    int temp=Integer.parseInt(s.substring(i,j));
                    if(!isPrime(temp)){//如果不是质数就返回false
                        return false;
                    }
                }
            }
            return true;
        }
        static boolean isPrime(int n){
            if(n==1)return false;
            for (int i = 2; i <= Math.sqrt(n) ; i++) {
                if(n%i==0){
                    return false;
                }
            }
            return true;
        }
    }

![ce97922dc278432994ebb0e0040092b7.png][]

### 分析： ###

> **思路：**
> 
> **1、质数判断**
> 
> **2、数值切割**

## 第 3 题：[卡牌\_二分\_快读][Link 2] ##

> #### 问题描述 ####
> 
> 这天, 小明在整理他的卡牌。
> 
> 他一共有 n 种卡牌, 第 i 种卡牌上印有正整数数 i(i∈\[1,n\]), 且第 i 种卡牌 现有 ai 张。
> 
> 而如果有 n 张卡牌, 其中每种卡牌各一张, 那么这 nn 张卡牌可以被称为一 套牌。小明为了凑出尽可能多套牌, 拿出了 m 张空白牌, 他可以在上面写上数 i, 将其当做第 i 种牌来凑出套牌。然而小明觉得手写的牌不太美观, 决定第 ii 种牌最多手写 bi 张。
> 
> 请问小明最多能凑出多少套牌?
> 
> #### 输入格式 ####
> 
> 输入共 3 行, 第一行为两个正整数 n,m。
> 
> 第二行为 n 个正整数 a1,a2,…,an。
> 
> 第三行为 n 个正整数 b1,b2,…,bn 。
> 
> #### 输出格式 ####
> 
> 一行, 一个整数表示答案。
> 
> #### 样例输入 ####
> 
>     4 5
>     1 2 3 4
>     5 5 5 5
> 
> #### 样例输出 ####
> 
>     3
> 
> #### 样例说明 ####
> 
> 这 5 张空白牌中, 拿 2 张写 1 , 拿 1 张写 2 , 这样每种牌的牌数就变为了 3,3,3,4, 可以凑出 3 套牌, 剩下 2 张空白牌不能再帮助小明凑出一套。
> 
> #### 评测用例规模与约定 ####
> 
> 对于 30%的数据, 保证 n≤2000;
> 
> 对于 100% 的数据, 保证 n≤2×10^5;ai,bi≤2\*n;m≤n^2 。
> 
> #### 运行限制 ####
> 
>  *  最大运行时间：1s
>  *  最大运行内存: 512M

### 代码： ###

package 第十四届蓝桥杯三月真题刷题训练.day12;
    
    import java.io.*;
    import java.util.Scanner;
    
    /**
     * @author yx
     * @date 2023-03-15 16:45
     */
    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();
         */
        static int[]a;
        static int[]b;
        static int n;
        static long m;
        public static void main(String[] args) throws IOException {
            String[] s=ins.readLine().split(" ");
            n=Integer.parseInt(s[0]);
            m=Long.parseLong(s[1]);
            a=new int[n];
            b=new int[n];
            String[] s2=ins.readLine().split(" ");
            for (int i = 0; i < n; i++) {
                a[i]=Integer.parseInt(s2[i]);
            }
            String[] s3=ins.readLine().split(" ");
            for (int i = 0; i < n; i++) {
                b[i]=Integer.parseInt(s3[i]);
            }
            int l=0;
            int r=2*n;
            int ans=0;
            while (l<=r){
                int mid=(l+r)/2;
                if(check(mid)){
                    ans=mid;
                    l=mid+1;
                }else {
                    r=mid-1;
                }
            }
            out.println(ans);
            out.flush();
        }
        static boolean check(int t){
            long temp=m;//记录空白卡牌
            for (int i = 0; i < n; i++) {
                if(a[i]>=t)continue;
                if(b[i]+a[i]<t)return false;
                if(temp+a[i]<t)return false;
                if(t-a[i]<=temp){
                    temp-=(t-a[i]);
                }else{
                    return false;
                }
            }
            return true;
        }
    }

### ![5da835ab6ad1457f8dd5bcdcbbd5daeb.png][]分析： ###

> **这道题目非常综合，考察了二分以及Java的IO流输入输出**，下面是我总结的一些要点！
> 
> **（1）这道题目是通过二分的手段来找到最多的能凑到的牌的套数**
> 
> 我自己的一套二分模板（经供参考）：
> 
>     while (l<=r){
>                 int mid=(l+r)/2;
>                 if(check(mid)){
>                     ans=mid;
>                     l=mid+1;
>                 }else {
>                     r=mid-1;
>                 }
>             }
> 
> **二分的难点有两个：**
> 
> 1.  二分边界，即L和R的退出条件
> 2.  check函数的函数体实现
> 
> **（2）这道题目充分的体现了Java的不足，普通的Scanner输入只能拿到30%的分数，这道题目要想拿满分必须要使用Java的I/O流输入**
> 
> 下面是我的题解代码中每次都会出现的IO流模板：
> 
>     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();
>          */
> 
> **（3）在做这道题目的时候，我发现Scanner和BufferReader不能同时使用，会出现输入异常，这个点希望大家在做题的时候注意一下！！**

## 第 4 题：[染色时间][Link 3] ##

> **拍了一天戏，脑袋晕晕的，下次补！**

[0]: https://www.lanqiao.cn/problems/2293/learning/?page=33&first_category_id=1&sort=students_count&difficulty=30&second_category_id=3
[cd96e368cebc491090356fe5f8e8caa4.png]: https://img-blog.csdnimg.cn/cd96e368cebc491090356fe5f8e8caa4.png
[Link 1]: https://www.lanqiao.cn/problems/2382/learning/?page=1&first_category_id=1&sort=students_count&difficulty=20&second_category_id=3&name=%E8%B6%85%E7%BA%A7%E8%B4%A8%E6%95%B0
[ce97922dc278432994ebb0e0040092b7.png]: https://img-blog.csdnimg.cn/ce97922dc278432994ebb0e0040092b7.png
[Link 2]: https://www.lanqiao.cn/problems/2191/learning/?page=1&first_category_id=1&sort=students_count&second_category_id=3&name=%E5%8D%A1&tags=2022
[5da835ab6ad1457f8dd5bcdcbbd5daeb.png]: https://img-blog.csdnimg.cn/5da835ab6ad1457f8dd5bcdcbbd5daeb.png
[Link 3]: https://www.lanqiao.cn/problems/2386/learning/?page=1&first_category_id=1&sort=students_count&second_category_id=3&tags=2022&difficulty=10