devbox
知新_RL
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

2018年第九届蓝桥杯国赛试题及详解（Java本科B组）_18年蓝桥杯

作者：知新_RL | 2024-04-30 02:30:02

赞

踩

18年蓝桥杯

蓝桥杯历年真题题目及题解目录汇总 

 

  1. 结果填空 (满分13分)
  2. 结果填空 (满分39分)
  3. 代码填空 (满分27分)
  4. 程序设计（满分45分）
  5. 程序设计（满分71分）
  6. 程序设计（满分105分）

 


1.标题：三角形面积

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

求该三角形的面积。

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

稳就行，答案：8.795

  1. public class _01_三角形面积 {
  2. //	(2.3, 2.5)
  3. //	(6.4, 3.1)
  4. //	(5.1, 7.2)
  5. 	public static void main(String[] args) {
  6. 		double x1=2.3,y1=2.5,x2=6.4,y2=3.1,x3=5.1,y3=7.2;
  7. 		//double x1=0,y1=0,x2=0,y2=1,x3=1,y3=0;
  8. 		double X1=x2-x1,Y1=y2-y1,X2=x3-x1,Y2=y3-y1;
  9. 		
  10. 		System.out.println((X1*Y2-X2*Y1)/2);
  11. 	}
  12.  
  13. }


2.标题：最大乘积

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

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

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

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

答案：839542176，写烂了的全排

  1. public class _02_最大乘积 {
  2.  
  3. 	public static void main(String[] args) {
  4. 		dfs(0);
  5. 		System.out.println(ans);
  6. 	}
  7. 	
  8. 	static int[] a = new int[] {1,2,3,4,5,6,7,8,9};
  9. 	static int ans=0;
  10. 	static void dfs(int m) {
  11. 		if(m>=9) {
  12. 			for(int i=1;i<=8;i++) {
  13. 				int x=0,y=0;
  14. 				for(int j=0;j<i;j++)
  15. 					x = 10*x+a[j];
  16. 				for(int k=i;k<9;k++)
  17. 					y = 10*y+a[k];
  18. 				
  19. 				
  20. 				int res = x*y;
  21. 				int[] cnt = new int[10];
  22. 				while(res>0) {
  23. 					cnt[res%10]++;
  24. 					res/=10;
  25. 				}
  26. 				boolean flag = true;
  27. 				for(int k=1;k<=9;k++)
  28. 					if(cnt[k]!=1) {
  29. 						flag = false;
  30. 						break;
  31. 					}
  32. 				
  33. 				if(flag) {
  34. 				ans = Math.max(x*y, ans);
  35. 				if(x*y==ans)
  36. 					System.out.println(x+" * "+y+" == "+ans);
  37. 				}
  38. 			}
  39. 			return;
  40. 		}
  41. 		
  42. 		for(int i=m;i<9;i++) {
  43. 			swap(i,m);
  44. 			dfs(m+1);
  45. 			swap(i,m);
  46. 		}
  47. 		
  48. 	}
  49. 	
  50. 	static void swap(int i,int j) {
  51. 		int t = a[i];
  52. 		a[i] = a[j];
  53. 		a[j] = t;
  54. 	}
  55.  
  56. }


3.标题：全排列

对于某个串，比如：“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个，再递归处理

  1. import java.util.*;
  2. public class A
  3. {
  4. 	static void permu(char[] data, int cur){
  5. 		if(cur==data.length-1){
  6. 			System.out.println(new String(data));
  7. 			return;
  8. 		}
  9. 		
  10. 		for(int i=cur; i<data.length; i++){
  11. 			char tmp = data[i]; 
  12. 			for(int j=i-1; j>=cur; j--) data[j+1] = data[j];
  13. 			data[cur] = tmp;			
  14.  
  15. 			permu(data, cur+1);			
  16.  
  17. 			tmp = data[cur]; 
  18. 			__________________________________________ ;
  19. 			data[i] = tmp;			
  20. 		}
  21. 	}
  22. 	
  23. 	static void permu(String x){
  24. 		permu(x.toCharArray(),0);
  25. 	}
  26. 	
  27. 	public static void main(String[] args){
  28. 		permu("1234");
  29. 	}
  30. }


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

答案：for(int j=cur; j<i; j++) data[j] = data[j+1];

花样太多了，填个空都要填这么复杂的，从三目运算升级到填for循环？？不过思路还是确定的，那个地方就是要回溯

 

 


4.标题：整理玩具

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

常规的搜索题，记录全局的0-9的个数，每次搜索和全局的比较，还可以提前优化剪枝，不过数据规模才10*10，瞎搜也一样，时间充裕的话，自己出多几个样例验证

  1. import java.util.Scanner;
  2.  
  3. public class _04_整理玩具 {
  4.  
  5. 	public static void main(String[] args) {
  6. 		Scanner in = new Scanner(System.in);
  7. 		int T = in.nextInt();
  8. 		while(T-->0) {
  9. 			n = in.nextInt();
  10. 			m = in.nextInt();
  11. 			cur = new int[15];
  12. 			cnt = new int[15];
  13. 			ch = new char[n+5][m+5];
  14. 			vis = new int[n+5][m+5];
  15. 			for(int i=0;i<n;i++)
  16. 				ch[i] = in.next().toCharArray();
  17. 			for(int i=0;i<n;i++)
  18. 				for(int j=0;j<m;j++)
  19. 					cur[ch[i][j]-'0']++;
  20. 			boolean flag = getAns();
  21. 			if(flag)
  22. 				System.out.println("YES");
  23. 			else
  24. 				System.out.println("NO");
  25. 		}
  26.  
  27. 	}
  28. 	
  29. 	static char[][] ch;
  30. 	static int n,m,mx,my;
  31. 	static int[] cur;//记录图中0-9出现的个数
  32. 	static int[] cnt;//记录搜索中出现0-9的个数
  33. 	static int[] dx = new int[] {1,0,-1,0};
  34. 	static int[] dy = new int[] {0,1,0,-1};
  35. 	static int[][] vis;
  36. 	
  37. 	static void dfs(int x,int y,int t) {
  38. 		mx = Math.max(mx, x);
  39. 		my = Math.max(my, y);
  40.  
  41. 		vis[x][y] = t;
  42. 		cnt[ch[x][y]-'0']++;
  43. 		for(int i=0;i<4;i++) {
  44. 			int u = x+dx[i];
  45. 			int v = y+dy[i];
  46. 			if(u>=0 && u<n && v>=0 && v<m && vis[u][v]==0 && ch[u][v]==ch[x][y])
  47. 				dfs(u,v,t);
  48. 		}
  49. 	}
  50. 	
  51. 	static boolean getAns() {
  52. 		int t=0;
  53. 		for(int i=0;i<n;i++)
  54. 			for(int j=0;j<m;j++)
  55. 				if(cnt[ch[i][j]-'0']==0) {//可以设个变量t = ch[i][j]-'0',更好书写
  56. 					mx=my=-1;
  57. 					dfs(i,j,++t);
  58. 					if(cnt[ch[i][j]-'0']!=cur[ch[i][j]-'0'])
  59. 						return false;
  60. 					
  61. 					for(int ii=i;ii<=mx;ii++)//判断是否矩形,mx,my记录右下角
  62. 						for(int jj=j;jj<=my;jj++)
  63. 							if(vis[ii][jj]!=vis[i][j])
  64. 								return false;
  65. 				}
  66. 		
  67. 		return true;
  68. 	}
  69. 	
  70. 	
  71. }


5.标题：版本分支

小明负责维护公司一个奇怪的项目。这个项目的代码一直在不断分支(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，否则按无效代码处理。

先贴个退化的并查集混个30%分保平安 

  1. import java.util.Scanner;
  2.  
  3. public class _05_版本分支 {
  4.  
  5. 	public static void main(String[] args) {
  6. 		Scanner in = new Scanner(System.in);
  7. 		int n = in.nextInt();
  8. 		int q = in.nextInt();
  9. 		for(int i=1;i<=100000;i++)
  10. 			f[i] = i;
  11. 		for(int i=1;i<=n-1;i++) {
  12. 			int x = in.nextInt();
  13. 			int y = in.nextInt();
  14. 			f[y] = x;
  15. 		}
  16. 		while(q-->0) {
  17. 			int x = in.nextInt();
  18. 			int y = in.nextInt();
  19. 			boolean flag = false;
  20. 			while(f[y]!=y) {
  21. 				if(f[y]==x) {
  22. 					flag = true;
  23. 					break;
  24. 				}
  25. 				y = f[y];
  26. 			}
  27. 			
  28. 			if(flag || x==y)
  29. 				System.out.println("YES");
  30. 			else
  31. 				System.out.println("NO");
  32. 		}
  33. 		
  34. 	}
  35. 	
  36. 	
  37. 	static int[] f = new int[100005];
  38. 	
  39. 	static int find(int x) {
  40. 		if(f[x]==x)
  41. 			return x;
  42. 		return find(f[x]);
  43. 	}
  44. 	
  45. 	static void union(int x,int y) {
  46. 		int a = f[x];
  47. 		int b = f[y];
  48. 		if(a!=b) 
  49. 			f[b] = a;
  50. 	}
  51.  
  52. }


6.标题：防御力

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

 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/知新_RL/article/detail/511030
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号