2019第十届蓝桥杯省赛JAVA A组真题解析（带源码及解析）

青旅半醒 2022-11-19 04:06 195阅读 0赞

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

### 目录： ###

*   *  蓝桥杯历年真题及解析.
     *   *  A：平方和（难度：★）
         *   *  题目：
             *  分析：
             *  代码：
         *  B：数列求值（难度：★）
         *   *  题目：
             *  分析：
             *  代码：
         *  C：迷宫（难度：★★★★）
         *   *  题目：
             *  分析：
             *  代码：
         *  D：最大降雨量（难度：★★★）
         *   *  题目：
             *  分析：
             *  代码：
         *  E：RSA解密（难度：★★★★★）
         *   *  题目：
             *  分析：
             *  代码：
         *  F：完全二叉树的权值（难度：★★）
         *   *  题目：
             *  分析：
             *  代码：
         *  G：外卖店优先级（难度：★★★）
         *   *  题目：
             *  分析：
             *  代码：
         *  H：修改数组（难度：★★★★）
         *   *  题目：
             *  分析：
             *  代码：
         *  I：糖果（难度：★★★★★）
         *   *  题目：
             *  分析：
             *  代码：
         *  J：组合数问题（难度：★★★★★）
         *   *  题目：
             *  分析：
             *  代码：
         *  算法交流群：

### A：平方和（难度：★） ###

#### 题目： ####

【问题描述】  
小明对数位中含有 2、0、1、9 的数字很感兴趣，在 1 到 40 中这样的数包  
括 1、2、9、10 至 32、39 和 40，共 28 个，他们的和是 574，平方和是 14362。  
注意，平方和是指将每个数分别平方后求和。  
请问，在 1 到 2019 中，所有这样的数的平方和是多少？  
【答案提交】  
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一  
个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。  
提示：如果你编写程序计算，发现结果是负的，请仔细检查自己的程序，  
不要怀疑考场的编程软件。

#### 分析： ####

数字比较大，用long，对每个数进行检查，符合条件即加入ans  
答案=2658417853

#### 代码： ####

满分

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

### B：数列求值（难度：★） ###

#### 题目： ####

【问题描述】  
给定数列 1, 1, 1, 3, 5, 9, 17, …，从第 4 项开始，每项都是前 3 项的和。求  
第 20190324 项的最后 4 位数字。  
【答案提交】  
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一  
个 4 位整数（提示：答案的千位不为 0），在提交答案时只填写这个整数，填写  
多余的内容将无法得分。

#### 分析： ####

斐波那契问题的plus版本，没有本质区别。  
模拟运算即可，%10000保证数据不要溢出。  
答案=4659

#### 代码： ####

满分

public class B数列求值 { 
        public static void main(String[] args) { 
            int arr[]=new int[20190325];
            arr[1]=1;
            arr[2]=1;
            arr[3]=1;
            for(int i=4;i<20190325;i++){ 
                arr[i]+=(arr[i-1]+arr[i-2]+arr[i-3]);
                arr[i]%=10000;
            }
            System.out.println(arr[20190324]);
        }
    }

### C：迷宫（难度：★★★★） ###

#### 题目： ####

【问题描述】  
下图给出了一个迷宫的平面图，其中标记为 1 的为障碍，标记为 0 的为可  
以通行的地方。  
010000  
000100  
001001  
110000  
迷宫的入口为左上角，出口为右下角，在迷宫中，只能从一个位置走到这  
个它的上、下、左、右四个方向之一。  
对于上面的迷宫，从入口开始，可以按DRRURRDDDR 的顺序通过迷宫，  
一共 10 步。其中 D、U、L、R 分别表示向下、向上、向左、向右走。  
对于下面这个更复杂的迷宫（30 行 50 列），请找出一种通过迷宫的方式，  
其使用的步数最少，在步数最少的前提下，请找出字典序最小的一个作为答案。  
请注意在字典序中D<L<R<U。（如果你把以下文字复制到文本文件中，请务  
必检查复制的内容是否与文档中的一致。在试题目录下有一个文件 maze.txt，  
内容与下面的文本相同）

> 01010101001011001001010110010110100100001000101010  
> 00001000100000101010010000100000001001100110100101  
> 01111011010010001000001101001011100011000000010000  
> 01000000001010100011010000101000001010101011001011  
> 00011111000000101000010010100010100000101100000000  
> 11001000110101000010101100011010011010101011110111  
> 00011011010101001001001010000001000101001110000000  
> 10100000101000100110101010111110011000010000111010  
> 00111000001010100001100010000001000101001100001001  
> 11000110100001110010001001010101010101010001101000  
> 00010000100100000101001010101110100010101010000101  
> 11100100101001001000010000010101010100100100010100  
> 00000010000000101011001111010001100000101010100011  
> 10101010011100001000011000010110011110110100001000  
> 10101010100001101010100101000010100000111011101001  
> 10000000101100010000101100101101001011100000000100  
> 10101001000000010100100001000100000100011110101001  
> 00101001010101101001010100011010101101110000110101  
> 11001010000100001100000010100101000001000111000010  
> 00001000110000110101101000000100101001001000011101  
> 10100101000101000000001110110010110101101010100001  
> 00101000010000110101010000100010001001000100010101  
> 10100001000110010001000010101001010101011111010010  
> 00000100101000000110010100101001000001000000000010  
> 11010000001001110111001001000011101001011011101000  
> 00000110100010001000100000001000011101000000110011  
> 10101000101000100010001111100010101001010000001000  
> 10000010100101001010110000000100101010001011101000  
> 00111100001000010000000110111000000001000000001011  
> 10000001100111010111010001000110111010101101111000

【答案提交】  
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一  
个字符串，包含四种字母 D、U、L、R，在提交答案时只填写这个字符串，填  
写多余的内容将无法得分。

#### 分析： ####

迷宫类型的题目一般用BFS or DFS，  
此题询问移动路线，所以我们选择BFS。  
为了防止陷入死循环，我们采用一个buf数组用来标记。  
每次移动将移动路径记录下来，  
当走到终点时，将路线依次与ans相比较。  
最终走完所有路径即得到结果。  
答案=DDDDRRURRRRRRDRRRRDDDLDDRDDDDDDDDDDDDRDDRRRURRUURRDDDDRDRRRRRRDRRURRDDDRRRRUURUUUUUUULULLUUUURRRRUULLLUUUULLUUULUURRURRURURRRDDRRRRRDDRRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR

#### 代码： ####

满分

//ans="DDDDRRURRRRRRDRRRRDDDLDDRDDDDDDDDDDDDRDDRRRURRUURRDDDDRDRRRRRRDRRURRDDDRRRRUURUUUUUUULULLUUUURRRRUULLLUUUULLUUULUURRURRURURRRDDRRRRRDDRRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR";
    
    import java.util.HashMap;
    import java.util.Scanner;
    //范围明确不清晰，m写成了n
    //新制代码写完后，没有注释掉原来的代码。
    //简洁或的用法，先判断第一个表达式，符合情况即不再判断第二个表达式
    //hashMap在装入新的元素时，会把旧元素覆盖。
    public class  迷宫{ 
    	public static int n=30,m=50;
    	public static char c[][]=new char [n][m];
    	public static boolean b[][]=new boolean [n][m];
    	public static HashMap<Integer,String> old=new HashMap<Integer,String>();
    	public static HashMap<Integer,String> niu=new HashMap<Integer,String>();
    	public static String ans="";
    	public static boolean BFS(int x,int y,String s){ 
    		boolean ok=false;
    		b[x][y]=true;
    		for(int i=-1;i<2;i++){ 
    			for(int j=-1;j<2;j++){ 
    				if(Math.abs(i+j)!=1)continue;
    				if(i+x<0||j+y<0||i+x>=n||j+y>=m||c[x+i][y+j]=='1'||b[x+i][y+j])continue;//
    				int index=(i+x)*100+y+j;
    				String ns=s+f(i,j);
    				if(niu.containsKey(index)){ 
    					niu.put(index, ns.compareTo(niu.get(index))>0?niu.get(index):ns);
    				}else{ 
    					niu.put(index, ns);
    				}
    				if(i+x==n-1&&j+y==m-1){ 
    					ok=true;
    					if(ans.equals("")){ 
    						ans=ns;
    					}else{ 
    						ans=(ans.compareTo(ns)>0)?ns:ans;
    					}
    				}
    			}
    		}
    		
    		return ok;
    	}
    	public static String f(int x,int y){ 
    		if(x==1)return "D";
    		else if(x==-1)return "U";
    		else if (y==1)return "R";
    		else return "L";
    	}
    	public static void main(String[] args) { 
    		Scanner sc=new Scanner(System.in);
    		for(int i=0;i<n;i++){ 
    			c[i]=sc.next().toCharArray();
    		}
    		old.put(0, "");
    		boolean end=false;
    		while(!end){ 
    			for(int t:old.keySet()){ 
    				if(BFS(t/100,t%100,old.get(t))){ 
    					end=true;
    				}
    			}
    			old.clear();
    			old.putAll(niu);
    			niu.clear();
    		}
    		System.out.println(ans);
    	}
    }

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

#### 题目： ####

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

#### 分析： ####

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

#### 代码： ####

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

### E：RSA解密（难度：★★★★★） ###

#### 题目： ####

【问题描述】  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70][]

【答案提交】  
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一  
个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

#### 分析： ####

//稍候

#### 代码： ####

//稍候

### F：完全二叉树的权值（难度：★★） ###

#### 题目： ####

【问题描述】  
给定一棵包含 N 个节点的完全二叉树，树上每个节点都有一个权值，按从  
上到下、从左到右的顺序依次是 A1, A2, · · · AN，如下图所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 1]

现在小明要把相同深度的节点的权值加在一起，他想知道哪个深度的节点  
权值之和最大？如果有多个深度的权值和同为最大，请你输出其中最小的深度。  
注：根的深度是 1。  
【输入格式】  
第一行包含一个整数 N。  
第二行包含 N 个整数 A1, A2, · · · AN 。  
【输出格式】  
输出一个整数代表答案。  
【样例输入】  
7  
1 6 5 4 3 2 1  
【样例输出】  
2  
【评测用例规模与约定】  
对于所有评测用例，1 ≤ N ≤ 100000，−100000 ≤ Ai ≤ 100000。

#### 分析： ####

完全二叉树性质问题，统计深度相同的节点的value和，排序，最大的就是解。

#### 代码： ####

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

import java.util.Scanner;
    
    public class F完全二叉树的权值 { 
        public static void main(String[] args) { 
            Scanner sc=new Scanner(System.in);
            while(sc.hasNext()){ 
                int n=sc.nextInt();
                long x;
                int p=1;
                long ans[]=new long[20];
                for(int i=1;i<=n;i++){ 
                    x=sc.nextLong();
                    if(i>=Math.pow(2, p))p++;
                    ans[p]+=x;
                }
                long max=Integer.MIN_VALUE;
                for(int i=0;i<20;i++){ 
                    if(ans[i]>max){ 
                        max=ans[i];
                        p=i;
                    }
                }
                System.out.println(p);
            }
        }
    }

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

#### 题目： ####

【问题描述】  
“饱了么”外卖系统中维护着 N 家外卖店，编号 1 ∼ N。每家外卖店都有  
一个优先级，初始时 (0 时刻) 优先级都为 0。  
每经过 1 个时间单位，如果外卖店没有订单，则优先级会减少 1，最低减  
到 0；而如果外卖店有订单，则优先级不减反加，每有一单优先级加 2。  
如果某家外卖店某时刻优先级大于 5，则会被系统加入优先缓存中；如果  
优先级小于等于 3，则会被清除出优先缓存。  
给定 T 时刻以内的 M 条订单信息，请你计算 T 时刻时有多少外卖店在优  
先缓存中。  
【输入格式】  
第一行包含 3 个整数 N、M 和 T。  
以下 M 行每行包含两个整数 ts 和 id，表示 ts 时刻编号 id 的外卖店收到  
一个订单。  
【输出格式】  
输出一个整数代表答案。  
【样例输入】  
2 6 6  
1 1  
5 2  
3 1  
6 2  
2 1  
6 2  
【样例输出】  
1  
【样例解释】  
6 时刻时，1 号店优先级降到 3，被移除出优先缓存；2 号店优先级升到 6，  
加入优先缓存。所以是有 1 家店 (2 号) 在优先缓存中。  
【评测用例规模与约定】  
对于 80% 的评测用例，1 ≤ N, M, T ≤ 10000。  
对于所有评测用例，1 ≤ N, M, T ≤ 100000，1 ≤ ts ≤ T，1 ≤ id ≤ N。

#### 分析： ####

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

#### 代码： ####

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

import java.util.ArrayList;
    import java.util.HashMap;
    import java.util.HashSet;
    import java.util.Scanner;
     
    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：修改数组（难度：★★★★） ###

#### 题目： ####

【问题描述】  
给定一个长度为 N 的数组 A = \[A1, A2, · · · AN\]，数组中有可能有重复出现  
的整数。  
现在小明要按以下方法将其修改为没有重复整数的数组。小明会依次修改  
A2, A3, · · · , AN。  
当修改 Ai 时，小明会检查 Ai 是否在 A1 ∼ Ai−1 中出现过。如果出现过，则  
小明会给 Ai 加上 1 ；如果新的 Ai 仍在之前出现过，小明会持续给 Ai 加 1 ，直  
到 Ai 没有在 A1 ∼ Ai−1 中出现过。  
当 AN 也经过上述修改之后，显然 A 数组中就没有重复的整数了。  
现在给定初始的 A 数组，请你计算出最终的 A 数组。  
【输入格式】  
第一行包含一个整数 N。  
第二行包含 N 个整数 A1, A2, · · · , AN 。  
【输出格式】  
输出 N 个整数，依次是最终的 A1, A2, · · · , AN。  
【样例输入】  
5  
2 1 1 3 4  
【样例输出】  
2 1 3 4 5  
【评测用例规模与约定】  
对于 80% 的评测用例，1 ≤ N ≤ 10000。  
对于所有评测用例，1 ≤ N ≤ 100000，1 ≤ Ai ≤ 1000000。

#### 分析： ####

多用一个数组标记相同数字出现的次数，每次修改时直接加上相同次数即可起到优化时间的作用。

#### 代码： ####

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

import java.util.Scanner;
     
    public class H修改数组 { 
        public static void main(String[] args) { 
            Scanner sc=new Scanner(System.in);
            int n=sc.nextInt();
            int arr[]=new int[n];
            int ans[]=new int[n];
            int []cnt=new int[1000006];
            for(int i=0;i<n;i++){ 
                arr[i]=sc.nextInt();
                ans[i]=arr[i]+cnt[arr[i]];
                cnt[arr[i]]++;
            }
            boolean buf[]=new boolean[2000006];
            for(int i=0;i<ans.length;i++){ 
                while(buf[ans[i]]){ 
                    ans[i]++;
                }
                buf[ans[i]]=true;
            }
            StringBuilder sb=new StringBuilder();
            for(int i=0;i<ans.length;i++){ 
                sb.append((i==0?"":" ")+ans[i]);
            }
            System.out.println(sb.toString());
        }
    }

### I：糖果（难度：★★★★★） ###

#### 题目： ####

【问题描述】  
糖果店的老板一共有 M 种口味的糖果出售。为了方便描述，我们将 M 种  
口味编号 1 ∼ M。  
小明希望能品尝到所有口味的糖果。遗憾的是老板并不单独出售糖果，而  
是 K 颗一包整包出售。  
幸好糖果包装上注明了其中 K 颗糖果的口味，所以小明可以在买之前就知  
道每包内的糖果口味。  
给定 N 包糖果，请你计算小明最少买几包，就可以品尝到所有口味的糖  
果。  
【输入格式】  
第一行包含三个整数 N、M 和 K。  
接下来 N 行每行 K 这整数 T1, T2, · · · , TK，代表一包糖果的口味。  
【输出格式】  
一个整数表示答案。如果小明无法品尝所有口味，输出 −1。  
【样例输入】  
6 5 3  
1 1 2  
1 2 3  
1 1 3  
2 3 5  
5 4 2  
5 1 2  
【样例输出】  
2  
【评测用例规模与约定】  
对于 30% 的评测用例，1 ≤ N ≤ 20 。  
对于所有评测样例，1 ≤ N ≤ 100，1 ≤ M ≤ 20，1 ≤ K ≤ 20，1 ≤ Ti ≤ M。

#### 分析： ####

//稍候

#### 代码： ####

//稍候

### J：组合数问题（难度：★★★★★） ###

#### 题目： ####

【问题描述】  
给 n, m, k，求有多少对 (i, j) 满足 1 ≤ i ≤ n, 0 ≤ j ≤ min(i, m) 且 C  
j  
i ≡  
0(mod k)，k 是质数。其中 C  
j  
i 是组合数，表示从 i 个不同的数中选出 j 个组成  
一个集合的方案数。  
【输入格式】  
第一行两个数 t, k，其中 t 代表该测试点包含 t 组询问，k 的意思与上文中  
相同。  
接下来 t 行每行两个整数 n, m，表示一组询问。  
【输出格式】  
输出 t 行，每行一个整数表示对应的答案。由于答案可能很大，请输出答  
案除以 109 + 7 的余数。  
【样例输入】  
1 2  
3 3  
【样例输出】  
1  
【样例说明】  
在所有可能的情况中，只有 C  
1  
2 = 2 是 2 的倍数。  
【样例输入】  
2 5  
4 5  
6 7  
【样例输出】  
0  
7  
【样例输入】  
3 23  
23333333 23333333  
233333333 233333333  
2333333333 2333333333  
【样例输出】  
851883128  
959557926  
680723120  
【数据规模和约定】  
对于所有评测用例，1 ≤ k ≤ 108, 1 ≤ t ≤ 105, 1 ≤ n, m ≤ 1018，且 k 是质数。  
评测时将使用 10 个评测用例测试你的程序，每个评测用例的限制如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 2]

#### 分析： ####

//稍候

#### 代码： ####

//稍候

### 算法交流群： ###

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

[Link 1]: https://blog.csdn.net/qq_43652327/article/details/104899994
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70]: /images/20221022/985c6e353df84f60a2fd1805e808c352.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 1]: /images/20221022/8b17eb8f32724fb6b003acc028bc44c9.png
[20210414114059857.png]: /images/20221022/8670048316f444a8a2f3d2f158435c53.png
[20210414114228917.png]: /images/20221022/bb384f589a71434dab82faf70bfad2b6.png
[20210414114529242.png]: /images/20221022/8127557231f34395b6c1120d6f97eaa9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 2]: /images/20221022/162f8397ec6e422697aae75c88ae98e7.png
[20210414105035110.png]: /images/20221022/2f4718a0576c47b1aa7f4ef24c7bfe62.png