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

怼烎@ 2022-12-19 11:40 173阅读 0赞

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

### 目录 ###

*   *  蓝桥杯历年真题及解析.
     *   *   *  A：分机号（难度：★）.
             *   *  分析：
                 *  AC代码：
             *  B：五星填数（难度：★）.
             *   *  分析：
                 *  AC代码：
             *  C：显示二叉树（难度：★★）.
             *   *  分析：
                 *  AC代码：
             *  D：穿越雷区（难度：★★★）.
             *   *  分析：
                 *  AC代码：
             *  E：表格计算（难度：★★★★）.
             *   *  分析：
                 *  AC代码：
             *  F：铺瓷砖（难度：★★★★★）.
             *   *  分析：
                 *  AC代码：

#### A：分机号（难度：★）. ####

X老板脾气古怪，他们公司的电话分机号都是3位数，老板规定，所有号码必须是降序排列，且不能有重复的数位。比如：

751,520,321 都满足要求，而，  
766,918,201 就不符合要求。

现在请你计算一下，按照这样的规定，一共有多少个可用的3位分机号码？

请直接提交该数字，不要填写任何多余的内容。

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

for循环枚举所有的三位数，  
对每个三位数进行check统计

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

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

public class Main { 
    	public static void main(String[] args) { 
    		int ans=0;
    		for(int i=100;i<1000;i++){ 
    			if(i/100>(i/10)%10&&(i/10)%10>i%10){ 
    				ans++;
    			}
    		}
    		System.out.println(ans);
    	}
    }

#### B：五星填数（难度：★）. ####

如【图1.png】的五星图案节点填上数字：1~12，除去7和11。  
要求每条直线上数字和相等。

如图就是恰当的填法。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70_pic_center]

请你利用计算机搜索所有可能的填法有多少种。  
注意：旋转或镜像后相同的算同一种填法。

请提交表示方案数目的整数，不要填写任何其它内容。

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

典型全排列问题，  
把所有要填写的数据放入全排列的数组  
对数组进行全排列，  
对每次全排列的结果进行check，  
符合条件即ans++；

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

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

import java.util.HashSet;
    
    public class Main { 
    	public static int arr[]={ 1,2,3,4,5,6,8,9,10,12};
    	public static int ans=0;
    	public static void check(){ 
    		HashSet<Integer> set=new HashSet<Integer>();
    		
    		set.add(arr[0]+arr[1]+arr[2]+arr[3]);
    		set.add(arr[3]+arr[4]+arr[5]+arr[6]);
    		set.add(arr[6]+arr[7]+arr[1]+arr[8]);
    		set.add(arr[8]+arr[2]+arr[4]+arr[9]);
    		set.add(arr[9]+arr[5]+arr[7]+arr[0]);
    		if(set.size()==1)ans++;
    	}
    	public static void qpl(int k){ 
    		if(k>=arr.length){ 
    			check();
    		}else{ 
    			for(int i=k;i<arr.length;i++){ 
    				int 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/10);
    	}
    }

#### C：显示二叉树（难度：★★）. ####

排序二叉树的特征是：  
某个节点的左子树的所有节点值都不大于本节点值。  
某个节点的右子树的所有节点值都不小于本节点值。

为了能形象地观察二叉树的建立过程，小明写了一段程序来显示出二叉树的结构来。

class BiTree
    { 
    	private int v;
    	private BiTree l;
    	private BiTree r;
    	
    	public BiTree(int v){ 
    		this.v = v;
    	}
    	
    	public void add(BiTree the){ 
    		if(the.v < v){ 
    			if(l==null) l = the;
    			else l.add(the);
    		}
    		else{ 
    			if(r==null) r = the;
    			else r.add(the);
    		}
    	}
    	
    	public int getHeight(){ 
    		int h = 2;
    		int hl = l==null? 0 : l.getHeight();
    		int hr = r==null? 0 : r.getHeight();
    		return h + Math.max(hl,hr);
    	}
    	
    	public int getWidth(){ 
    		int w = (""+v).length();
    		if(l!=null) w += l.getWidth();
    		if(r!=null) w += r.getWidth();
    		return w;
    	}
    	
    	public void show(){ 
    		char[][] buf = new char[getHeight()][getWidth()];
    		printInBuf(buf, 0, 0);
    		showBuf(buf);
    	}
    	
    	private void showBuf(char[][] x){ 
    		for(int i=0; i<x.length; i++){ 
    			for(int j=0; j<x[i].length; j++)
    				System.out.print(x[i][j]==0? ' ':x[i][j]);
    			System.out.println();
    		}
    	}
    	
    	private void printInBuf(char[][] buf, int x, int y){ 
    		String sv = "" + v;
    		
    		int p1 = l==null? x : l.getRootPos(x);
    		int p2 = getRootPos(x);
    		int p3 = r==null? p2 : r.getRootPos(p2+sv.length());
    		
    		buf[y][p2] = '|';
    		for(int i=p1; i<=p3; i++) buf[y+1][i]='-';
    		for(int i=0; i<sv.length(); i++) ________________________________;  //填空位置
    		if(p1<p2) buf[y+1][p1] = '/';
    		if(p3>p2) buf[y+1][p3] = '\\';
    		
    		if(l!=null) l.printInBuf(buf,x,y+2);
    		if(r!=null) r.printInBuf(buf,p2+sv.length(),y+2);
    	}
    	
    	private int getRootPos(int x){ 
    		return l==null? x : x + l.getWidth();
    	}
    }
    
    public class Main
    { 
    	public static void main(String[] args)
    	{ 		
    		BiTree tree = new BiTree(500);
    		tree.add(new BiTree(200));
    		tree.add(new BiTree(509));
    		tree.add(new BiTree(100));
    		tree.add(new BiTree(250));
    		tree.add(new BiTree(507));
    		tree.add(new BiTree(600));
    		tree.add(new BiTree(650));
    		tree.add(new BiTree(450));
    		tree.add(new BiTree(510));
    		tree.add(new BiTree(440));
    		tree.add(new BiTree(220));		
    		tree.show();		
    	}
    }

对于上边的测试数据，应该显示出：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70_pic_center 1]

请分析程序逻辑，填写划线部分缺失的代码。

注意，只填写缺少的部分，不要填写已有的代码或符号，也不要加任何说明文字。

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

观察代码我们即可发现，buf即为输出的数组，  
注释填空部分，运行发现现在程序仅仅缺少数据，而不缺少基础的结构  
所以我们推测填空部分一定是一个数据V  
数据又和上一行的 | 对齐，  
所以推出buf\[y+1\]\[p2+i\]=String.valueOf(v).charAt(i);

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

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

package JAVA2015;
    
    
    public class C显示二叉树
    { 
    	public static void main(String[] args)
    	{ 		
    		BiTree tree = new BiTree(500);
    		tree.add(new BiTree(200));
    		tree.add(new BiTree(509));
    		tree.add(new BiTree(100));
    		tree.add(new BiTree(250));
    		tree.add(new BiTree(507));
    		tree.add(new BiTree(600));
    		tree.add(new BiTree(650));
    		tree.add(new BiTree(450));
    		tree.add(new BiTree(510));
    		tree.add(new BiTree(440));
    		tree.add(new BiTree(220));		
    		tree.show();		
    	}
    }
    
    class BiTree
    { 
    	private int v;
    	private BiTree l;
    	private BiTree r;
    	
    	public BiTree(int v){ 
    		this.v = v;
    	}
    	
    	public void add(BiTree the){ 
    		if(the.v < v){ 
    			if(l==null) l = the;
    			else l.add(the);
    		}
    		else{ 
    			if(r==null) r = the;
    			else r.add(the);
    		}
    	}
    	
    	public int getHeight(){ 
    		int h = 2;
    		int hl = l==null? 0 : l.getHeight();
    		int hr = r==null? 0 : r.getHeight();
    		return h + Math.max(hl,hr);
    	}
    	
    	public int getWidth(){ 
    		int w = (""+v).length();
    		if(l!=null) w += l.getWidth();
    		if(r!=null) w += r.getWidth();
    		return w;
    	}
    	
    	public void show(){ 
    		char[][] buf = new char[getHeight()][getWidth()];
    		printInBuf(buf, 0, 0);
    		showBuf(buf);
    	}
    	
    	private void showBuf(char[][] x){ 
    		for(int i=0; i<x.length; i++){ 
    			for(int j=0; j<x[i].length; j++)
    				System.out.print(x[i][j]==0? ' ':x[i][j]);
    			System.out.println();
    		}
    	}
    	
    	private void printInBuf(char[][] buf, int x, int y){ 
    		String sv = "" + v;
    		
    		int p1 = l==null? x : l.getRootPos(x);
    		int p2 = getRootPos(x);
    		int p3 = r==null? p2 : r.getRootPos(p2+sv.length());
    		
    		buf[y][p2] = '|';
    		for(int i=p1; i<=p3; i++) buf[y+1][i]='-';
    		for(int i=0; i<sv.length(); i++) 
    			buf[y+1][p2+i]=String.valueOf(v).charAt(i);
    			//________________________________; //填空位置
    		if(p1<p2) buf[y+1][p1] = '/';
    		if(p3>p2) buf[y+1][p3] = '\\';
    		
    		if(l!=null) l.printInBuf(buf,x,y+2);
    		if(r!=null) r.printInBuf(buf,p2+sv.length(),y+2);
    	}
    	
    	private int getRootPos(int x){ 
    		return l==null? x : x + l.getWidth();
    	}
    }

#### D：穿越雷区（难度：★★★）. ####

X星的坦克战车很奇怪，它必须交替地穿越正能量辐射区和负能量辐射区才能保持正常运转，否则将报废。  
某坦克需要从A区到B区去（A，B区本身是安全区，没有正能量或负能量特征），怎样走才能路径最短？

已知的地图是一个方阵，上面用字母标出了A，B区，其它区都标了正号或负号分别表示正负能量辐射区。  
例如：  
![在这里插入图片描述][20201106215923894.png_pic_center]

坦克车只能水平或垂直方向上移动到相邻的区。

数据格式要求：

输入第一行是一个整数n，表示方阵的大小， 4<=n<100  
接下来是n行，每行有n个数据，可能是A，B，+，-中的某一个，中间用空格分开。  
A，B都只出现一次。

要求输出一个整数，表示坦克从A区到B区的最少移动步数。  
如果没有方案，则输出-1  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70_pic_center 2]

资源约定：  
峰值内存消耗（含虚拟机） < 512M  
CPU消耗 < 2000ms

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

所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。  
注意：不要使用package语句。不要使用jdk1.7及以上版本的特性。  
注意：主类的名字必须是：Main，否则按无效代码处理。

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

BFS问题，每次以当前位置为起点，向周围扩散一个移动单位  
每次记录当前位置与当前符号，还有移动步数  
每次改变位置状态与符号状态，步数+1  
定义一个布尔类型的数组标记访问状态，防止重复访问。  
最终第一次到达B点的状态即为最短状态。

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

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

import java.util.HashMap;
    import java.util.Scanner;
    
    public class Main{ 
    	public static boolean buf[][];
    	public static char c[][];
    	public static int n;
    	public static int bfs(HashMap<Integer, Character> list,int step){ 
    		HashMap<Integer, Character> cur=new HashMap<Integer, Character>();
    		int x,y;
    		char flag;
    		boolean ok=false;
    		for(int t:list.keySet()){ 
    			flag=list.get(t);
    			x=t/1000;
    			y=t%1000;
    			buf[x][y]=true;
    			for(int i=-1;i<2;i++){ 
    				for(int j=-1;j<2;j++){ 
    					if(Math.abs(i+j)==1){ 
    						if(x+i>=0&&x+i<n
    								&&y+j>=0&&y+j<n
    								&&buf[x+i][y+j]==false
    								&&c[x+i][y+j]!=flag){ 
    							cur.put((x+i)*1000+y+j,c[x+i][y+j]);
    							if(c[x+i][y+j]=='B')ok=true;
    						}
    					}
    				}
    			}
    		}
    		if(ok)return step;
    		else return bfs(cur, step+1);
    	}
    	public static void main(String[] args) { 
    		Scanner scanner=new Scanner(System.in);
    		n=scanner.nextInt();
    		scanner.nextLine();
    		c=new char [n][n];
    		buf=new boolean[n][n];
    		for(int i=0;i<n;i++){ 
    			String string=scanner.nextLine();
    			string=string.replace(" ", "");
    			c[i]=string.toCharArray();
    		}
    		int ans=0;
    		for(int i=0;i<n;i++){ 
    			for(int j=0;j<n;j++){ 
    				if(c[i][j]=='A'){ 
    					HashMap<Integer, Character> list=new HashMap<Integer, Character>();
    					list.put(i*1000+j, c[i][j]);
    					ans=bfs(list,1);
    				}
    			}
    		}
    		System.out.println(ans);
    	}
    }

#### E：表格计算（难度：★★★★）. ####

某次无聊中， atm 发现了一个很老的程序。这个程序的功能类似于 Excel ，它对一个表格进行操作。  
不妨设表格有 n 行，每行有 m 个格子。  
每个格子的内容可以是一个正整数，也可以是一个公式。  
公式包括三种：

1.  SUM(x1,y1:x2,y2) 表示求左上角是第 x1 行第 y1 个格子，右下角是第 x2 行第 y2 个格子这个矩形内所有格子的值的和。
2.  AVG(x1,y1:x2,y2) 表示求左上角是第 x1 行第 y1 个格子，右下角是第 x2 行第 y2 个格子这个矩形内所有格子的值的平均数。
3.  STD(x1,y1:x2,y2) 表示求左上角是第 x1 行第 y1 个格子，右下角是第 x2 行第 y2 个格子这个矩形内所有格子的值的标准差。

标准差即为方差的平方根。  
方差就是：每个数据与平均值的差的平方的平均值，用来衡量单个数据离开平均数的程度。

公式都不会出现嵌套。

如果这个格子内是一个数，则这个格子的值等于这个数，否则这个格子的值等于格子公式求值结果。

输入这个表格后，程序会输出每个格子的值。atm 觉得这个程序很好玩，他也想实现一下这个程序。

「输入格式」  
第一行两个数 n, m 。  
接下来 n 行输入一个表格。每行 m 个由空格隔开的字符串，分别表示对应格子的内容。  
输入保证不会出现循环依赖的情况，即不会出现两个格子 a 和 b 使得 a 的值依赖 b 的值且 b 的值依赖 a 的值。

「输出格式」  
输出一个表格，共 n 行，每行 m 个保留两位小数的实数。  
数据保证不会有格子的值超过 1e6 。

「样例输入」  
3 2  
1 SUM(2,1:3,1)  
2 AVG(1,1:1,2)  
SUM(1,1:2,1) STD(1,1:2,2)

「样例输出」  
1.00 5.00  
2.00 3.00  
3.00 1.48

「数据范围」  
对于 30% 的数据，满足： n, m <= 5  
对于 100% 的数据，满足： n, m <= 50

资源约定：  
峰值内存消耗（含虚拟机） < 512M  
CPU消耗 < 2000ms

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

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

我们循环遍历表格，当发现有未知函数状态，即计算当前函数，当函数内存在另一个函数时，DFS执行计算新的函数，一直深搜下去即可。

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

我努力了，但还是只能通过80%的数据  
![在这里插入图片描述][20201106220518707.png_pic_center]

import java.util.Scanner;
    
    public class Main{ 
    	public static double ans[][];
    
    	public static int[] comput(String str) { 
    		int arr[] = new int[4];
    		str = str.substring(4);
    		arr[0] = Integer.valueOf(str.substring(0, str.indexOf(',')));
    		str = str.substring(str.indexOf(',') + 1);
    		arr[1] = Integer.valueOf(str.substring(0, str.indexOf(':')));
    		str = str.substring(str.indexOf(':') + 1);
    		arr[2] = Integer.valueOf(str.substring(0, str.indexOf(',')));
    		str = str.substring(str.indexOf(',') + 1);
    		arr[3] = Integer.valueOf(str.substring(0, str.indexOf(')')));
    		return arr;
    	}
    
    	public static double totry(String s[][], String str) { 
    		double fin = 0;
    		int xy[] = comput(str);
    		double sum = 0;
    		double avg = 0;
    		double std = 0;
    		int cnt = 0;
    		for (int i = xy[0] - 1; i < xy[2]; i++) { 
    			for (int j = xy[1] - 1; j < xy[3]; j++) { 
    				if (ans[i][j] == 0) { 
    					ans[i][j] = totry(s, s[i][j]);
    				}
    				sum += ans[i][j];
    				cnt++;
    			}
    		}
    		avg = sum / cnt;
    		for (int i = xy[0] - 1; i < xy[2]; i++) { 
    			for (int j = xy[1] - 1; j < xy[3]; j++) { 
    				std += (ans[i][j] - avg) * (ans[i][j] - avg);
    			}
    		}
    		std /= cnt;
    		std = Math.sqrt(std);
    		if (str.contains("SUM")) { 
    			fin = sum;
    		} else if (str.contains("AVG")) { 
    			fin = avg;
    		} else if (str.contains("STD")) { 
    			fin = std;
    		}
    		return fin;
    	}
    
    	public static void check(String s[][]) { 
    		for (int i = 0; i < s.length; i++) { 
    			for (int j = 0; j < s[i].length; j++) { 
    				if (ans[i][j] > 0)
    					continue;
    				else
    					ans[i][j] = totry(s, s[i][j]);
    			}
    		}
    	}
    
    	public static void main(String[] args) { 
    		Scanner scanner = new Scanner(System.in);
    		int n = scanner.nextInt(), m = scanner.nextInt();
    		String s[][] = new String[n][m];
    		ans = new double[n][m];
    		for (int i = 0; i < n; i++) { 
    			for (int j = 0; j < m; j++) { 
    				s[i][j] = scanner.next();
    				if (s[i][j].length() < 9) { 
    					ans[i][j] = Double.parseDouble(s[i][j]);
    				}
    			}
    		}
    		check(s);
    		for (int i = 0; i < n; i++) { 
    			for (int j = 0; j < m; j++) { 
    				System.out.print(String.format("%.2f", ans[i][j]) + (j + 1 == m ? "" : " "));
    			}
    			System.out.println();
    		}
    	}
    }

#### F：铺瓷砖（难度：★★★★★）. ####

为了让蓝桥杯竞赛更顺利的进行，主办方决定给竞赛的机房重新铺放瓷砖。机房可以看成一个n\*m的矩形，而这次使用的瓷砖比较特别，有两种形状，如【图1.png】所示。在铺放瓷砖时，可以旋转。  
![在这里插入图片描述][20201106220702262.png_pic_center]

主办方想知道，如果使用这两种瓷砖把机房铺满，有多少种方案。

【输入格式】  
输入的第一行包含两个整数，分别表示机房两个方向的长度。

【输出格式】  
输出一个整数，表示可行的方案数。这个数可能很大，请输出这个数除以65521的余数。

【样例输入1】  
4 4  
【样例输出1】  
2  
【样例说明1】  
这两种方案如下【图2.png】所示：  
![在这里插入图片描述][20201106220732656.png_pic_center]

【样例输入2】  
2 6  
【样例输出2】  
4  
【数据规模与约定】  
对于20%的数据，1<=n, m<=5。  
对于50%的数据，1<=n<=100，1<=m<=5。  
对于100%的数据，1<=n<=10^15，1<=m<=6。

资源约定：  
峰值内存消耗（含虚拟机） < 512M  
CPU消耗 < 8000ms

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

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

需要将在状态压缩的动态规划中去除无用状态，然后建立矩阵表示，使用矩阵乘法的方法来实现状态压缩中的递推，待更新  
以后忘了记得催我。。。。

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

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

[Link 1]: https://blog.csdn.net/qq_43652327/article/details/104899994
[20201106214355793.png_pic_center]: /images/20221120/895f8582d045448892b30e4ecb9538c2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/c8e7b9612f894a2692705932badea2ec.png
[20201106214707287.png_pic_center]: /images/20221120/e0670cf5c91f485cbe4a90f9c211d201.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221120/e4173f38cd844c51b915729eb7531f1b.png
[20201106215923894.png_pic_center]: /images/20221120/7f4b015260a1493f899996b757a2e36b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221120/729988196ac84494b220d88fc1a2954d.png
[20201106220146351.png_pic_center]: /images/20221120/78fcc4b2dbcd45e9bf0bf4c4c57d2bcd.png
[20201106220518707.png_pic_center]: /images/20221120/e0d0619f539348e9acba10d09b02a2f6.png
[20201106220702262.png_pic_center]: /images/20221120/41624366771a4ba1b3bb7f05c5240dd3.png
[20201106220732656.png_pic_center]: /images/20221120/b7c7f820d448474bb687068b6fba0b13.png
[20201031221138562.png_pic_center]: /images/20221120/fe7fca695602495b8485367e5a5e3ea1.png