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

分手后的思念是犯贱 2022-11-20 04:49 176阅读 0赞

>  *  [蓝桥杯 Java B组 省赛决赛 真题详解及小结汇总【2013年(第4届)~2020年(第11届)】][Java B_ _ _2013_4_2020_11]
>  *  [第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]
> 
> --------------------
> 
> 1.  2015年 第06届 蓝桥杯 Java B组 决赛真题详解及小结
> 2.  2016年 第07届 蓝桥杯 Java B组 决赛真题详解及小结
> 3.  2017年 第08届 蓝桥杯 Java B组 决赛真题详解及小结
> 4.  2018年 第09届 蓝桥杯 Java B组 决赛真题详解及小结
> 5.  2019年 第10届 蓝桥杯 Java B组 决赛真题详解及小结
> 6.  2020年 第11届 蓝桥杯 Java B组 决赛真题详解及小结

***目   录***

一、三角形面积——答案：8.795

解法一：手工计算（大矩形-三角形）

解法二：海伦公式

二、最大乘积——答案：839542176

解法一

解法二

三、全排列——答案：for (int j = cur + 1; j <= i; j++) data\[j-1\] = data\[j\];

四、整理玩具

五、版本分支

六、防御力

小结

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

> ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk0OTEzNQ_size_16_color_FFFFFF_t_70][]

# 一、三角形面积——答案：8.795 #

> 标题：三角形面积
> 
> 已知三角形三个顶点在直角坐标系下的坐标分别为：  
> (2.3, 2.5)  
> (6.4, 3.1)  
> (5.1, 7.2)
> 
> 求该三角形的面积。
> 
> 注意，要提交的是一个小数形式表示的浮点数。  
> 要求精确到小数后3位，如不足3位，需要补零。

## 解法一：手工计算（大矩形-三角形） ##

> [原文链接][Link 2]
> 
> ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk0OTEzNQ_size_16_color_FFFFFF_t_70 1][]  ![20201108190248364.png][]

## 解法二：海伦公式 ##

> [原文链接][Link 3][——wyk][Link 3]
> 
> ![20201108184414866.png][]
> 
> ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk0OTEzNQ_size_16_color_FFFFFF_t_70 2][]

package national_09_2018;
    
    public class A01_三角形面积 {
    
    	public static void main(String[] args) {
    		double s1 = 4.7 * 2.8 / 2;
    		double s2 = 1.3 * 4.1 / 2;
    		double s3 = 4.1 * 0.6 / 2;
    		double ss = 4.1 * 4.7;
    		System.out.println(String.format("%.3f", s1));
    		System.out.println(String.format("%.3f", s2));
    		System.out.println(String.format("%.3f", s3));
    		System.out.println(String.format("%.3f", ss));
    		System.out.println(String.format("%.3f", ss - s1 - s2 - s3));
    		System.out.println("---");
    		double a = Math.sqrt((6.4 - 2.3) * (6.4 - 2.3) + (3.1 - 2.5) * (3.1 - 2.5)); // ac边
    		double b = Math.sqrt((6.4 - 5.1) * (6.4 - 5.1) + (3.1 - 7.2) * (3.1 - 7.2)); // bc边
    		double c = Math.sqrt((5.1 - 2.3) * (5.1 - 2.3) + (7.2 - 2.5) * (7.2 - 2.5)); // ab边
    		double p = (a + b + c) / 2;
    		System.out.println(String.format("%.3f", a));
    		System.out.println(String.format("%.3f", b));
    		System.out.println(String.format("%.3f", c));
    		System.out.println(String.format("%.3f", p));
    		System.out.println(String.format("%.3f", Math.sqrt(p * (p - a) * (p - b) * (p - c))));
    	}
    
    }

# 二、最大乘积——答案：839542176 #

> 标题：最大乘积
> 
> 把 1~9 这9个数字分成两组，中间插入乘号，  
> 有的时候，它们的乘积也只包含1~9这9个数字，而且每个数字只出现1次。
> 
> 比如：  
> 984672 \* 351 = 345619872  
> 98751 \* 3462 = 341875962  
> 9 \* 87146325 = 784316925  
> ...
> 
> 符合这种规律的算式还有很多，请你计算在所有这些算式中，乘积最大是多少？
> 
> 注意，需要提交的是一个整数，表示那个最大的积，不要填写任何多余的内容。  
> （只提交乘积，不要提交整个算式）

## 解法一 ##

> ![20201108204924573.png][]
> 
> 前期乘积肯定有很多不符合条件的，这些信息不应该return掉，应该继续循环下一次。
> 
> check()函数：将数组按位进行分割。 
> 
> 1.  1-8：arr\[0\]~arr\[0\]、arr\[1\]~arr\[8\]
> 2.  2-7：arr\[0\]~arr\[1\]、arr\[2\]~arr\[8\]
> 3.  3-6：arr\[0\]~arr\[2\]、arr\[3\]~arr\[8\]
> 4.  4-5：arr\[0\]~arr\[3\]、arr\[4\]~arr\[8\]
> 5.  5-4：arr\[0\]~arr\[4\]、arr\[5\]~arr\[8\]
> 6.  6-3：arr\[0\]~arr\[5\]、arr\[6\]~arr\[8\]
> 7.  7-2：arr\[0\]~arr\[6\]、arr\[7\]~arr\[8\]
> 8.  8-1：arr\[0\]~arr\[7\]、arr\[8\]~arr\[8\]

package national_09_2018;
    
    import java.math.BigInteger;
    import java.util.Arrays;
    import java.util.HashSet;
    
    public class B02_最大乘积 {
    
    	static int maxValue = 0;
    
    	public static void main(String[] args) {
    //		System.out.println("" + 1 + 2); // 12
    //		System.out.println("Integer.MAX_VALUE: " + Integer.MAX_VALUE);
    		int a[] = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    		f(a, 0);
    //		check(a);
    		System.out.println(maxValue);
    	}
    
    	public static void f(int arr[], int k) { // 全排列 列出1~9的全部组合
    		if (k == arr.length) {
    //			System.out.println(Arrays.toString(arr));
    			check(arr);
    			return;
    		}
    		for (int i = k; i < arr.length; i++) {
    			int temp = arr[i];
    			arr[i] = arr[k];
    			arr[k] = temp;
    			f(arr, k + 1);
    			temp = arr[i];
    			arr[i] = arr[k];
    			arr[k] = temp;
    		}
    	}
    
    	public static void check(int arr[]) { // 将数组按位进行分割: 1-8\2-7\...\4-5\5-4\...\8-1
    		for (int i = 0; i < 8; i++) { // 循环8次
    			String front = "", back = "";
    			for (int j = 0; j <= i; j++) {
    				front = front + arr[j];
    //				System.out.println("front: " + front);
    			}
    			for (int j = i + 1; j <= 8; j++) {
    				back = back + arr[j];
    //				System.out.println("back: " + back);
    			}
    //			System.out.println(front + "、" + back + "\n");
    			int tempSum = Integer.parseInt(front) * Integer.parseInt(back);
    
    			char[] charArray = (tempSum + "").toCharArray();
    			if (charArray.length != 9) {
    //				return; // 不能return!!! 要continue!
    				// 前期乘积肯定有很多不符合条件的，这些信息不应该return掉，应该继续循环下一次。
    				continue;
    			}
    			HashSet<Character> hashSet = new HashSet<Character>(); // 去重
    			for (int k = 0; k < charArray.length; k++) {
    				hashSet.add(charArray[k]);
    			}
    			if (hashSet.size() != 9 || hashSet.contains('0')) {
    //				return; // 不能return!!! 要continue!
    				// 前期乘积肯定有很多不符合条件的，这些信息不应该return掉，应该继续循环下一次。
    				continue;
    			}
    
    			if (tempSum >= maxValue) {
    				maxValue = tempSum;
    			}
    		}
    	}
    
    }

## 解法二 ##

> [原文链接][Link 3][——wyk][Link 3]
> 
> 【解析】：全排列出九个数字的所有排列顺序，  
> 对每一种排列进行枚举，分割成两部分，  
> 对两部分的乘积取结果，  
> 检查乘积结果是否符合条件，  
> 如果符合条件，即更新全局变量ans。
> 
> ![20201108203233316.png][]

package national_09_2018;
    
    import java.util.HashSet;
    
    public class B02_最大乘积2 { // 求最大值，不是求符合条件的种数。
    
    	public static long arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    	public static long ans = 0;
    
    	public static long tolong(int begin, int end) {
    		long cur = 0;
    		for (int i = begin; i <= end; i++) {
    			cur *= 10;
    			cur += arr[i];
    		}
    		return cur;
    	}
    
    	public static void check() {
    		for (int i = 0; i < 8; i++) {
    			long x = tolong(0, i);
    			long y = tolong(i + 1, 8);
    			long cur = x * y;
    			if (cur < 123456789)
    				continue;
    			HashSet<Integer> set = new HashSet<Integer>();
    			while (cur > 0) {
    				set.add((int) (cur % 10));
    				cur /= 10;
    			}
    			if (set.size() == 9 && !set.contains(0)) {
    				ans = Math.max(ans, x * y);
    			}
    		}
    	}
    
    	public static void qpl(int k) { // 全排列
    		if (k >= arr.length) {
    			check();
    		} else {
    			for (int i = k; i < arr.length; i++) {
    				long t = arr[i];
    				arr[i] = arr[k];
    				arr[k] = t;
    				qpl(k + 1);
    				t = arr[i];
    				arr[i] = arr[k];
    				arr[k] = t;
    			}
    		}
    	}
    
    	public static void main(String[] args) {
    		qpl(0);
    		System.out.println(ans);
    	}
    
    }

# 三、全排列——答案：for (int j = cur + 1; j <= i; j++) data\[j-1\] = data\[j\]; #

> 标题：全排列
> 
> 对于某个串，比如：“1234”，求它的所有全排列。  
> 并且要求这些全排列一定要按照字母的升序排列。  
> 对于“1234”，应该输出(一共4!=24行)：  
> 1234  
> 1243  
> 1324  
> 1342  
> 1423  
> 1432  
> 2134  
> 2143  
> 2314  
> 2341  
> 2413  
> 2431  
> 3124  
> 3142  
> 3214  
> 3241  
> 3412  
> 3421  
> 4123  
> 4132  
> 4213  
> 4231  
> 4312  
> 4321
> 
> 下面是实现程序，请仔细分析程序逻辑，并填写划线部分缺少的代码。
> 
> // 轮换前k个，再递归处理  
> import java.util.\*;  
> public class A  
> \{  
>     static void permu(char\[\] data, int cur)\{  
>         if(cur==data.length-1)\{  
>             System.out.println(new String(data));  
>             return;  
>         \}  
>           
>         for(int i=cur; i<data.length; i++)\{  
>             char tmp = data\[i\];   
>             for(int j=i-1; j>=cur; j--) data\[j+1\] = data\[j\];  
>             data\[cur\] = tmp;            
> 
>             permu(data, cur+1);            
> 
>             tmp = data\[cur\];   
>             \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_ ;  
>             data\[i\] = tmp;              
>         \}  
>     \}  
>       
>     static void permu(String x)\{  
>         permu(x.toCharArray(),0);  
>     \}  
>       
>     public static void main(String\[\] args)\{  
>         permu("1234");  
>     \}  
> \}
> 
>   
> 请注意：只需要填写划线部分缺少的内容，不要抄写已有的代码或符号。

> [原文链接][Link 3][——wyk][Link 3]
> 
> 【答案】：for (int j = cur + 1; j <= i; j++) data\[j-1\] = data\[j\];
> 
> 【解析】：观察题目发现是个全排列问题，填空部分是全排列的回溯部分，只需要根据函数体内上半部分交换的原则重新进行回溯回去即可。
> 
> ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk0OTEzNQ_size_16_color_FFFFFF_t_70 3][]

package national_09_2018;
    
    import java.util.*;
    
    public class C03_全排列 {
    
    	static void permu(char[] data, int cur) {
    		if (cur == data.length - 1) {
    			System.out.println(new String(data));
    			return;
    		}
    
    		for (int i = cur; i < data.length; i++) {
    			char tmp = data[i];
    			for (int j = i - 1; j >= cur; j--)
    				data[j + 1] = data[j];
    			data[cur] = tmp;
    
    			permu(data, cur + 1);
    
    			tmp = data[cur];
    //				_______________________________________;
    			for (int j = cur + 1; j <= i; j++)
    				data[j-1] = data[j];
    //			_______________________________________;
    			data[i] = tmp;
    		}
    	}
    
    	static void permu(String x) {
    		permu(x.toCharArray(), 0);
    	}
    
    	public static void main(String[] args) {
    		permu("1234");
    	}
    
    }

# 四、整理玩具 #

> 标题：整理玩具
> 
> 小明有一套玩具，一共包含NxM个部件。这些部件摆放在一个包含NxM个小格子的玩具盒中，每个小格子中恰好摆放一个部件。  
> 
> 每一个部件上标记有一个0~9的整数，有可能有多个部件标记相同的整数。  
> 
> 小明对玩具的摆放有特殊的要求：标记相同整数的部件必须摆在一起，组成一个矩形形状。
> 
> 如以下摆放是满足要求的：
> 
> 00022  
> 00033  
> 44444  
> 
> 12244  
> 12244  
> 12233
> 
> 01234  
> 56789
> 
> 以下摆放不满足要求：
> 
> 11122  
> 11122  
> 33311
> 
> 111111  
> 122221  
> 122221  
> 111111
> 
> 11122  
> 11113  
> 33333
> 
> 给出一种摆放方式，请你判断是否符合小明的要求。
> 
> 输入  
> \----  
> 输入包含多组数据。    
> 第一行包含一个整数T，代表数据组数。 (1 <= T <= 10)   
> 以下包含T组数据。    
> 每组数据第一行包含两个整数N和M。  (1 <= N, M <= 10)    
> 以下包含N行M列的矩阵，代表摆放方式。  
> 
> 输出  
> \---  
> 对于每组数据，输出YES或者NO代表是否符合小明的要求。  
> 
> 【样例输入】  
> 3    
> 3 5    
> 00022  
> 00033  
> 44444    
> 3 5    
> 11122  
> 11122  
> 33311  
> 2 5    
> 01234  
> 56789
> 
> 【样例输出】  
> YES  
> NO  
> YES
> 
>   
> 资源约定：  
> 峰值内存消耗（含虚拟机） < 256M  
> CPU消耗  < 1000ms
> 
>   
> 请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
> 
> 所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。  
> 不要使用package语句。不要使用jdk1.7及以上版本的特性。  
> 主类的名字必须是：Main，否则按无效代码处理。

> [原文链接][Link 3][——wyk][Link 3]
> 
> 【解析】：由题目可以确定数字相同的玩具放在了一起，  
> 所以我们可以定义一个数组用来存放当前数据的信息，  
> 我们采用二维数组，  
> 每一行代表当前编号玩具的信息  
> 第一列表示当前编号玩具的占地面积  
> 第二列表示当前编号玩具的占地右下角的横坐标  
> 第三列表示当前编号玩具的占地右下角的纵坐标  
> 第四列表示当前编号玩具的占地左上角的横坐标  
> 第五列表示当前编号玩具的占地左上角的纵坐标  
> 所以应该有
> 
> \-> buf\[i\]\[0\] != 0 && buf\[i\]\[0\] != (buf\[i\]\[1\] - buf\[i\]\[3\] + 1) \* (buf\[i\]\[2\] - buf\[i\]\[4\] + 1)
> 
> 恒成立。
> 
> ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk0OTEzNQ_size_16_color_FFFFFF_t_70 4][]

package national_09_2018;
    
    import java.util.Scanner;
    
    public class D04_整理玩具 {
    
    	public static void main(String[] args) {
    		Scanner scanner = new Scanner(System.in);
    		int t = scanner.nextInt();
    		while (t-- > 0) {
    			int n = scanner.nextInt(), m = scanner.nextInt();
    			char c[][] = new char[n][m];
    			int buf[][] = new int[10][5];
    			for (int i = 0; i < 10; i++) {
    				buf[i][0] = 0;
    				buf[i][1] = -1;
    				buf[i][2] = -1;
    				buf[i][3] = 999;
    				buf[i][4] = 999;
    			}
    			for (int i = 0; i < n; i++) {
    				c[i] = scanner.next().toCharArray();
    			}
    			for (int i = 0; i < n; i++) {
    				for (int j = 0; j < m; j++) {
    					buf[c[i][j] - '0'][0]++;
    					buf[c[i][j] - '0'][1] = Math.max(buf[c[i][j] - '0'][1], i);
    					buf[c[i][j] - '0'][2] = Math.max(buf[c[i][j] - '0'][2], j);
    					buf[c[i][j] - '0'][3] = Math.min(buf[c[i][j] - '0'][3], i);
    					buf[c[i][j] - '0'][4] = Math.min(buf[c[i][j] - '0'][4], j);
    				}
    			}
    			boolean ok = true;
    			for (int i = 0; i < 10; i++) {
    				if (buf[i][0] != 0 && buf[i][0] != (buf[i][1] - buf[i][3] + 1) * (buf[i][2] - buf[i][4] + 1)) {
    					ok = false;
    				}
    			}
    			System.out.println(ok ? "YES" : "NO");
    		}
    	}
    
    }

# 五、版本分支 #

> 标题：版本分支
> 
> 小明负责维护公司一个奇怪的项目。这个项目的代码一直在不断分支(branch)但是从未发生过合并(merge)。  
> 现在这个项目的代码一共有N个版本，编号1~N，其中1号版本是最初的版本。  
> 除了1号版本之外，其他版本的代码都恰好有一个直接的父版本；即这N个版本形成了一棵以1为根的树形结构。  
> 
> 如下图就是一个可能的版本树：
> 
>     1  
>    / \\  
>   2   3  
>   |  / \\  
>   5 4   6
> 
> 现在小明需要经常检查版本x是不是版本y的祖先版本。你能帮助小明吗？
> 
> 输入  
> \----  
> 第一行包含两个整数N和Q，代表版本总数和查询总数。    
> 以下N-1行，每行包含2个整数u和v，代表版本u是版本v的直接父版本。    
> 再之后Q行，每行包含2个整数x和y，代表询问版本x是不是版本y的祖先版本。  
> 
> 对于30%的数据，1 <= N <= 1000  1 <= Q <= 1000    
> 对于100%的数据，1 <= N <= 100000  1 <= Q <= 100000  
> 
> 输出  
> \----  
> 对于每个询问，输出YES或NO代表x是否是y的祖先。  
> 
> 【样例输入】  
> 6 5  
> 1 2  
> 1 3  
> 2 5  
> 3 6  
> 3 4  
> 1 1  
> 1 4  
> 2 6  
> 5 2  
> 6 4
> 
> 【样例输出】  
> YES  
> YES  
> NO  
> NO  
> NO
> 
> 资源约定：  
> 峰值内存消耗（含虚拟机） < 256M  
> CPU消耗  < 1000ms
> 
>   
> 请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
> 
> 所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。  
> 不要使用package语句。不要使用jdk1.7及以上版本的特性。  
> 主类的名字必须是：Main，否则按无效代码处理。

> [原文链接——wyk][Link 3]
> 
> 【解析】：wyk大佬用并查集的思路，用一个数组储存该节点的父节点，当询问祖先关系是，向上查找父节点，时间复杂度较高，通过数据50%。
> 
> ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk0OTEzNQ_size_16_color_FFFFFF_t_70 5][]

package national_09_2018;
    
    import java.util.*;
    
    public class E05_版本分支 {
    
    	public static void main(String[] args) {
    		Scanner sc = new Scanner(System.in);
    		int n = sc.nextInt(), q = sc.nextInt(), u, v;
    		int pa[] = new int[n + 1];
    		for (int i = 1; i < n; i++) {
    			u = sc.nextInt();
    			v = sc.nextInt();
    			pa[v] = u;
    		}
    		for (int i = 0; i < q; i++) {
    			u = sc.nextInt();
    			v = sc.nextInt();
    			boolean is = false;
    			while (v != 0) {
    				if (v == u) {
    					is = true;
    					break;
    				}
    				v = pa[v];
    			}
    			System.out.println(is ? "YES" : "NO");
    		}
    	}
    
    }

# 六、防御力 #

> 标题：防御力
> 
> 小明最近在玩一款游戏。对游戏中的防御力很感兴趣。  
> 我们认为直接影响防御的参数为“防御性能”，记作d，而面板上有两个防御值A和B，与d成对数关系，A=2^d，B=3^d（注意任何时候上式都成立）。  
> 在游戏过程中，可能有一些道具把防御值A增加一个值，有另一些道具把防御值B增加一个值。  
> 现在小明身上有n1个道具增加A的值和n2个道具增加B的值，增加量已知。
> 
> 现在已知第i次使用的道具是增加A还是增加B的值，但具体使用那个道具是不确定的，请找到一个字典序最小的使用道具的方式，使得最终的防御性能最大。
> 
> 初始时防御性能为0，即d=0，所以A=B=1。
> 
> 【输入格式】  
> 输入的第一行包含两个数n1,n2，空格分隔。  
> 第二行n1个数，表示增加A值的那些道具的增加量。  
> 第三行n2个数，表示增加B值的那些道具的增加量。  
> 第四行一个长度为n1+n2的字符串，由0和1组成，表示道具的使用顺序。0表示使用增加A值的道具，1表示使用增加B值的道具。输入数据保证恰好有n1个0，n2个1。
> 
> 【输出格式】  
> 对于每组数据，输出n1+n2+1行，前n1+n2行按顺序输出道具的使用情况，若使用增加A值的道具，输出Ax，x为道具在该类道具中的编号（从1开始）。若使用增加B值的道具则输出Bx。最后一行输出一个大写字母E。
> 
> 【样例输入1】  
> 1 2  
> 4  
> 2 8  
> 101
> 
> 【样例输出1】  
> B2  
> A1  
> B1  
> E
> 
> 【样例输入2】  
> 3 0  
> 7 11 13
> 
> 000
> 
> 【样例输出2】  
> A1  
> A2  
> A3  
> E
> 
> 【样例说明】  
> 对于第一组测试数据，操作过程如下：  
> 操作  d         A              B  
> 初始  0            1              1  
> B2    2         4              9  
> A1    3            8              27  
> B1   log3(29)   2^(log3(29))   29
> 
> 可以证明，这个值是最大的。  
> 对于第二组测试数据，可见无论用什么顺序，A最后总为32，即d总为5，B总为243。 
> 
> 【数据规模】  
> 对于20%的数据，字符串长度<=10000；  
> 对于70%的数据，字符串长度<=200000；  
> 对于100%的数据，字符串长度<=2000000，输入的每个增加值不超过2^30。
> 
>   
> 资源约定：  
> 峰值内存消耗（含虚拟机） < 256M  
> CPU消耗  < 1000ms
> 
>   
> 请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
> 
> 所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。  
> 不要使用package语句。不要使用jdk1.7及以上版本的特性。  
> 主类的名字必须是：Main，否则按无效代码处理。

> 【解析】：题目要求防御性能最好，  
> 而且AB的先后顺序已经固定，  
> 我们只需要排好A和B两序列内部的排列顺序即可，  
> 对于A序列，对2取log，如果要使最终防御性能最好，  
> 那么就要先使用增益效果最差的道具，把增益效果好的道具放到后边以获得最大涨幅，  
> 对于B序列，对3取log，如果要使最终防御性能最好，  
> 那么就要先使用增益效果最好的道具，以便在初期能获得最大涨幅。

package national_09_2018;
    
    import java.util.Scanner;
    
    public class E06_防御力 {
    
    	public static int n1, n2;
    	public static double arr1[];
    	public static double arr2[];
    	public static int buf1[];
    	public static int buf2[];
    
    	public static void main(String[] args) {
    		Scanner sc = new Scanner(System.in);
    		n1 = sc.nextInt();
    		n2 = sc.nextInt();
    		arr1 = new double[n1]; // arr储存数据，buf做标记
    		arr2 = new double[n2];
    		buf1 = new int[n1];
    		buf2 = new int[n2];
    		sc.nextLine();
    		int x;
    		for (int i = 0; i < arr1.length; i++) {
    			x = sc.nextInt();
    			arr1[i] = Math.log(x) / Math.log(2); // 储存数据对2取log
    		}
    		sc.nextLine();
    		for (int i = 0; i < arr2.length; i++) {
    			x = sc.nextInt();
    			arr2[i] = Math.log(x) / Math.log(3); // 储存数据对3取log
    		}
    		sc.nextLine();
    		String str = sc.nextLine();
    		check(str); // 对数据处理
    	}
    
    	public static void check(String s) { // 每递归一次处理完字符串开头的所有相同字符
    		if (s.length() != 0) { // 字符串长度不为零
    			int x = sub(s); // 处理开头的所有相同字符
    			s = s.substring(x); // 将没有被处理的字符截取下来
    			check(s); // 递归
    		} else {
    			System.out.println("E"); // 字符串长度为零，输出E
    		}
    	}
    
    	public static int sub(String s) {
    		int i = 0;
    		if (s.charAt(0) == '0') { // 如果第一个字符为0
    			while (s.length() > i && s.charAt(i) == '0') // i++，直到遇见不相同字符跳出
    				i++;
    			int ans[] = new int[i]; // 建立小的答案数组，储存前i个答案
    			for (int j = 0; j < i; j++) { // ans指的是答案的下标
    				ans[j] = getmin(); // 循环i次，获取i个答案
    			}
    			int ii = i; // 定义ii控制循环次数
    			while (ii > 0) {
    				ii--;
    				double min = Integer.MAX_VALUE; // 定义最小值
    				int p = -1; // 定义指针，指向ans中最小的值
    				for (int j = 0; j < ans.length; j++) { // 循环ans找min
    					if (arr1[ans[j]] < min) { // 找最小值取代min，p指向新值
    						min = arr1[ans[j]];
    						p = ans[j];
    					}
    				}
    				arr1[p] = Integer.MAX_VALUE; // 将找过的值处理掉
    				p += 1; // p指的下标，p+1指的第几个数
    				System.out.println("A" + p); // 输出一个答案
    			}
    		} else { // 跟上边一样，只是对象变成了第一个字符为1，求最大值
    			while (s.length() > i && s.charAt(i) == '1')
    				i++;
    			int ans[] = new int[i];
    			for (int j = 0; j < i; j++) {
    				ans[j] = getmax();
    			}
    			int ii = i;
    			while (ii > 0) {
    				ii--;
    				double max = -1;
    				int p = -1;
    				for (int j = 0; j < ans.length; j++) {
    					if (arr2[ans[j]] > max) {
    						max = arr2[ans[j]];
    						p = ans[j];
    					}
    				}
    				arr2[p] = -1;
    				p += 1;
    				System.out.println("B" + p);
    			}
    		}
    		return i; // i是处理过的长度，提供给check函数，对字符串剪切
    	}
    
    	public static int getmin() {
    		double x = Integer.MAX_VALUE;
    		int p = -1;
    		for (int i = 0; i < arr1.length; i++) {
    			if (buf1[i] == 0) {
    				if (x > arr1[i]) {
    					x = arr1[i];
    					p = i;
    				}
    			}
    		}
    		buf1[p] = 1;
    		return p;
    	}
    
    	public static int getmax() {
    		double x = -1;
    		int p = -1;
    		for (int i = 0; i < arr2.length; i++) {
    			if (buf2[i] == 0) {
    				if (x < arr2[i]) {
    					x = arr2[i];
    					p = i;
    				}
    			}
    		}
    		buf2[p] = 1;
    		return p;
    	}
    
    }

# 小结 #

> [wyk大佬][wyk]实在太强喇呀！！！多谢carry！！！

[Java B_ _ _2013_4_2020_11]: 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
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk0OTEzNQ_size_16_color_FFFFFF_t_70]: /images/20221120/ecb27ff449744032a496dd4c0cc035a7.png
[Link 2]: https://blog.csdn.net/weixin_46239370/article/details/106220727
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk0OTEzNQ_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20201108192346545.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk0OTEzNQ==,size_16,color_FFFFFF,t_70
[20201108190248364.png]: /images/20221120/2b517aedda47476792060bbd88d7f356.png
[Link 3]: https://blog.csdn.net/qq_43652327/article/details/109408317
[20201108184414866.png]: /images/20221120/ff326df52ea24238b44bf54c46811ec9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk0OTEzNQ_size_16_color_FFFFFF_t_70 2]: /images/20221120/fbad758b23534265ab50d509e8b3c2fb.png
[20201108204924573.png]: /images/20221120/87ab3fbd21f74d3abe45abee76aea0c5.png
[20201108203233316.png]: /images/20221120/baae01b7da504ab2b0701278c8d43fd0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk0OTEzNQ_size_16_color_FFFFFF_t_70 3]: /images/20221120/aefd05131948400092ed933478f2a349.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk0OTEzNQ_size_16_color_FFFFFF_t_70 4]: /images/20221120/d4972fd8e48e4ca8ac81546a3d981319.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk0OTEzNQ_size_16_color_FFFFFF_t_70 5]: /images/20221120/4b26361a146f41d699a5c69b8d99aa12.png
[wyk]: https://blog.csdn.net/qq_43652327