2020年第11届蓝桥杯 Java B组决赛真题详解及小结

Dear 丶 2022-12-21 09:29 197阅读 0赞

>  *  [蓝桥杯 Java B组 省赛决赛 真题详解及小结汇总【2013年(第4届)~2021年(第12届)】][Java B_ _ _2013_4_2021_12]
>  *  [第11届 蓝桥杯-第1、2次模拟(软件类)真题-(2020年3月、4月)-官方讲解视频][11_ _-_1_2_-_2020_3_4_-]
> 
> --------------------
> 
>  *  说明：大部分题解思路及程序代码 源自 [蓝桥杯 官网视频(Java B组历年真题解析)][_Java B] —— [郑未老师][Link 1]。
> 
> 1.  [2013年 第04届 蓝桥杯 Java B组 省赛真题详解及小结][2013_ _04_ _ Java B_]
> 2.  [2014年 第05届 蓝桥杯 Java B组 省赛真题详解及小结][2014_ _05_ _ Java B_]
> 3.  [2015年 第06届 蓝桥杯 Java B组 省赛真题详解及小结][2015_ _06_ _ Java B_]
> 4.  [2016年 第07届 蓝桥杯 Java B组 省赛真题详解及小结][2016_ _07_ _ Java B_]
> 5.  [2017年 第08届 蓝桥杯 Java B组 省赛真题详解及小结][2017_ _08_ _ Java B_]
> 6.  [2018年 第09届 蓝桥杯 Java B组 省赛真题详解及小结][2018_ _09_ _ Java B_]
> 7.  [2019年 第10届 蓝桥杯 Java B组 省赛真题详解及小结][2019_10_ _ Java B_]
> 8.  [2020年 第11届 蓝桥杯 第1次模拟赛真题详解及小结【Java版】（校内模拟）][2020_11_ _ _1_Java]// [官方讲解视频][11_ _-_1_2_-_2020_3_4_-]
> 9.  [2020年 第11届 蓝桥杯 第2次模拟赛真题详解及小结【Java版】][2020_11_ _ _2_Java]// [官方讲解视频][11_ _-_1_2_-_2020_3_4_-]
> 10. [2020年 第11届 蓝桥杯 C/C++ B组 省赛真题详解及小结【第1场省赛 2020.07.05】][2020_11_ _ C_C_ B_ _1_ 2020.07.05][【Java版】][2020_11_ _ C_C_ B_ _1_ 2020.07.05]
> 11. [2020年 第11届 蓝桥杯 Java B组 省赛真题详解及小结【第1场省赛 2020.07.05】][2020_11_ _ Java B_ _1_ 2020.07.05]
> 12. [2020年 第11届 蓝桥杯 Java B组 省赛真题详解及小结【第2场省赛 2020.10.17】][2020_ _11_ _ Java B_ _2_ 2020.10.17]
> 13. [2020年 第11届 蓝桥杯 Java C组 省赛真题详解及小结【第1场省赛 2020.07.05】][2020_11_ _ Java C_ _1_ 2020.07.05]
> 14. [2021年 第12届 蓝桥杯 第1次模拟赛真题详解及小结【Java版】][2021_ _12_ _ _1_Java]
> 15. 2021年 第12届 蓝桥杯 第2次模拟赛真题详解及小结【Java版】
> 16. 2021年 第12届 蓝桥杯 Java B组 省赛真题详解及小结
> 
> --------------------
> 
> 1.  [2015年 第06届 蓝桥杯 Java B组 决赛真题详解及小结][2015_ _06_ _ Java B_ 1]
> 2.  [2016年 第07届 蓝桥杯 Java B组 决赛真题详解及小结][2016_ _07_ _ Java B_ 1]
> 3.  [2017年 第08届 蓝桥杯 Java B组 决赛真题详解及小结][2017_ _08_ _ Java B_ 1]
> 4.  [2018年 第09届 蓝桥杯 Java B组 决赛真题详解及小结][2018_ _09_ _ Java B_ 1]
> 5.  [2019年 第10届 蓝桥杯 Java B组 决赛真题详解及小结][2019_ _10_ _ Java B_]
> 6.  [2020年 第11届 蓝桥杯 Java B组 决赛真题详解及小结][2020_ _11_ _ Java B_]

***目   录***

一、试题 A: 美丽的 2（本题总分：5 分）——答案：563

解法一：字符串.contains()

二、试题 B: 扩散（本题总分：5 分）——答案：20312088

解法一

解法二

三、试题 C: 阶乘约数（本题总分：10 分）——答案：39001250856960000

解法一

四、试题 D: 本质上升序列（本题总分：10 分）——答案：5977

解法一

五、试题 E: 玩具蛇（本题总分：15 分）——答案：552

解法一

六、试题 F: 蓝肽子序列（时间限制: 1.0s 内存限制: 512.0MB 本题总分：15 分）

解法一

七、试题 G: 皮亚诺曲线距离（时间限制: 1.0s 内存限制: 512.0MB 本题总分：20 分）

解法一

八、试题 H: 画廊（时间限制: 1.0s 内存限制: 512.0MB 本题总分：20 分）

解法一

九、试题 I: 补给（时间限制: 3.0s 内存限制: 512.0MB 本题总分：25 分）

解法一

十、试题 J: 质数行者（时间限制: 5.0s 内存限制: 512.0MB 本题总分：25 分）

解法一

小结

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

> ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk0OTEzNQ_size_16_color_FFFFFF_t_70][]   ![20201231183320767.png][]

# 一、试题 A: 美丽的 2（本题总分：5 分）——答案：563 #

> 【问题描述】
> 
> 小蓝特别喜欢 2，今年是公元 2020 年，他特别高兴。
> 
> 他很好奇，在公元 1 年到公元 2020 年（包含）中，有多少个年份的数位中包含数字 2？
> 
> 【答案提交】
> 
> 这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 解法一：字符串.contains() ##

> 【解析】：枚举暴力check
> 
> ![20201231183247855.png][]

package national_11_2020;
    
    public class A01_美丽的2 {
    
    	public static void main(String[] args) {
    		int answer = 0;
    		for (int i = 1; i <= 2020; i++) {
    			if ((i + "").contains("2")) {
    				answer++;
    			}
    		}
    		System.out.println(answer);
    	}
    
    }

# 二、试题 B: 扩散（本题总分：5 分）——答案：20312088 #

> 【问题描述】
> 
> 小蓝在一张无限大的特殊画布上作画。
> 
> 这张画布可以看成一个方格图，每个格子可以用一个二维的整数坐标表示。
> 
> 小蓝在画布上首先点了一下几个点：(0, 0), (2020, 11), (11, 14), (2000, 2000)。只有这几个格子上有黑色，其它位置都是白色的。
> 
> 每过一分钟，黑色就会扩散一点。具体的，如果一个格子里面是黑色，它就会扩散到上、下、左、右四个相邻的格子中，使得这四个格子也变成黑色（如果原来就是黑色，则还是黑色）。
> 
> 请问，经过 2020 分钟后，画布上有多少个格子是黑色的。
> 
> 【答案提交】
> 
> 这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 解法一 ##

> [原文链接wyk：2020第十一届蓝桥杯国赛JAVA B组真题解析（带源码及解析）][wyk_2020_JAVA B]
> 
> 【解析】：定义两个set容器，装状态压缩的坐标，定义一个二维数组标记中心。
> 
> ![20201231194057281.png][]

package national_11_2020;
    
    import java.util.HashSet;
    
    public class B02_扩散 {
    
    	public static HashSet<Integer> set1 = new HashSet<Integer>();
    	public static HashSet<Integer> set2 = new HashSet<Integer>();
    	public static boolean center[][] = new boolean[10000][10000];
    
    	public static void in(int n) {
    		int x = n / 10000;
    		int y = n % 10000;
    		center[x][y] = true;
    		for (int i = -1; i < 2; i++) {
    			for (int j = -1; j < 2; j++) {
    				if (Math.abs(i + j) == 1 && !center[x + i][y + j]) {
    					set2.add((x + i) * 10000 + y + j);
    				}
    			}
    		}
    	}
    
    	public static void main(String[] args) {
    		set1.add(50005000);
    		set1.add(70205011);
    		set1.add(50115014);
    		set1.add(70007000);
    		for (int i = 0; i < 2020; i++) {
    			for (int x : set1) {
    				in(x);
    			}
    			set1.clear();
    			set1.addAll(set2);
    			set2.clear();
    			System.out.println(i);
    		}
    		for (int n : set1) {
    			int x = n / 10000;
    			int y = n % 10000;
    			center[x][y] = true;
    		}
    		long ans = 0;
    		for (int i = 0; i < 10000; i++) {
    			for (int j = 0; j < 10000; j++) {
    				ans += center[i][j] ? 1 : 0;
    			}
    		}
    		System.err.println(ans);
    	}
    	
    }

## 解法二 ##

> [原文链接：蓝桥杯十一届javab国赛扩散][javab]
> 
> ![20201231194832213.png][]

package national_11_2020;
    
    import java.util.LinkedList;
    import java.util.Queue;
    
    public class B02_扩散2 {
    
    	static int[][] route = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
    	static int[][] map;
    
    	public static void main(String[] args) {
    		map = new int[10000][10000];
    		int[][] temp = new int[10000][10000];
    		int ans = 0;
    		// 初始化-1
    		for (int i = 0; i < map.length; i++) {
    			for (int j = 0; j < map[0].length; j++) {
    				map[i][j] = -1;
    			}
    		}
    		Queue<P> p_queue = new LinkedList<>();
    		p_queue.add(new P(2020, 2020, 0));
    		p_queue.add(new P(4040, 2031, 0));
    		p_queue.add(new P(2031, 2034, 0));
    		p_queue.add(new P(4020, 4020, 0));
    		while (!p_queue.isEmpty()) {
    			P p = p_queue.poll();
    			if (p.getStep() == 2020) {
    				for (int i = 0; i < map.length; i++) {
    					for (int j = 0; j < map[0].length; j++) {
    						if (map[i][j] == 1) {
    							ans++;
    						}
    					}
    				}
    				System.out.println(ans);
    				System.exit(0);
    			}
    			for (int i = 0; i < route.length; i++) {
    				int x1 = p.getX() + route[i][0];
    				int y1 = p.getY() + route[i][1];
    				if (map[x1][y1] == 1)
    					continue;
    				map[x1][y1] = 1;
    				p_queue.add(new P(x1, y1, p.getStep() + 1));
    			}
    		}
    
    	}
    
    }
    
    class P {
    
    	private int x;
    	private int y;
    	private int step;
    
    	public int getX() {
    		return x;
    	}
    
    	public void setX(int x) {
    		this.x = x;
    	}
    
    	public int getY() {
    		return y;
    	}
    
    	public void setY(int y) {
    		this.y = y;
    	}
    
    	public int getStep() {
    		return step;
    	}
    
    	public void setStep(int step) {
    		this.step = step;
    	}
    
    	public P(int x, int y, int step) {
    		this.x = x;
    		this.y = y;
    		this.step = step;
    	}
    
    }

# 三、试题 C: 阶乘约数（本题总分：10 分）——答案：39001250856960000 #

> 【问题描述】
> 
> 定义阶乘 n! = 1 × 2 × 3 × · · · × n。
> 
> 请问 100! （100 的阶乘）有多少个约数。
> 
> 【答案提交】
> 
> 这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 解法一 ##

> [求N的阶乘约数的个数][N]
> 
> 【解析】：先用Big Integer求出100！然后根据约数个数定理求出100！=Πpi^ai，ans=Π(ai+1)

# 四、试题 D: 本质上升序列（本题总分：10 分）——答案：5977 #

> 【问题描述】
> 
> 小蓝特别喜欢单调递增的事物。
> 
> 在一个字符串中，如果取出若干个字符，将这些字符按照在字符串中的顺序排列后是单调递增的，则成为这个字符串中的一个单调递增子序列。
> 
> 例如，在字符串 lanqiao 中，如果取出字符 n 和 q，则 nq 组成一个单调递增子序列。类似的单调递增子序列还有 lnq、i、ano 等等。
> 
> 小蓝发现，有些子序列虽然位置不同，但是字符序列是一样的，例如取第二个字符和最后一个字符可以取到 ao，取最后两个字符也可以取到 ao。小蓝认为他们并没有本质不同。
> 
> 对于一个字符串，小蓝想知道，本质不同的递增子序列有多少个？
> 
> 例如，对于字符串 lanqiao，本质不同的递增子序列有 21 个。它们分别 是 l、a、n、q、i、o、ln、an、lq、aq、nq、ai、lo、ao、no、io、lnq、anq、lno、ano、aio。
> 
> 请问对于以下字符串（共 200 个小写英文字母，分四行显示）：（如果你把以下文字复制到文本文件中，请务必检查复制的内容是否与文档中的一致。在试题目录下有一个文件 inc.txt，内容与下面的文本相同）
> 
> tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhf
> 
> iadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqij
> 
> gihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmad
> 
> vrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl
> 
> 本质不同的递增子序列有多少个？
> 
> 【答案提交】
> 
> 这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 解法一 ##

> [原文链接wyk：2020第十一届蓝桥杯国赛JAVA B组真题解析（带源码及解析）][wyk_2020_JAVA B]
> 
> ![2020123119451120.png][]

package national_11_2020;
    
    import java.util.Arrays;
    import java.util.Scanner;
    
    public class D04_本质上升序列 {
    
    	public static int[] dp;
    
    	public static void main(String[] args) {
    		Scanner sc = new Scanner(System.in);
    		String s = sc.next();
    		char[] num = s.toCharArray();
    		dp = new int[s.length()];
    		Arrays.fill(dp, 1);
    		for (int i = 0; i < s.length(); i++) {
    			for (int j = 0; j < i; j++) {
    				if (num[j] < num[i]) {
    					dp[i] += dp[j];
    				}
    				if (num[j] == num[i]) {
    					dp[i] -= dp[j];
    				}
    			}
    		}
    		int res = 0;
    		for (int i = 0; i < dp.length; i++) {
    			res += dp[i];
    		}
    		System.out.println(res);
    	}
    
    }

# 五、试题 E: 玩具蛇（本题总分：15 分）——答案：552 #

> 【问题描述】
> 
> 小蓝有一条玩具蛇，一共有 16 节，上面标着数字 1 至 16。每一节都是一个正方形的形状。相邻的两节可以成直线或者成 90 度角。
> 
> 小蓝还有一个 4 × 4 的方格盒子，用于存放玩具蛇，盒子的方格上依次标着字母 A 到 P 共 16 个字母。
> 
> 小蓝可以折叠自己的玩具蛇放到盒子里面。他发现，有很多种方案可以将 玩具蛇放进去。
> 
> 下图给出了两种方案：
> 
> ![20201231184408184.png][]
> 
> 请帮小蓝计算一下，总共有多少种不同的方案。如果两个方案中，存在玩具蛇的某一节放在了盒子的不同格子里，则认为是不同的方案。
> 
> 【答案提交】
> 
> 这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 解法一 ##

> [原文链接：蓝桥杯十一届javab国赛玩具蛇][javab 1]
> 
> 【解析】：暴力枚举dfs；暴力枚举起点，然后dfs。
> 
> ![20201231195128126.png][]

package national_11_2020;
    
    public class E05_玩具蛇 {
    
    	static int count;
    	static int[][] route = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
    	static int[][] temp = new int[4][4];
    
    	public static void main(String[] args) {
    		for (int i = 0; i < 4; i++) {
    			for (int j = 0; j < 4; j++) {
    				temp[i][j] = 1;
    				dfs(i, j, 1);
    				// 清零
    				clean(temp);
    			}
    		}
    		System.out.println(count);
    	}
    
    	private static void dfs(int x, int y, int ans) {
    		if (ans == 16) {
    			for (int[] ints : temp) {
    				for (int i : ints) {
    					if (i == 0)
    						return;
    				}
    			}
    			count++;
    			return;
    		}
    		for (int i = 0; i < route.length; i++) {
    			int x1 = x + route[i][0];
    			int y1 = y + route[i][1];
    			if (x1 < 0 || y1 < 0 || x1 >= 4 || y1 >= 4)
    				continue;
    			if (temp[x1][y1] != 0)
    				continue;
    			temp[x1][y1] = ans + 1;
    			dfs(x1, y1, ans + 1);
    			temp[x1][y1] = 0;
    		}
    	}
    
    	private static void clean(int[][] arr) {
    		for (int i = 0; i < arr.length; i++) {
    			for (int j = 0; j < arr[0].length; j++) {
    				arr[i][j] = 0;
    			}
    		}
    	}
    
    	private static void print(int[][] arr) {
    		for (int i = 0; i < arr.length; i++) {
    			for (int j = 0; j < arr[0].length; j++) {
    				System.out.print(arr[i][j] + "    ");
    			}
    			System.out.println();
    		}
    	}
    
    }

# 六、试题 F: 蓝肽子序列（时间限制: 1.0s 内存限制: 512.0MB 本题总分：15 分） #

> 【问题描述】
> 
> L 星球上的生物由蛋蓝质组成，每一种蛋蓝质由一类称为蓝肽的物资首尾连接成一条长链后折叠而成。
> 
> 生物学家小乔正在研究 L 星球上的蛋蓝质。她拿到两个蛋蓝质的蓝肽序列，想通过这两条蓝肽序列的共同特点来分析两种蛋蓝质的相似性。
> 
> 具体的，一个蓝肽可以使用 1 至 5 个英文字母表示，其中第一个字母大写，后面的字母小写。一个蛋蓝质的蓝肽序列可以用蓝肽的表示顺序拼接而成。
> 
> 在一条蓝肽序列中，如果选取其中的一些位置，把这些位置的蓝肽取出，并按照它们在原序列中的位置摆放，则称为这条蓝肽的一个子序列。蓝肽的子序列不一定在原序列中是连续的，中间可能间隔着一些未被取出的蓝肽。
> 
> 如果第一条蓝肽序列可以取出一个子序列与第二条蓝肽序列中取出的某个子序列相等，则称为一个公共蓝肽子序列。
> 
> 给定两条蓝肽序列，找出他们最长的那个公共蓝肽子序列的长度。
> 
> 【输入格式】
> 
> 输入两行，每行包含一个字符串，表示一个蓝肽序列。字符串中间没有空格等分隔字符。
> 
> 【输出格式】
> 
> 输出一个整数，表示最长的那个公共蓝肽子序列的长度。
> 
> 【样例输入】
> 
> LanQiaoBei
> 
> LanTaiXiaoQiao
> 
> 【样例输出】
> 
> 2
> 
> 【样例说明】
> 
> 最长的公共蓝肽子序列为 LanQiao，共两个蓝肽。
> 
> 【评测用例规模与约定】
> 
> 对于 20% 的评测用例，两个字符串的长度均不超过 20。
> 
> 对于 50% 的评测用例，两个字符串的长度均不超过 100。
> 
> 对于所有评测用例，两个字符串的长度均不超过 1000。

## 解法一 ##

> 【解析】：标准动态规划。

# 七、试题 G: 皮亚诺曲线距离（时间限制: 1.0s 内存限制: 512.0MB 本题总分：20 分） #

> 【问题描述】
> 
> 皮亚诺曲线是一条平面内的曲线。 下图给出了皮亚诺曲线的 1 阶情形，它是从左下角出发，经过一个 3 × 3 的方格中的每一个格子，最终到达右上角的一条曲线。
> 
> ![20201231184830808.png][]
> 
> 下图给出了皮亚诺曲线的 2 阶情形，它是经过一个 ![3^\{2\} \\times 3^\{2\}][3_2_ _times 3_2] 的方格中的每一个格子的一条曲线。它是将 1 阶曲线的每个方格由 1 阶曲线替换而成。
> 
> ![20201231185009141.png][]
> 
> 下图给出了皮亚诺曲线的 3 阶情形，它是经过一个 ![3^\{2\} \\times 3^\{2\}][3_2_ _times 3_2] 的方格中的每一 个格子的一条曲线。它是将 2 阶曲线的每个方格由 1 阶曲线替换而成。
> 
> ![20201231185037539.png][]
> 
> 皮亚诺曲线总是从左下角开始出发，最终到达右上角。
> 
> 我们将这些格子放到坐标系中，对于 k 阶皮亚诺曲线，左下角的坐标是 (0, 0)，右上角坐标是 (![3^\{k\}][3_k] − 1, ![3^\{k\}][3_k] − 1)，右下角坐标是 (![3^\{k\}][3_k] − 1, 0)，左上角坐标是 (0, ![3^\{k\}][3_k] − 1)。
> 
> 给定 k 阶皮亚诺曲线上的两个点的坐标，请问这两个点之间，如果沿着皮亚诺曲线走，距离是到少？
> 
> 【输入格式】
> 
> 输入的第一行包含一个正整数 k，皮亚诺曲线的阶数。 第二行包含两个整数 x1, y1，表示第一个点的坐标。
> 
> 第三行包含两个整数 x2, y2，表示第二个点的坐标。
> 
> 【输出格式】
> 
> 输出一个整数，表示给定的两个点之间的距离。
> 
> 【样例输入】
> 
> 1
> 
> 0 0
> 
> 2 2
> 
> 【样例输出】
> 
> 8
> 
> 【样例输入】
> 
> 2
> 
> 0 2
> 
> 0 3
> 
> 【样例输出】
> 
> 13
> 
> 【评测用例规模与约定】
> 
> 对于 30% 的评测用例，0 ≤ k ≤ 10。
> 
> 对于 50% 的评测用例，0 ≤ k ≤ 20。
> 
> 对于所有评测用例，0 ≤ k ≤ 100, 0 ≤ x1, y1, x2, y2 < ![3^\{k\}][3_k] , x1, y1, x2, y2 ≤ ![10^\{18\}][10_18]。 数据保证答案不超过 ![10^\{18\}][10_18]。

## 解法一 ##

# 八、试题 H: 画廊（时间限制: 1.0s 内存限制: 512.0MB 本题总分：20 分） #

> 【问题描述】
> 
> 小蓝办了一个画展，在一个画廊左右两边陈列了他自己的作品。为了使画展更有意思，小蓝没有等距陈列自己的作品，而是按照更有艺术感的方式陈列。在画廊的左边陈列了 L 幅作品，在画廊的右边陈列了 R 幅作品，左边的作品距离画廊的起点依次为 ![u\_\{1\}][u_1], ![u\_\{2\}][u_2], · · · , ![u\_\{L\}][u_L]，右边的作品距离画廊起点依次为 ![v\_\{1\}][v_1], ![v\_\{1\}][v_1], · · · , ![v\_\{R\}][v_R]。
> 
> 每周，小蓝要整理一遍自己的每一幅作品。整理一幅作品的时间是固定的，但是要带着沉重的工具。从一幅作品到另一幅作品之间的距离为直线段的长度。
> 
> 小蓝从画廊的起点的正中央（左右两边的中点）出发，整理好每一幅画，最终到达画廊的终点的正中央。已知画廊的宽为 w。
> 
> 请问小蓝最少带着工具走多长的距离？
> 
> 【输入格式】
> 
> 输入的第一行包含四个整数 L, R, d, w，表示画廊左边和右边的作品数量， 以及画廊的长度和宽度。
> 
> 第二行包含 L 个正整数 ![u\_\{1\}][u_1], ![u\_\{2\}][u_2], · · · , ![u\_\{L\}][u_L]，表示画廊左边的作品的位置。
> 
> 第三行包含 R 个正整数 ![v\_\{1\}][v_1], ![v\_\{1\}][v_1], · · · , ![v\_\{R\}][v_R]，表示画廊右边的作品的位置。
> 
> 【输出格式】
> 
> 输出一个实数，四舍五入保留两位小数，表示小蓝最少带着工具走的距离。
> 
> 【样例输入】
> 
> 3 3 10 2
> 
> 1 3 8
> 
> 2 4 6
> 
> 【样例输出】
> 
> 14.71
> 
> 【样例说明】
> 
> 小蓝从起点开始，首先到达左边第一幅作品（走动距离 √ 2），然后到达左边第二幅作品（走动距离 2），然后到达右边第一幅作品（走动距离 √ 5），然后到达右边第二幅和第三幅作品（走动距离 2 和 2），然后到达左边第三幅作品（走动距离 2 √ 2），最后到达画廊终点（走动距离 √ 5）。
> 
> 总共距离为 √ 2 + 2 + √ 5 + 2 + 2 + 2 √ 2 + √ 5 ≈ 14.71。
> 
> 【评测用例规模与约定】
> 
> 对于 40% 的评测用例，1 ≤ L, R ≤ 10, 1 ≤ d ≤ 100, 1 ≤ w ≤ 100。
> 
> 对于 70% 的评测用例，1 ≤ L, R ≤ 100, 1 ≤ d ≤ 1000, 1 ≤ w ≤ 1000。
> 
> 对于所有评测用例，1 ≤ L, R ≤ 500, 1 ≤ d ≤ 100000, 1 ≤ w ≤ 100000, 0 ≤ ![u\_\{1\}][u_1] < ![u\_\{2\}][u_2] < · · · < ![u\_\{L\}][u_L] ≤ d, 0 ≤ ![v\_\{1\}][v_1] < ![v\_\{2\}][v_2] < · · · < ![v\_\{R\}][v_R] ≤ d。

## 解法一 ##

# 九、试题 I: 补给（时间限制: 3.0s 内存限制: 512.0MB 本题总分：25 分） #

> 【问题描述】
> 
> 小蓝是一个直升飞机驾驶员，他负责给山区的 n 个村庄运送物资。每个月，他都要到每个村庄至少一次，可以多于一次，将村庄需要的物资运送过去。每个村庄都正好有一个直升机场，每两个村庄之间的路程都正好是村庄之间的直线距离。
> 
> 由于直升机的油箱大小有限，小蓝单次飞行的距离不能超过 D。每个直升机场都有加油站，可以给直升机加满油。
> 
> 每个月，小蓝都是从总部出发，给各个村庄运送完物资后回到总部。如果方便，小蓝中途也可以经过总部来加油。
> 
> 总部位于编号为 1 的村庄。
> 
> 请问，要完成一个月的任务，小蓝至少要飞行多长距离？
> 
> 【输入格式】
> 
> 输入的第一行包含两个整数 n, D，分别表示村庄的数量和单次飞行的距离。
> 
> 接下来 n 行描述村庄的位置，其中第 i 行两个整数 ![x\_\{i\}][x_i] , ![y\_\{i\}][y_i]，表示编号为 i 的村庄的坐标。村庄 i 和村庄 j 之间的距离为 √ (xi − xj) 2 + (yi − yj) 2。
> 
> 【输出格式】
> 
> 输出一行，包含一个实数，四舍五入保留正好 2 位小数，表示答案。
> 
> 【样例输入】
> 
> 4 10 1 1 5 5 1 5
> 
> 5 1
> 
> 【样例输出】
> 
> 16.00
> 
> 【样例说明】
> 
> 四个村庄形成一个正方形的形状。
> 
> 【样例输入】
> 
> 4 6 1 1 4 5 8 5 11 1
> 
> 【样例输出】
> 
> 28.00
> 
> 【样例说明】
> 
> 补给顺序为 1 → 2 → 3 → 4 → 3 → 2 → 1。
> 
> 【评测用例规模与约定】
> 
> 对于所有评测用例，1 ≤ n ≤ 20, 1 ≤ ![x\_\{i\}][x_i] , ![y\_\{i\}][y_i] ≤ ![10^\{4\}][10_4] , 1 ≤ D ≤ ![10^\{5\}][10_5]。

## 解法一 ##

# 十、试题 J: 质数行者（时间限制: 5.0s 内存限制: 512.0MB 本题总分：25 分） #

> 【问题描述】
> 
> 小蓝在玩一个叫质数行者的游戏。
> 
> 游戏在一个 n × m × w 的立体方格图上进行，从北到南依次标号为第 1 行到第 n 行，从西到东依次标号为第 1 列到第 m 列，从下到上依次标号为第 1 层到第 w 层。
> 
> 小蓝要控制自己的角色从第 1 行第 1 列第 1 层移动到第 n 行第 m 列第 w 层。每一步，他可以向东走质数格、向南走质数格或者向上走质数格。每走到一个位置，小蓝的角色要稍作停留。
> 
> 在游戏中有两个陷阱，分别为第 r1 行第 c1 列第 h1 层和第 r2 行第 c2 列第 h2 层。这两个陷阱的位置可以跨过，但不能停留。也就是说，小蓝不能控制角色某一步正好走到陷阱上，但是某一步中间跨过了陷阱是允许的。
> 
> 小蓝最近比较清闲，因此他想用不同的走法来完成这个游戏。所谓两个走法不同，是指小蓝稍作停留的位置集合不同。
> 
> 请帮小蓝计算一下，他总共有多少种不同的走法。
> 
> 提示：请注意内存限制，如果你的程序运行时超过内存限制将不得分。
> 
> 【输入格式】
> 
> 输入第一行包含两个整数 n, m, w，表示方格图的大小。
> 
> 第二行包含 6 个整数，r1, c1, h1, r2, c2, h2，表示陷阱的位置。
> 
> 【输出格式】
> 
> 输出一行，包含一个整数，表示走法的数量。答案可能非常大，请输出答案除以 1000000007 的余数。
> 
> 【样例输入】
> 
> 5 6 1
> 
> 3 4 1 1 2 1
> 
> 【样例输出】
> 
> 11
> 
> 【样例说明】
> 
> 用 (r, c, h) 表示第 r 行第 c 列第 h 层，可能的走法有以下几种：
> 
> 1. (1, 1, 1) − (1, 3, 1) − (1, 6, 1) − (3, 6, 1) − (5, 6, 1)。
> 
> 2. (1, 1, 1) − (1, 3, 1) − (3, 3, 1) − (3, 6, 1) − (5, 6, 1)。
> 
> 3. (1, 1, 1) − (1, 3, 1) − (3, 3, 1) − (5, 3, 1) − (5, 6, 1)。
> 
> 4. (1, 1, 1) − (3, 1, 1) − (3, 3, 1) − (3, 6, 1) − (5, 6, 1)。
> 
> 5. (1, 1, 1) − (3, 1, 1) − (3, 3, 1) − (5, 3, 1) − (5, 6, 1)。
> 
> 6. (1, 1, 1) − (3, 1, 1) − (5, 1, 1) − (5, 3, 1) − (5, 6, 1)。
> 
> 7. (1, 1, 1) − (3, 1, 1) − (5, 1, 1) − (5, 4, 1) − (5, 6, 1)。
> 
> 8. (1, 1, 1) − (1, 4, 1) − (1, 6, 1) − (3, 6, 1) − (5, 6, 1)。
> 
> 9. (1, 1, 1) − (1, 6, 1) − (3, 6, 1) − (5, 6, 1)。
> 
> 10. (1, 1, 1) − (3, 1, 1) − (3, 6, 1) − (5, 6, 1)。
> 
> 11. (1, 1, 1) − (3, 1, 1) − (5, 1, 1) − (5, 6, 1)。
> 
> 【评测用例规模与约定】
> 
> 对于 30% 的评测用例 1 ≤ n, m,w ≤ 50。
> 
> 对于 60% 的评测用例 1 ≤ n, m,w ≤ 300。
> 
> 对于所有评测用例，1 ≤ n, m, w ≤ 1000，1 ≤ r1,r2 ≤ n, 1 ≤ c1, c2 ≤ m, 1 ≤ h1, h2 ≤ w，陷阱不在起点或终点，两个陷阱不同。

## 解法一 ##

# 小结 #

> 只会第1题，能得蓝桥杯国家优秀奖。。。

[Java B_ _ _2013_4_2021_12]: https://blog.csdn.net/weixin_44949135/article/details/108230143
[11_ _-_1_2_-_2020_3_4_-]: https://blog.csdn.net/weixin_44949135/article/details/106223446
[_Java B]: http://dasai.lanqiao.cn/pages/dasai/news_detail_w.html?id=644
[Link 1]: https://blog.csdn.net/zhengwei223
[2013_ _04_ _ Java B_]: https://blog.csdn.net/weixin_44949135/article/details/108087292
[2014_ _05_ _ Java B_]: https://blog.csdn.net/weixin_44949135/article/details/108098676
[2015_ _06_ _ Java B_]: https://blog.csdn.net/weixin_44949135/article/details/108123806
[2016_ _07_ _ Java B_]: https://blog.csdn.net/weixin_44949135/article/details/108142487
[2017_ _08_ _ Java B_]: https://blog.csdn.net/weixin_44949135/article/details/108143554
[2018_ _09_ _ Java B_]: https://blog.csdn.net/weixin_44949135/article/details/108144284
[2019_10_ _ Java B_]: https://blog.csdn.net/weixin_44949135/article/details/108150820
[2020_11_ _ _1_Java]: https://blog.csdn.net/weixin_44949135/article/details/108179383
[2020_11_ _ _2_Java]: https://blog.csdn.net/weixin_44949135/article/details/108203734
[2020_11_ _ C_C_ B_ _1_ 2020.07.05]: https://blog.csdn.net/weixin_44949135/article/details/108232922
[2020_11_ _ Java B_ _1_ 2020.07.05]: https://blog.csdn.net/weixin_44949135/article/details/108228625
[2020_ _11_ _ Java B_ _2_ 2020.10.17]: https://blog.csdn.net/weixin_44949135/article/details/109402088
[2020_11_ _ Java C_ _1_ 2020.07.05]: https://blog.csdn.net/weixin_44949135/article/details/108240826
[2021_ _12_ _ _1_Java]: https://blog.csdn.net/weixin_44949135/article/details/111873706
[2015_ _06_ _ Java B_ 1]: https://blog.csdn.net/weixin_44949135/article/details/109589070
[2016_ _07_ _ Java B_ 1]: https://blog.csdn.net/weixin_44949135/article/details/109588929
[2017_ _08_ _ Java B_ 1]: https://blog.csdn.net/weixin_44949135/article/details/109499807
[2018_ _09_ _ Java B_ 1]: https://blog.csdn.net/weixin_44949135/article/details/109565870
[2019_ _10_ _ Java B_]: https://blog.csdn.net/weixin_44949135/article/details/109406449
[2020_ _11_ _ Java B_]: https://blog.csdn.net/weixin_44949135/article/details/109711931
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk0OTEzNQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2020123118205996.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk0OTEzNQ==,size_16,color_FFFFFF,t_70
[20201231183320767.png]: /images/20221120/dcaa298f1bd24512afa5fa5932945fc8.png
[20201231183247855.png]: /images/20221120/c84ce7f209ba4e66a4aab20a884b549e.png
[wyk_2020_JAVA B]: https://blog.csdn.net/qq_43652327/article/details/109690012
[20201231194057281.png]: /images/20221120/69efc112ba254a8faab0fe75da2d93dd.png
[javab]: https://blog.csdn.net/qq_42794826/article/details/109941294
[20201231194832213.png]: /images/20221120/917c10b1cbd149bfbb0bb762d67c7d2d.png
[N]: https://blog.csdn.net/ji414341055/article/details/5759157
[2020123119451120.png]: /images/20221120/61ee0b7c3b9a44438c20bd5a2bcab8d2.png
[20201231184408184.png]: /images/20221120/7ee9f1cbb8b14138a162811e90ae5f23.png
[javab 1]: https://blog.csdn.net/qq_42794826/article/details/109940074
[20201231195128126.png]: /images/20221120/152ef50749bf475e902c67064f72b17c.png
[20201231184830808.png]: /images/20221120/cf554fb7f456409384d0a243e34902b6.png
[3_2_ _times 3_2]: https://private.codecogs.com/gif.latex?3%5E%7B2%7D%20%5Ctimes%203%5E%7B2%7D
[20201231185009141.png]: /images/20221120/384b772080ab4ce2a62a3da79ce1801c.png
[20201231185037539.png]: /images/20221120/41702c36e22e4216817215013ecb6163.png
[3_k]: https://private.codecogs.com/gif.latex?3%5E%7Bk%7D
[10_18]: https://private.codecogs.com/gif.latex?10%5E%7B18%7D
[u_1]: https://private.codecogs.com/gif.latex?u_%7B1%7D
[u_2]: https://private.codecogs.com/gif.latex?u_%7B2%7D
[u_L]: https://private.codecogs.com/gif.latex?u_%7BL%7D
[v_1]: https://private.codecogs.com/gif.latex?v_%7B1%7D
[v_R]: https://private.codecogs.com/gif.latex?v_%7BR%7D
[v_2]: https://private.codecogs.com/gif.latex?v_%7B2%7D
[x_i]: https://private.codecogs.com/gif.latex?x_%7Bi%7D
[y_i]: https://private.codecogs.com/gif.latex?y_%7Bi%7D
[10_4]: https://private.codecogs.com/gif.latex?10%5E%7B4%7D
[10_5]: https://private.codecogs.com/gif.latex?10%5E%7B5%7D