2017蓝桥杯省赛JavaB组部分题目及解答

左手的ㄟ右手 2022-11-30 12:40 233阅读 0赞

# 第二题 #

标题：纸牌三角形

A,2,3,4,5,6,7,8,9 共9张纸牌排成一个正三角形（A按1计算）。要求每个边的和相等。  
下图就是一种排法（如有对齐问题，参看p1.png）。  
![在这里插入图片描述][20200824153223539.png_pic_center]

这样的排法可能会有很多。

如果考虑旋转、镜像后相同的算同一种，一共有多少种不同的排法呢？

public class _02纸牌三角形 { 
    
    	static int ans;
    	
    	public static void main(String[] args) { 
    		int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9};
    		ans = f(arr, 0);
    		System.out.println(ans/6);//镜像加旋转共6种情况
    	}
    
    	private static int f(int[] arr, int k) { 
    		if(k == 9) { 
    			if(check(arr)) { 
    				ans++;
    				return ans;
    			}
    		}
    		
    		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;
    		}
    		return ans;
    	}
    
    	private static boolean check(int[] arr) { 
    		if(arr[0]+arr[1]+arr[3]+arr[5] == arr[0]+arr[2]+arr[4]+arr[8] &&
    				arr[0]+arr[1]+arr[3]+arr[5] == arr[5]+arr[6]+arr[7]+arr[8])
    			return true;
    		return false;
    	}
    }

# 第三题 #

标题：承压计算

X星球的高科技实验室中整齐地堆放着某批珍贵金属原料。

每块金属原料的外形、尺寸完全一致，但重量不同。  
金属材料被严格地堆放成金字塔形。

7  
5 8  
7 8 8  
9 2 7 2  
8 1 4 9 1  
8 1 8 8 4 1  
7 9 6 1 4 5 4  
5 6 5 5 6 9 5 6  
5 5 4 7 9 3 5 5 1  
7 5 7 9 7 4 7 3 3 1  
4 6 4 5 5 8 8 3 2 4 3  
1 1 3 3 1 6 6 5 5 4 4 2  
9 9 9 2 1 9 1 9 2 9 5 7 9  
4 3 3 7 7 9 3 6 1 3 8 8 3 7  
3 6 8 1 5 3 9 5 8 3 8 1 8 3 3  
8 3 2 3 3 5 5 8 5 4 2 8 6 7 6 9  
8 1 8 1 8 4 6 2 2 1 7 9 4 2 3 3 4  
2 8 4 2 2 9 9 2 8 3 4 9 6 3 9 4 6 9  
7 9 7 4 9 7 6 6 2 8 9 4 1 8 1 7 2 1 6  
9 2 8 6 4 2 7 9 5 4 1 2 5 1 7 3 9 8 3 3  
5 2 1 6 7 9 3 2 8 9 5 5 6 6 6 2 1 8 7 9 9  
6 7 1 8 8 7 5 3 6 5 4 7 3 4 6 7 8 1 3 2 7 4  
2 2 6 3 5 3 4 9 2 4 5 7 6 6 3 2 7 2 4 8 5 5 4  
7 4 4 5 8 3 3 8 1 8 6 3 2 1 6 2 6 4 6 3 8 2 9 6  
1 2 4 1 3 3 5 3 4 9 6 3 8 6 5 9 1 5 3 2 6 8 8 5 3  
2 2 7 9 3 3 2 8 6 9 8 4 4 9 5 8 2 6 3 4 8 4 9 3 8 8  
7 7 7 9 7 5 2 7 9 2 5 1 9 2 6 5 3 9 3 5 7 3 5 4 2 8 9  
7 7 6 6 8 7 5 5 8 2 4 7 7 4 7 2 6 9 2 1 8 2 9 8 5 7 3 6  
5 9 4 5 5 7 5 5 6 3 5 3 9 5 8 9 5 4 1 2 6 1 4 3 5 3 2 4 1  
X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X

其中的数字代表金属块的重量（计量单位较大）。  
最下一层的X代表30台极高精度的电子秤。

假设每块原料的重量都十分精确地平均落在下方的两个金属块上，  
最后，所有的金属块的重量都严格精确地平分落在最底层的电子秤上。  
电子秤的计量单位很小，所以显示的数字很大。

工作人员发现，其中读数最小的电子秤的示数为：2086458231

请你推算出：读数最大的电子秤的示数为多少？

//注意单位问题
    public class _03承压计算 { 
    
    	static long[][] arr = new long[30][30];
    	static long factor = 1;
    	public static void main(String[] args) { 
    		Scanner sc = new Scanner(System.in);
    		//将factor赋值为2^29，经验算，输入值与最后一行电子秤的值的单位之间差了2^29
    		for(int i = 1; i < 30; i++) { 
    			factor <<= 1;//位运算，左移一位相当于乘2
    		}
    		for(int i = 0; i < 29; i++) { 
    			for(int j = 0; j <= i; j++) { 
    				arr[i][j] = sc.nextLong()*factor;
    			}
    		}
    		for(int i = 0; i < 29; i++) { 
    			for(int j = 0; j <= i; j++) { 
    				long half = arr[i][j]/2;
    				arr[i+1][j] += half;
    				arr[i+1][j+1] += half;
    			}
    		}
    		Arrays.sort(arr[29]);
    		System.out.println(arr[29][29]);//输出最后一行最大值
    	}
    }

# 第五题 #

标题：取数位

求1个整数的第k位数字有很多种方法。  
以下的方法就是一种。

public class Main  
\{  
static int len(int x)\{  
if(x<10) return 1;  
return len(x/10)+1;  
\}

// 取x的第k位数字
    static int f(int x, int k){
    	if(len(x)-k==0) return x%10;
    	return ______________________;  //填空
    }
    
    public static void main(String[] args)
    {
    	int x = 23513;
    	//System.out.println(len(x));
    	System.out.println(f(x,3));
    }

对于题目中的测试数据，应该打印5。

请仔细分析源码，并补充划线部分所缺少的代码。

public class _05取数位 { 
    
    	public static void main(String[] args) { 
    		int x = 23513;
    		//System.out.println(len(x));
    		System.out.println(f(x,3));
    	}
    	static int len(int x){ 
    		if(x<10) return 1;
    		return len(x/10)+1;
    	}
    	
    	// 取x的第k位数字 ,从左到右数
    	static int f(int x, int k){ 
    		if(len(x)-k==0) return x%10;
    		return f(x/10, k);  //填空
    	}
    }

# 第六题 #

标题：最大公共子串

最大公共子串长度问题就是：  
求两个串的所有子串中能够匹配上的最大长度是多少。

比如：“abcdkkk” 和 “baabcdadabc”，  
可以找到的最长的公共子串是"abcd",所以最大公共子串长度为4。

下面的程序是采用矩阵法进行求解的，这对串的规模不大的情况还是比较有效的解法。

请分析该解法的思路，并补全划线部分缺失的代码。

public class Main  
\{  
static int f(String s1, String s2)  
\{  
char\[\] c1 = s1.toCharArray();  
char\[\] c2 = s2.toCharArray();

int[][] a = new int[c1.length+1][c2.length+1];
    	
    	int max = 0;
    	for(int i=1; i<a.length; i++){
    		for(int j=1; j<a[i].length; j++){
    			if(c1[i-1]==c2[j-1]) {
    				a[i][j] = __________________;  //填空 
    				if(a[i][j] > max) max = a[i][j];
    			}
    		}
    	}
    	
    	return max;
    }
    
    public static void main(String[] args){
    	int n = f("abcdkkk", "baabcdadabc");
    	System.out.println(n);
    }

public class _06最长公共子串 { 
    	static int f(String s1, String s2)
    	{ 
    		char[] c1 = s1.toCharArray();
    		char[] c2 = s2.toCharArray();
    		
    		int[][] a = new int[c1.length+1][c2.length+1];
    		
    		int max = 0;
    		for(int i=1; i<a.length; i++){ 
    			for(int j=1; j<a[i].length; j++){ 
    				if(c1[i-1]==c2[j-1]) { 
    					a[i][j] = a[i-1][j-1]+1;  //填空 ，联系动态规划
    					if(a[i][j] > max) max = a[i][j];
    				}
    			}
    		}
    		
    		return max;
    	}
    	public static void main(String[] args) { 
    		int n = f("abcdkkk", "baabcdadabc");
    		System.out.println(n);
    	}
    }

# 第七题 #

标题：日期问题

小明正在整理一批历史文献。这些历史文献中出现了很多日期。小明知道这些日期都在1960年1月1日至2059年12月31日。令小明头疼的是，这些日期采用的格式非常不统一，有采用年/月/日的，有采用月/日/年的，还有采用日/月/年的。更加麻烦的是，年份也都省略了前两位，使得文献上的一个日期，存在很多可能的日期与其对应。

比如02/03/04，可能是2002年03月04日、2004年02月03日或2004年03月02日。

给出一个文献上的日期，你能帮助小明判断有哪些可能的日期对其对应吗？

输入一个日期，格式是"AA/BB/CC"。 (0 <= A, B, C <= 9)

输出若干个不相同的日期，每个日期一行，格式是"yyyy-MM-dd"。多个日期按从早到晚排列。  
样例输入  
02/03/04

样例输出  
2002-03-04  
2004-02-03  
2004-03-02

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

public class _07日期问题 { 
    	public static void main(String[] args) { 
    		Scanner sc = new Scanner(System.in);
    		String date = sc.nextLine();
    		int a = Integer.parseInt(date.substring(0, 2));
    		int b = Integer.parseInt(date.substring(3, 5));
    		int c = Integer.parseInt(date.substring(6));
    		String case1 = f(a, b, c);// 年/月/日
    		String case2 = f(c, b, a);// 月/日/年
    		String case3 = f(c, a, b);// 日/月/年
    		Set<String> set = new TreeSet<String>();
    		if(case1 != "")
    			set.add(case1);
    		if(case2 != "")
    			set.add(case2);
    		if(case3 != "")
    			set.add(case3);
    		for(String str : set) { 
    			System.out.println(str);
    		}
    		
    	}
    
    	private static String f(int a, int b, int c) { 
    		//判断年份
    		if(a>=0 && a <= 59)
    			a+=2000;
    		else if(a>=60 && a <= 99)
    			a+=1900;
    		else
    			return "";
    		//判断月份
    		boolean isLeap = isLeap(a);
    		if(b < 1 || b > 12)//月份不合法
    			return "";
    		if(c < 1 || c > 31)//日不合法
    			return "";
    		
    		String _a = a + "";
    		String _b;
    		if(b < 10)
    			_b = "0"+b;
    		else
    			_b = ""+b;
    		switch(b) { 
    		case 2:
    			if(isLeap && c > 29) return "";
    			if(!isLeap && c > 28) return "";
    			break;
    		case 4:
    			if(c > 30) return "";
    			break;
    		case 6:
    			if(c > 30) return "";
    			break;
    		case 9:
    			if(c > 30) return "";
    			break;
    		case 11:
    			if(c > 30) return "";
    			break;	
    		}
    		String _c;
    		if(c < 10)
    			_c = "0"+c;
    		else
    			_c = ""+c;
    		return _a+"-"+ _b +"-"+_c; 
    	}
    
    	//判断是否闰年
    	private static boolean isLeap(int a) { 
    		return ((a%4 == 0 && a%100 != 0)|| (a%400 == 0));
    	}
    }

# 第九题 #

标题： 分巧克力

儿童节那天有K位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。
    小明一共有N块巧克力，其中第i块是Hi x Wi的方格组成的长方形。
    
    为了公平起见，小明需要从这 N 块巧克力中切出K块巧克力分给小朋友们。切出的巧克力需要满足：
    
    1. 形状是正方形，边长是整数  
    2. 大小相同

例如一块6x5的巧克力可以切出6块2x2的巧克力或者2块3x3的巧克力。

当然小朋友们都希望得到的巧克力尽可能大，你能帮小Hi计算出最大的边长是多少么？

输入  
第一行包含两个整数N和K。(1 <= N, K <= 100000)  
以下N行每行包含两个整数Hi和Wi。(1 <= Hi, Wi <= 100000)  
输入保证每位小朋友至少能获得一块1x1的巧克力。

public class _09分巧克力 { 
    	public static void main(String[] args) { 
    		int n,k;
    		int[] h = new int[100000];
    		int[] w = new int[100000];
    		Scanner sc = new Scanner(System.in);
    		n = sc.nextInt();
    		k = sc.nextInt();
    		for(int i = 0; i < n; i++) { 
    			h[i] = sc.nextInt();
    			w[i] = sc.nextInt();
    		}
    		int r = 100001;
    		int l = 1;
    		int ans = 0;
    		while(l <= r) { 
    			int mid = (l + r)/2;
    			int cnt = 0;
    			for(int i = 0; i < n; i++) { 
    				cnt += (h[i]/mid)*(w[i]/mid);
    			}
    			if(cnt >= k) { 
    				l = mid + 1;
    				ans = mid;
    			}else { 
    				r = mid - 1;
    			}
    		}
    		System.out.println(ans); 
    	}
    }

# 第十题 #

标题： k倍区间

给定一个长度为N的数列，A1, A2, … AN，如果其中一段连续的子序列Ai, Ai+1, … Aj(i <= j)之和是K的倍数，我们就称这个区间\[i, j\]是K倍区间。

你能求出数列中总共有多少个K倍区间吗？

## 输入 ##

第一行包含两个整数N和K。(1 <= N, K <= 100000)  
以下N行每行包含一个整数Ai。(1 <= Ai <= 100000)

## 输出 ##

输出一个整数，代表K倍区间的数目。

例如，  
输入：  
5 2  
1  
2  
3  
4  
5

程序应该输出：  
6

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

public class _10K倍区间 { 
    	static int n;
    	static int k;
    	static int[] arr;
    	static int[] s;//前缀和数组，记录前i个数字之和
    	public static void main(String[] args) { 
    		Scanner sc = new Scanner(System.in);
    		n = sc.nextInt();
    		k = sc.nextInt();
    		arr = new int[n];
    		s = new int[n+1];
    		for(int i = 0; i < n; i++) { 
    			arr[i] = sc.nextInt();
    		}
    		s[0] = 0;
    		for(int i = 1; i <= n; i++) { 
    			for(int j = 0; j < n; j++) { 
    				s[i] = sum(i-1, j);
    			}
    		}
    		int ans1 = f1();//暴力法
    		int ans2 = f2();//前缀和
    		int ans3 = f3();//优化(同余数相减的结果的余数为0)
    		System.out.println(ans1);
    		System.out.println(ans2);
    		System.out.println(ans3);
    	}
    
    	private static int f3() { 
    		int[] ss = new int[n+1];
    		int ans = 0;
    		Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    		for(int i = 0; i <= n; i++) { 
    			ss[i] = s[i]%k;
    			if(map.get(ss[i]) == null) { 
    				map.put(ss[i], 1);
    			}else { 
    				map.put(ss[i],map.get(ss[i])+1);
    			}
    		}
    		Set<Integer> set = map.keySet();
    		for(int key : set) { 
    			int value = map.get(key);
    			ans += (value*(value-1))/2;
    		}
    		return ans;
    	}
    
    	private static int f2() { 
    		int ans = 0;
    		for(int i = 0; i < n; i++) { 
    			for(int j = i+1; j <= n; j++) { 
    				if((s[j]-s[i])%k == 0) { 
    					ans++;
    				}
    			}
    		}
    		return ans;
    	}
    	
    	//暴力解法
    	private static int f1() { 
    		int ans = 0;
    		for(int i = 0; i < n; i++) { 
    			for(int j = i; j < n; j++) { 
    				if(sum(i, j)%k == 0) { 
    					ans++;
    				}
    			}
    		}
    		return ans;
    	}
    	//求数组下标i到下标j之间的和
    	private static int sum(int i, int j) { 
    		int s = 0;
    		for(int m = i; m <= j; m++) { 
    			s = s + arr[m];
    		}
    		return s;
    	}
    }

[20200824153223539.png_pic_center]: /images/20221123/37d055da6183493c892cba69ed1f81c4.png