2018第九届蓝桥杯国赛JAVA B组真题解析（带源码及解析）

逃离我推掉我的手 2022-11-21 11:21 144阅读 0赞

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

### 目录 ###

*   *  蓝桥杯历年真题及解析.
     *   *   *  A：三角形面积（难度：★）.
             *   *  分析：
                 *  AC代码：
             *  B：最大乘积（难度：★★）.
             *   *  分析：
                 *  AC代码：
             *  C：全排列（难度：★）.
             *   *  分析：
                 *  AC代码：
             *  D：整理玩具（难度：★★★）.
             *   *  分析：
                 *  AC代码：
             *  E：版本分支（难度：★★★★）.
             *   *  分析：
                 *  AC代码：
             *  F：防御力（难度：★★★★★）.
             *   *  分析：
                 *  AC代码：

#### A：三角形面积（难度：★）. ####

已知三角形三个顶点在直角坐标系下的坐标分别为：  
(2.3, 2.5)  
(6.4, 3.1)  
(5.1, 7.2)

求该三角形的面积。

注意，要提交的是一个小数形式表示的浮点数。  
要求精确到小数后3位，如不足3位，需要补零。

##### 分析： #####

直接带入海伦公式即可，  
p=(a+b+c)/2;  
ans=sqrt(p(p-a)(p-b)(p-c));

##### AC代码： #####

![在这里插入图片描述][20201031214048426.png_pic_center]

public class Main { 
    	public static void main(String[] args) { 
    		double a=Math.sqrt((6.4-2.3)*(6.4-2.3)+(3.1-2.5)*(3.1-2.5));
    		double b=Math.sqrt((6.4-5.1)*(6.4-5.1)+(3.1-7.2)*(3.1-7.2));
    		double c=Math.sqrt((5.1-2.3)*(5.1-2.3)+(7.2-2.5)*(7.2-2.5));
    		double p=(a+b+c)/2;
    		System.out.println(String.format("%.3f", Math.sqrt(p*(p-a)*(p-b)*(p-c))));
    	}
    }

#### B：最大乘积（难度：★★）. ####

把 1~9 这9个数字分成两组，中间插入乘号，  
有的时候，它们的乘积也只包含1~9这9个数字，而且每个数字只出现1次。

比如：  
984672 \* 351 = 345619872  
98751 \* 3462 = 341875962  
9 \* 87146325 = 784316925  
…

符合这种规律的算式还有很多，请你计算在所有这些算式中，乘积最大是多少？

注意，需要提交的是一个整数，表示那个最大的积，不要填写任何多余的内容。  
（只提交乘积，不要提交整个算式）

##### 分析： #####

全排列出九个数字的所有排列顺序  
对每一种排列进行枚举分割成两部分  
对两部分的乘积取结果  
检查乘积结果是否符合条件  
如果符合条件即更新全局变量ans

##### AC代码： #####

![在这里插入图片描述][20201031214439787.png_pic_center]

import java.util.HashSet;
    //求最大值，不是求符合条件的种数
    public class Main{ 
    	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);
    	}
    }

#### C：全排列（难度：★）. ####

对于某个串，比如：“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");
    	}
    }

请注意：只需要填写划线部分缺少的内容，不要抄写已有的代码或符号。

##### 分析： #####

观察题目发现是个全排列问题，  
填空部分是全排列的回溯部分  
只需要根据函数体内上半部分交换的原则重新进行回溯回去即可。

##### AC代码： #####

不能交题，但是运行结果是正确的

public class Main { 
    	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");
    	}
    }

#### D：整理玩具（难度：★★★）. ####

小明有一套玩具，一共包含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，否则按无效代码处理。

##### 分析： #####

由题目可以确定数字相同的玩具放在了一起，  
所以我们可以定义一个数组用来存放当前数据的信息，  
我们采用二维数组，  
每一行代表当前编号玩具的信息  
第一列表示当前编号玩具的占地面积  
第二列表示当前编号玩具的占地右下角的横坐标  
第三列表示当前编号玩具的占地右下角的纵坐标  
第四列表示当前编号玩具的占地左上角的横坐标  
第五列表示当前编号玩具的占地左上角的纵坐标  
所以应该有

\-> buf\[i\]\[0\]!=0&&buf\[i\]\[0\]!=(buf\[i\]\[1\]-buf\[i\]\[3\]+1)\*(buf\[i\]\[2\]-buf\[i\]\[4\]+1)

恒成立。

##### AC代码： #####

![在这里插入图片描述][20201031215546646.png_pic_center]

import java.util.Scanner;
    
    public class Main { 
    	
    	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");
    		}
    	}
    }

#### E：版本分支（难度：★★★★）. ####

小明负责维护公司一个奇怪的项目。这个项目的代码一直在不断分支(branch)但是从未发生过合并(merge)。  
现在这个项目的代码一共有N个版本，编号1~N，其中1号版本是最初的版本。  
除了1号版本之外，其他版本的代码都恰好有一个直接的父版本；即这N个版本形成了一棵以1为根的树形结构。

如下图就是一个可能的版本树：  
![在这里插入图片描述][20201031215718665.png_pic_center]

现在小明需要经常检查版本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

请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。

##### 分析： #####

我才用并查集的思路，  
用一个数组储存该节点的父节点，  
当询问祖先关系是，向上查找父节点，  
时间复杂度较高  
通过数据50%

##### AC代码： #####

![在这里插入图片描述][20201031215938706.png_pic_center]  
![在这里插入图片描述][20201031220025356.png_pic_center]

import java.util.*;
    
    public class Main { 
    	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");
    		}
    
    	}
    }

#### F：防御力（难度：★★★★★）. ####

小明最近在玩一款游戏。对游戏中的防御力很感兴趣。  
我们认为直接影响防御的参数为“防御性能”，记作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

请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。

##### 分析： #####

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

##### AC代码： #####

![在这里插入图片描述][20201031220325442.png_pic_center]

import java.util.Scanner;
    
    public class Main{ 
    	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;
    	}
    }

![在这里插入图片描述][20201031221138562.png_pic_center]

[Link 1]: https://blog.csdn.net/qq_43652327/article/details/104899994
[20201031214048426.png_pic_center]: /images/20221120/ed679cbf63c34a4ea201b6d7e0e70f88.png
[20201031214439787.png_pic_center]: /images/20221120/2805dc59fb11487d90581e2f425cf4a5.png
[20201031215546646.png_pic_center]: /images/20221120/2f549c3844bc468a85dfb4b939428a87.png
[20201031215718665.png_pic_center]: /images/20221120/83e16fe8c387452b82766a83d2770911.png
[20201031215938706.png_pic_center]: /images/20221120/0e6f3ee3ec544695b1aa0bd230702354.png
[20201031220025356.png_pic_center]: /images/20221120/038e570903d0439387939f136dd2b6be.png
[20201031220325442.png_pic_center]: /images/20221120/060893c8a4474c1ab282d059e42b5d95.png
[20201031221138562.png_pic_center]: https://img-blog.csdnimg.cn/20201031221138562.png#pic_center