2019第十届蓝桥杯JAVA C组题解

逃离我推掉我的手 2023-06-18 03:54 19阅读 0赞

## [蓝桥杯历年真题及解析][Link 1]. ##

### 目录： ###

*   *  蓝桥杯历年真题及解析.
     *   *  A：求和（难度：★）
         *   *  题目：
             *  分析：
             *  代码：
         *  B：矩形切割（难度：★）
         *   *  题目：
             *  分析：
             *  代码：
         *  C：不同子串（难度：★★）
         *   *  题目：
             *  分析：
             *  代码：
         *  D：质数（难度：★★★）
         *   *  题目：
             *  分析：
             *  代码：
         *  E：最大降雨量（难度：★★★）
         *   *  题目：
             *  分析：
             *  代码：
         *  F：旋转（难度：★★）
         *   *  题目：
             *  分析：
             *  代码：
         *  G：外卖店优先级（难度：★★★★）
         *   *  题目：
             *  分析：
             *  代码：
         *  H：人物相关性分析（难度：★★★★）
         *   *  题目：
             *  分析：
             *  代码：
         *  I：等差数列（难度：★★★★）
         *   *  题目：
             *  分析：
             *  代码：
         *  J：扫地机器人（难度：★★★★★）
         *   *  题目：
             *  分析：
             *  代码：
         *  算法交流群

### A：求和（难度：★） ###

#### 题目： ####

//试题 A: 求和  
//本题总分：5 分  
//【问题描述】  
//小明对数位中含有 2、0、1、9 的数字很感兴趣，在 1 到 40 中这样的数包  
//括 1、2、9、10 至 32、39 和 40，共 28 个，他们的和是 574。  
//请问，在 1 到 2019 中，所有这样的数的和是多少？  
//【答案提交】  
//这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一  
//个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

#### 分析： ####

暴力枚举每个数字，挨个check即可。  
答案=1905111

#### 代码： ####

package JC2019;
    //正确
    public class A求和 { 
    	public static boolean check(int i){ 
    		int x;
    		while(i>0){ 
    			x=i%10;
    			i/=10;
    			if(x==2||x==0||x==1||x==9){ 
    				return true;
    			}
    		}
    		return false;
    	}
    	public static void main(String[] args) { 
    		long sum=0;
    		for(int i=0;i<=2019;i++){ 
    			if(check(i)){ 
    				sum+=i;
    			}
    		}
    		System.out.println(sum);
    	}
    }

### B：矩形切割（难度：★） ###

#### 题目： ####

//【问题描述】  
//小明有一些矩形的材料，他要从这些矩形材料中切割出一些正方形。  
//当他面对一块矩形材料时，他总是从中间切割一刀，切出一块最大的正方  
//形，剩下一块矩形，然后再切割剩下的矩形材料，直到全部切为正方形为止。  
//例如，对于一块两边分别为 5 和 3 的材料（记为 5 × 3），小明会依次切出  
//3 × 3、2 × 2、1 × 1、1 × 1 共 4 个正方形。  
//现在小明有一块矩形的材料，两边长分别是 2019 和 324。请问小明最终会  
//切出多少个正方形？  
//【答案提交】  
//这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一  
//个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

#### 分析： ####

类似gcd的做法，及时更换长和宽，当宽度为0时跳出，  
其余状态累加即为结果。  
答案=21

#### 代码： ####

public class B矩形切割 { 
    	public static int f(int w,int h){ 
    		if(h==0)return 0;
    		else return w/h+f(h,w%h);
    	}
    	public static void main(String[] args) { 
    		System.out.println(f(2019,324));
    	}
    }

### C：不同子串（难度：★★） ###

#### 题目： ####

//【问题描述】  
//一个字符串的非空子串是指字符串中长度至少为 1 的连续的一段字符组成  
//的串。例如，字符串aaab 有非空子串a, b, aa, ab, aaa, aab, aaab，一共 7 个。  
//注意在计算时，只算本质不同的串的个数。  
//请问，字符串0100110001010001 有多少个不同的非空子串？  
//【答案提交】  
//这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一  
//个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

#### 分析： ####

枚举起点和终点，装入Set自动去重，  
Set长度即为答案。  
答案=100

#### 代码： ####

package JC2019;
    //正确
    import java.util.HashSet;
    public class C { 
    	public static void main(String[] args) { 
    		String s="0100110001010001";
    		HashSet<String> set=new HashSet<String>();
    		for(int i=0;i<=s.length();i++){ 
    			for(int j=i;j<=s.length();j++){ 
    				String ss=s.substring(i,j);
    				set.add(ss);
    			}
    		}
    		System.out.println(set.size()-1);
    	}
    }

### D：质数（难度：★★★） ###

#### 题目： ####

//【问题描述】  
//我们知道第一个质数是 2、第二个质数是 3、第三个质数是 5……请你计算  
//第 2019 个质数是多少？  
//【答案提交】  
//这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一  
//个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

#### 分析： ####

从头到尾查一下质数即可，  
改一下质数筛也行，做法很多。  
答案=17569

#### 代码： ####

package JC2019;
    //正确
    public class D质数 { 
        static int p[]=new int[5000],len=0;
        static void init(){ 
            boolean buf[]=new boolean[30000];
            for(int i=2;i*i<buf.length;i++){ 
                for(int j=i*i;j<buf.length;j+=i){ 
                    buf[j]=true;
                }
            }
            for(int i=2;i<buf.length;i++){ 
                if(!buf[i]){ 
                    p[len]=i;
                    len++;
                }
            }
        }
        public static void main(String[] args) { 
            init();
            System.out.println(p[2018]);
        }
    }

### E：最大降雨量（难度：★★★） ###

#### 题目： ####

//【问题描述】  
//由于沙之国长年干旱，法师小明准备施展自己的一个神秘法术来求雨。  
//这个法术需要用到他手中的 49 张法术符，上面分别写着 1 至 49 这 49 个  
//数字。法术一共持续 7 周，每天小明都要使用一张法术符，法术符不能重复使  
//用。  
//每周，小明施展法术产生的能量为这周 7 张法术符上数字的中位数。法术  
//施展完 7 周后，求雨将获得成功，降雨量为 7 周能量的中位数。  
//由于干旱太久，小明希望这次求雨的降雨量尽可能大，请大最大值是多少？  
//【答案提交】  
//这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一  
//个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

#### 分析： ####

建立7\*7二维数组  
使从左到右严格递增  
使每行中位数从上到下严格递增  
得出该二维数组中位数右下角均为比它大的数  
则中位数最大值为49-16+1  
答案=34

#### 代码： ####

package JC2019;
    //正确
    public class E { 
    	public static void main(String[] args) { 
    		System.out.println(49-16+1);
    	}
    }

### F：旋转（难度：★★） ###

#### 题目： ####

//【问题描述】  
//图片旋转是对图片最简单的处理方式之一，在本题中，你需要对图片顺时  
//针旋转 90 度。  
//我们用一个 n × m 的二维数组来表示一个图片，例如下面给出一个 3 × 4 的  
//图片的例子：  
//1 3 5 7  
//9 8 7 6  
//3 5 9 7  
//这个图片顺时针旋转 90 度后的图片如下：  
//3 9 1  
//5 8 3  
//9 7 5  
//7 6 7  
//给定初始图片，请计算旋转后的图片。  
//【输入格式】  
//输入的第一行包含两个整数 n 和 m，分别表示行数和列数。  
//接下来 n 行，每行 m 个整数，表示给定的图片。图片中的每个元素（像  
//素）为一个值为 0 至 255 之间的整数（包含 0 和 255）。  
//【输出格式】  
//输出 m 行 n 列，表示旋转后的图片。  
//【样例输入】  
//3 4  
//1 3 5 7  
//9 8 7 6  
//3 5 9 7  
//【样例输出】  
//3 9 1  
//5 8 3  
//9 7 5  
//7 6 7  
//【评测用例规模与约定】  
//对于 30% 的评测用例，1 ≤ n, m ≤ 10。  
//对于 60% 的评测用例，1 ≤ n, m ≤ 30。  
//对于所有评测用例，1 ≤ n, m ≤ 100。

#### 分析： ####

定义一个m \* n的数组，按照提目要求进行模拟即可。  
![在这里插入图片描述][20210331212700509.png]

#### 代码： ####

package JC2019;
    //正确
    import java.util.Scanner;
    
    public class F { 
    	public static void main(String[] args) { 
    		Scanner sc=new Scanner (System.in);
    		int n=sc.nextInt(),m=sc.nextInt();
    		int tran[][]=new int[m][n];
    		for(int i=n-1;i>=0;i--){ 
    			for(int j=0;j<m;j++){ 
    				tran[j][i]=sc.nextInt();
    			}
    		}
    		for(int i=0;i<m;i++){ 
    			for(int j=0;j<n;j++){ 
    				System.out.print(tran[i][j]+" ");
    			}
    			System.out.println();
    		}
    	}
    }

### G：外卖店优先级（难度：★★★★） ###

#### 题目： ####

“饱了么”外卖系统中维护着N 家外卖店，编号1~N。  
每家外卖店都有一个优先级，初始时(0 时刻) 优先级都为0。  
每经过1 个时间单位，如果外卖店没有订单，则优先级会减少1，最低减到0；  
而如果外卖店有订单，则优先级不减反加，每有一单优先级加2。  
如果某家外卖店某时刻优先级大于5，则会被系统加入优先缓存中；  
如果优先级小于等于3，则会被清除出优先缓存。  
给定T 时刻以内的M 条订单信息，请你计算T 时刻时有多少外卖店在优先缓存中。  
输入  
第一行包含3 个整数N、M 和T。  
以下M 行每行包含两个整数ts 和id，表示ts 时刻编号id 的外卖店收到一个订单  
1<=N, M, T<=100000，1<=ts<=T，1<=id<=N。

输出  
输出一个整数代表答案。  
样例输入  
2 6 6  
1 1  
5 2  
3 1  
6 2  
2 1  
6 2  
样例输出  
1

#### 分析： ####

![在这里插入图片描述][2021033121351825.png]

pro数组记录所有店铺的优先级  
last数组记录所有店铺最后卖出东西的时间  
采用邻接表接受订单信息，  
ans表示当前优先队列有哪些店铺  
根据订单信息更新pro数组，last数组，ans队列。  
最后遍历所有店铺进行检查更新维护。

#### 代码： ####

import java.util.*;
     
    public class G外卖店优先级 { 
        public static void main(String[] args) { 
            Scanner sc=new Scanner(System.in);
            while(sc.hasNext()){ 
                int n=sc.nextInt();
                int m=sc.nextInt();
                int t=sc.nextInt();
                int pro[]=new int[n+1];
                int last[]=new int[n+1];
                HashMap<Integer,Integer> arr[]=new HashMap[t+1];
                for(int i=0;i<=t;i++){ 
                    arr[i]=new HashMap<Integer,Integer>();
                }
                int ts,id;
                for(int i=0;i<m;i++){ 
                    ts=sc.nextInt();
                    id=sc.nextInt();
                    arr[ts].put(id, arr[ts].getOrDefault(id, 0)+1);
                }
                HashSet<Integer> ans=new HashSet<Integer>();
                for(int i=0;i<=t;i++){ 
                    for(int x:arr[i].keySet()){ 
                        pro[x]=Math.max(0, pro[x]-(i-last[x]-1));
                        if(pro[x]<=3&&ans.contains(x))ans.remove(x);
                        pro[x]+=arr[i].get(x)*2;
                        if(pro[x]>5&&!ans.contains(x))ans.add(x);
                        last[x]=i;
                    }
                }
                for(int i=1;i<=n;i++){ 
                    if(last[i]!=t){ 
                        pro[i]=Math.max(0, pro[i]-(t-last[i]));
                        if(pro[i]<=3&&ans.contains(i))ans.remove(i);
                    }
                }
                System.out.println(ans.size());
            }
        }
    }

### H：人物相关性分析（难度：★★★★） ###

#### 题目： ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 1]

#### 分析： ####

![在这里插入图片描述][20210331214646562.png]

我们通过字符串处理提取出来所有的Alice和Bob所在的位置信息，  
之后采用差分的方式分布Alice的权值信息到差分数组。  
将差分数组恢复成前缀和，  
根据前缀和数组和Bob位置计算相关性。

#### 代码： ####

import java.util.*;
     
    public class H人物相关性分析{ 
        public static void main(String[] args) { 
            Scanner sc = new Scanner(System.in);
            int k = sc.nextInt();
            sc.nextLine();
            String s = sc.nextLine();
            char c[] = s.toCharArray();
            ArrayList<Integer> Al = new ArrayList<Integer>();
            ArrayList<Integer> Bo = new ArrayList<Integer>();
            for (int i = 0; i < c.length; i++) { 
                if ((i - 1 < 0 || c[i - 1] == '.' || c[i - 1] == ' ') && c[i] == 'A' && c[i + 1] == 'l' && c[i + 2] == 'i'
                        && c[i + 3] == 'c' && c[i + 4] == 'e' && (c[i + 5] == '.' || c[i + 5] == ' ')) { 
                    Al.add(i);
                }
            }
            for (int i = 0; i < c.length; i++) { 
                if ((i - 1 < 0 || c[i - 1] == '.' || c[i - 1] == ' ') && c[i] == 'B' && c[i + 1] == 'o' && c[i + 2] == 'b'
                        && (c[i + 3] == '.' || c[i + 3] == ' ')) { 
                    Bo.add(i);
                }
            }
     
            long ans = 0;
            int CF[] = new int[1000009];
            int QZH[] = new int[1000005];
            for (int t : Al) { 
                CF[Math.max(0, t - k - 3)]++;
                CF[Math.min(1000000, t + k + 5)]--;
            }
            QZH[0] = CF[0];
            for (int i = 1; i < 1000005; i++) { 
                QZH[i] = QZH[i - 1] + CF[i];
            }
            for (int t : Bo) { 
                ans += QZH[t];
            }
            System.out.println(ans);
        }
    }

### I：等差数列（难度：★★★★） ###

#### 题目： ####

数学老师给小明出了一道等差数列求和的题目。但是粗心的小明忘记了一部分的数列，只记得其中N 个整数。  
现在给出这N 个整数，小明想知道包含这N 个整数的最短的等差数列有几项？  
输入  
输入的第一行包含一个整数N。  
第二行包含N 个整数A1.A2,…, AN。(注意A1<=AN 并不一定是按等差数列中的顺序给出)  
2<=N<=100000,0<=Ai<=10^9  
输出  
输出一个整数表示答案。  
样例输入  
5  
2 6 4 10 20  
样例输出  
10  
提示  
包含2、6、4、10、20 的最短的等差数列是2、4、6、8、10、12、14、16、18、20。

#### 分析： ####

![在这里插入图片描述][20210331214705345.png]

将一组数据进行排序，  
求出相邻数据的差值，所有差值的GCD即为最大公差，  
（最大值-最小值）/ 最大公差 + 1 即为最终结果。

#### 代码： ####

import java.util.*;
     
    public class I等差数列 { 
        static long gcd(long A,long B){ 
            if(B==0)return A;
            else return gcd(B,A%B);
        }
        public static void main(String[] args) { 
            Scanner sc=new Scanner(System.in);
            while(sc.hasNext()){ 
                int n=sc.nextInt();
                long arr[]=new long[n];
                for(int i=0;i<n;i++){ 
                    arr[i]=sc.nextLong();
                }
                Arrays.sort(arr);
                long dc=arr[1]-arr[0];
                for(int i=2;i<n;i++){ 
                    dc=gcd(dc,arr[i]-arr[i-1]);
                }
                System.out.println(dc==0?n:(arr[n-1]-arr[0])/dc+1);
            }
        }
    }

### J：扫地机器人（难度：★★★★★） ###

#### 题目： ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 3]

#### 分析： ####

![在这里插入图片描述][20210331214806624.png]  
二分答案，我们只需要二分出打扫所需的时间，  
然后对该时间进行检查是否可以完成打扫即可。

#### 代码： ####

import java.util.Scanner;
     
    public class Main { 
        public static int n;
        public static int arr[];
        public static boolean clear[];
        public static boolean check(int arr[],int x){ 
            clear=new boolean[n+1];
            int p=0;
            int flag=0;
            int index=1;
            boolean out=true;
            while(index<=n){ 
                p=0;
                flag=0;
                while(p<x&&index+p<=n){ 
                    if(index+p<=n&&arr[index+p]>0){ 
                        if(arr[index+p]==1){     
                            flag++;
                            if(flag==2){ 
                                break;
                            }
                        }else{ 
                            flag++;
                            arr[index+p]--;
                            clear[index+p]=true;
                            break;
                        }
                    }
                    clear[index+p]=true;
                    p++;
                }
                if(flag>0){ 
                    index+=p;
                }else{ 
                    return false;
                }
            }
            for(int i=1;i<=n;i++){ 
                if(!clear[i])return clear[i];
            }
            return true;
        }
        public static void main(String[] args) { 
            Scanner sc=new Scanner(System.in);
            n=sc.nextInt();
            int k=sc.nextInt();
            arr=new int[n+1];
            for(int i=0;i<k;i++){ 
                arr[sc.nextInt()]++;
            }
             
            int l=1,r=n,mid=(l+r)/2;
            while(l<=r){ 
                mid=(l+r)/2;
                boolean cur=check(arr,mid);
                boolean cur1=check(arr,mid-1);
                if(cur&&!cur1){ 
                    break;
                }else if(cur){ 
                    r=mid;
                }else{ 
                    l=mid+1;
                }
            }
            System.out.println((mid-1)*2);
        }
    }

### 算法交流群 ###

![在这里插入图片描述][20210331215932968.png]

[Link 1]: https://blog.csdn.net/qq_43652327/article/details/104899994
[20210331212700509.png]: https://img-blog.csdnimg.cn/20210331212700509.png
[2021033121351825.png]: https://img-blog.csdnimg.cn/2021033121351825.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210331213749355.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/2021033121383191.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3,size_16,color_FFFFFF,t_70
[20210331214646562.png]: https://img-blog.csdnimg.cn/20210331214646562.png
[20210331214705345.png]: https://img-blog.csdnimg.cn/20210331214705345.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/2021033121490741.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20210331214933484.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3,size_16,color_FFFFFF,t_70
[20210331214806624.png]: https://img-blog.csdnimg.cn/20210331214806624.png
[20210331215932968.png]: https://img-blog.csdnimg.cn/20210331215932968.png