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

刺骨的言语ヽ痛彻心扉 2022-11-15 14:28 143阅读 0赞

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

### 目录： ###

*   *  蓝桥杯历年真题及解析.
     *   *  A：哪天返回（难度：★）
         *   *  题目：
             *  分析：
             *  代码：
         *  B：猴子分香蕉（难度：★）
         *   *  题目：
             *  分析：
             *  代码：
         *  C：字母阵列（难度：★★）
         *   *  题目：
             *  分析：
             *  代码：
         *  D：第几个幸运数（难度：★★★★）
         *   *  题目：
             *  分析：
             *  代码：
         *  E：书号验证（难度：★★）
         *   *  题目：
             *  分析：
             *  代码：
         *  F：打印大X（难度：★★★）
         *   *  题目：
             *  分析：
             *  代码：
         *  G：缩位求和（难度：★★★）
         *   *  题目：
             *  分析：
             *  代码：
         *  H：等腰三角形（难度：★★★★★）
         *   *  题目：
             *  分析：
             *  代码：
         *  I：小朋友崇拜圈（难度：★★★★）
         *   *  题目：
             *  分析：
             *  代码：
         *  J：耐摔指数（难度：★★★★★）
         *   *  题目：
             *  分析：
             *  代码：
         *  算法交流群

### A：哪天返回（难度：★） ###

#### 题目： ####

小明被不明势力劫持。后被扔到x星站再无问津。小明得知每天都有飞船飞往地球，但需要108元的船票，而他却身无分文。  
他决定在x星战打工。好心的老板答应包食宿，第1天给他1元钱。  
并且，以后的每一天都比前一天多2元钱，直到他有足够的钱买票。  
请计算一下，小明在第几天就能凑够108元，返回地球。

要求提交的是一个整数，表示第几天。请不要提交任何多余的内容。

#### 分析： ####

模拟题目所说过程，编程运算即可，  
答案=11

#### 代码： ####

public class A哪天返回 { 
        public static void main(String[] args) { 
            int cur=1;
            int day=1;
            while(cur<108){ 
                day++;
                cur+=day*2-1;
            }
            System.out.println(day);
        }
    }

### B：猴子分香蕉（难度：★） ###

#### 题目： ####

5只猴子是好朋友，在海边的椰子树上睡着了。这期间，有商船把一大堆香蕉忘记在沙滩上离去。  
第1只猴子醒来，把香蕉均分成5堆，还剩下1个，就吃掉并把自己的一份藏起来继续睡觉。  
第2只猴子醒来，重新把香蕉均分成5堆，还剩下2个，就吃掉并把自己的一份藏起来继续睡觉。  
第3只猴子醒来，重新把香蕉均分成5堆，还剩下3个，就吃掉并把自己的一份藏起来继续睡觉。  
第4只猴子醒来，重新把香蕉均分成5堆，还剩下4个，就吃掉并把自己的一份藏起来继续睡觉。  
第5只猴子醒来，重新把香蕉均分成5堆，哈哈，正好不剩！

请计算一开始最少有多少个香蕉。

需要提交的是一个整数，不要填写任何多余的内容。

#### 分析： ####

从1开始向上找，查看是否符合题目所说条件，  
符合条件的第一个即为解。  
答案=3141

#### 代码： ####

public class B猴子吃香蕉 { 
    	public static int check(int t, int ge) { 
    		if (t <= ge)
    			return -1;
    		t -= ge;
    		if (t % 5 != 0)
    			return -1;
    		else
    			return 4 * t / 5;
    	}
    
    	public static void main(String[] args) { 
    		for (int i = 1; true; i++) { 
    			int t = i;
    			for (int j = 1; t != -1 && j < 5; j++) { 
    				t = check(t, j);
    			}
    			if (t != -1 && t % 5 == 0) { 
    				System.out.println(i);
    				break;
    			}
    		}
    	}
    }

### C：字母阵列（难度：★★） ###

#### 题目： ####

仔细寻找，会发现：在下面的8x8的方阵中，隐藏着字母序列：“LANQIAO”。  
SLANQIAO  
ZOEXCCGB  
MOAYWKHI  
BCCIPLJQ  
SLANQIAO  
RSFWFNYA  
XIFZVWAL  
COAIQNAL

我们约定: 序列可以水平，垂直，或者是斜向；  
并且走向不限（实际上就是有一共8种方向）。  
上图中一共有4个满足要求的串。

下面有一个更大的（100x100）的字母方阵。  
你能算出其中隐藏了多少个“LANQIAO”吗？

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

限于篇幅，100\*100矩阵省略

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

请提交一个整数，不要填写任何多余的内容。

#### 分析： ####

枚举每一个位置作为起点，像八个方向进行对拍“LANQIAO”，  
符合情况的ans++；  
最终运行结束ans即为结果  
答案=

#### 代码： ####

import java.math.*;
    import java.util.*;
     
    public class C字母阵列 { 
        public static void main(String[] args){ 
    // Scanner sc=new Scanner(System.in);
    // char c[][]=new char [100][100];
    // char bz[]="LANQIAO".toCharArray();
    // for(int i=0;i<100;i++){ 
    // String s=sc.nextLine();
    // c[i]=s.toCharArray();
    // }
    // int ans=0;
    // for(int i=0;i<100;i++){ 
    // for(int j=0;j<100;j++){ 
    // if(c[i][j]!='L')continue;
    // for(int dirx=-1;dirx<2;dirx++){ 
    // for(int diry=-1;diry<2;diry++){ 
    // if(dirx*6+i<100&&dirx*6+i>=0&&diry*6+j<100&&diry*6+j>=0){ 
    // boolean ok=true;
    // for(int len=0;len<7;len++){ 
    // if(c[i+dirx*len][j+diry*len]!=bz[len])ok=false;
    // }
    // if(ok)ans++;
    // }
    // }
    // }
    // }
    // }
    // System.out.println(ans);
            System.out.println(41);
        }
    }

### D：第几个幸运数（难度：★★★★） ###

#### 题目： ####

到x星球旅行的游客都被发给一个整数，作为游客编号。  
x星的国王有个怪癖，他只喜欢数字3,5和7。  
国王规定，游客的编号如果只含有因子：3,5,7,就可以获得一份奖品。

我们来看前10个幸运数字是：  
3 5 7 9 15 21 25 27 35 45  
因而第11个幸运数字是：49

小明领到了一个幸运数字 59084709587505，他去领奖的时候，人家要求他准确地说出这是第几个幸运数字，否则领不到奖品。

请你帮小明计算一下，59084709587505是第几个幸运数字。

需要提交的是一个整数，请不要填写任何多余内容。

#### 分析： ####

BFS的思想，从3，5，7开始枚举，  
对于每个数据分别乘以3，5，7  
为了防止时间复杂度过高，将数据存入Set，并且不计算大于59084709587505的数据  
3的29次方即大于59084709587505  
答案=1905

#### 代码： ####

import java.util.*;
    
    public class D第几个幸运数 { 
    	public static void main(String[] args) { 
    		System.out.println(Math.pow(3, 29));
    		long len=3,ans=59084709587505l;
    		ArrayList<Long> list=new ArrayList<Long>();
    		list.add((long) 3);
    		list.add((long) 5);
    		list.add((long) 7);
    		for(int i=0;i<29;i++){ 
    			for(int j=0;j<len;j++){ 
    				for(int k=3;k<8;k+=2){ 
    					if(list.get(j)*k<=ans&&!list.contains(list.get(j)*k)){ 
    						list.add(list.get(j)*k);
    					}
    				}
    				if(list.get(j)*3>ans){ 
    					break ;
    				}
    			}
    			Collections.sort(list);
    			len=list.size();
    		}
    		System.out.println(list.size());
    	}
    }

### E：书号验证（难度：★★） ###

#### 题目： ####

2004年起，国际ISBN中心出版了《13位国际标准书号指南》。  
原有10位书号前加978作为商品分类标识；校验规则也改变。  
校验位的加权算法与10位ISBN的算法不同，具体算法是：  
用1分别乘ISBN的前12位中的奇数位（从左边开始数起），用3乘以偶数位，乘积之和以10为模，10与模值的差值再对10取模（即取个位的数字）即可得到校验位的值，其值范围应该为0~9。

下面的程序实现了该算法，请仔细阅读源码，填写缺失的部分。

public class A
    { 
    	static boolean f(String s){ 
    		int k=1;
    		int sum = 0;
    		for(int i=0; i<s.length(); i++){ 
    			char c = s.charAt(i);
    			if(c=='-' || c==' ') continue;
    			sum += ______________________________;  //填空
    			k++;
    			if(k>12) break; 
    		}
    		
    		return s.charAt(s.length()-1)-'0' == (10-sum % 10)%10;
    	}
    	
    	public static void main(String[] args){ 
    		System.out.println(f("978-7-301-04815-3"));
    		System.out.println(f("978-7-115-38821-6"));
    	}
    }

注意：只提交空缺的代码，不要抄写已经存在的代码。

#### 分析： ####

判断一下奇偶，然后乘以对应位置权值即可。  
答案=(k%20?3:1)\*(s.charAt(i)-‘0’)==

#### 代码： ####

public class E书号验证{ 
    
    	static boolean f(String s){ 
    		int k=1;
    		int sum = 0;
    		for(int i=0; i<s.length(); i++){ 
    			char c = s.charAt(i);
    			if(c=='-' || c==' ') continue;
    			sum+=(k%2==0?3:1)*(s.charAt(i)-'0');//填空
    			k++;
    			if(k>12) break; 
    		}
    		
    		return s.charAt(s.length()-1)-'0' == (10-sum % 10)%10;
    	}
    	
    	public static void main(String[] args){ 
    		System.out.println(f("978-7-115-38821-5"));
    		System.out.println(f("978-7-301-04815-3"));
    		System.out.println(f("978-7-115-38821-6"));
    	}
    }

### F：打印大X（难度：★★★） ###

#### 题目： ####

如下的程序目的是在控制台打印输出大X。  
可以控制两个参数：图形的高度，以及笔宽。

用程序中的测试数据输出效果：

高度=15, 笔宽=3

高度=8, 笔宽=5  
![在这里插入图片描述][20210402092505778.png]

请仔细分析程序流程，填写缺失的代码。

public class A
    { 
    	static void f(int h, int w){ 
    		System.out.println(String.format("高度=%d, 笔宽=%d",h,w));
    		int a1 = 0;
    		int a2 = h - 1;
    		
    		for(int k=0; k<h; k++){ 
    			int p = Math.min(a1,a2);
    			int q = Math.max(a1+w,a2+w);
    			
    			for(int i=0; i<p; i++) System.out.print(" ");
    			
    			if(q-p<w*2){ 
    				____________________________________________ ; //填空
    			}
    			else{ 
    				for(int i=0; i<w; i++) System.out.print("*");
    				for(int i=0; i<q-p-w*2; i++) System.out.print(" ");
    				for(int i=0; i<w; i++) System.out.print("*");
    			}
    			System.out.println();
    			a1++;
    			a2--;
    		}
    	}
    	
    	public static void main(String[] args){ 
    		f(15,3);
    		f(8,5);
    	}
    }

注意：只填写缺失的代码，不要拷贝已经存在的代码。

#### 分析： ####

观察代码发现，p所指向的是每一行的 \* 号的左边界  
Q所指向的是每一行的右边界。  
如果右边界-左边界<两倍的宽度，说明中间这段区间都是 \*  
答案=for(int i=0;i<q-p;i++)System.out.print("\*")

#### 代码： ####

public class F打印大X
    { 
    	static void f(int h, int w){ 
    		System.out.println(String.format("高度=%d, 笔宽=%d",h,w));
    		int a1 = 0;
    		int a2 = h - 1;
    		
    		for(int k=0; k<h; k++){ 
    			int p = Math.min(a1,a2);
    			int q = Math.max(a1+w,a2+w);
    			
    			for(int i=0; i<p; i++) System.out.print(" ");
    			
    			if(q-p<w*2){ 
    				//____________________________________________ ; //填空
    				for(int i=0;i<q-p;i++)System.out.print("*");
    			}
    			else{ 
    				for(int i=0; i<w; i++) System.out.print("*");
    				for(int i=0; i<q-p-w*2; i++) System.out.print(" ");
    				for(int i=0; i<w; i++) System.out.print("*");
    			}
    			System.out.println();
    			a1++;
    			a2--;
    		}
    	}
    	
    	public static void main(String[] args){ 
    		f(15,3);
    		f(8,5);
    	}
    }

### G：缩位求和（难度：★★★） ###

#### 题目： ####

在电子计算机普及以前，人们经常用一个粗略的方法来验算四则运算是否正确。  
比如：248 \* 15 = 3720  
把乘数和被乘数分别逐位求和，如果是多位数再逐位求和，直到是1位数，得  
2 + 4 + 8 = 14 ==> 1 + 4 = 5;  
1 + 5 = 6  
5 \* 6  
而结果逐位求和为 3  
5 \* 6 的结果逐位求和与3符合，说明正确的可能性很大！！（不能排除错误）

请你写一个计算机程序，对给定的字符串逐位求和：  
输入为一个由数字组成的串，表示n位数(n<1000);  
输出为一位数，表示反复逐位求和的结果。

例如：  
输入：  
35379

程序应该输出：  
9

再例如：  
输入：  
7583676109608471656473500295825

程序应该输出：  
1

#### 分析： ####

![在这里插入图片描述][20210402101319978.png]

两层循环模拟题目所说过程即可，  
直到答案长度为1截止

#### 代码： ####

import java.util.Scanner;
    
    public class G缩位求和 { 
    	public static void main(String[] args) { 
    		Scanner sc=new Scanner(System.in);
    		String n=sc.next();
    		int ans=0;
    		for(int i=0;i<n.length();i++){ 
    			ans+=n.charAt(i)-'0';
    		}
    		while(ans>=10){ 
    			int t=0;
    			while(ans!=0){ 
    				t+=ans%10;
    				ans/=10;
    			}
    			ans=t;
    		}
    		System.out.println(ans);
    	}
    }

### H：等腰三角形（难度：★★★★★） ###

#### 题目： ####

本题目要求你在控制台输出一个由数字组成的等腰三角形。  
具体的步骤是：

1.  先用1,2,3，…的自然数拼一个足够长的串
2.  用这个串填充三角形的三条边。从上方顶点开始，逆时针填充。  
    比如，当三角形高度是8时：  
    ![在这里插入图片描述][20210402092649510.png]

输入，一个正整数n(3<n<300),表示三角形的高度  
输出，用数字填充的等腰三角形。

为了便于测评，我们要求空格一律用"."代替。

例如：  
输入：  
5

程序应该输出：  
![在这里插入图片描述][20210402092737964.png]

再例如：  
输入：  
10

程序应该输出：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70]

再例如：  
输入：  
15

程序应该输出：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 1]

#### 分析： ####

![在这里插入图片描述][20210402101253888.png]

字符串问题，  
我们先把所有的数拼成字符串，  
然后通过字符串下标访问相应位置即可，  
至于相应位置则需要找公式，  
第 i 行所对应的两个数字分别在第 i 个位置和第 2\*n-1+n-1+n-i-1-1 个位置  
两者中间的所有元素即为下一层元素。

#### 代码： ####

import java.util.Scanner;
    
    public class H等腰三角形 { 
    	public static void main(String[] args) { 
    		Scanner sc=new Scanner(System.in);
    		int n=sc.nextInt();
    		String s="";
    		int len=Math.max(50, 3*n);
    		for(int i=1;i<len;i++){ 
    			s+=i;
    		}
    		for(int i=0;i<n;i++){ 
    			if(i==0){ 
    				for(int j=n-i-1;j>0;j--){ 
    					System.out.print('.');
    				}
    				System.out.println(s.charAt(0));
    			}else if(i==n-1){ 
    				System.out.println(s.substring(i,i+2*n-1));
    			}else{ 
    				for(int j=n-i-1;j>0;j--){ 
    					System.out.print('.');
    				}
    				System.out.print(s.charAt(i));
    				for(int j=2*n-2;j>2*(n-i)-1;j--){ 
    					System.out.print('.');
    				}
    				System.out.println(s.charAt(2*n-1+n-1+n-i-1-1));
    			}
    		}
    	}
    }

### I：小朋友崇拜圈（难度：★★★★） ###

#### 题目： ####

班里N个小朋友，每个人都有自己最崇拜的一个小朋友（也可以是自己）。  
在一个游戏中，需要小朋友坐一个圈，  
每个小朋友都有自己最崇拜的小朋友在他的右手边。  
求满足条件的圈最大多少人？

小朋友编号为1,2,3,…N  
输入第一行，一个整数N（3<N<100000）  
接下来一行N个整数，由空格分开。

要求输出一个整数，表示满足条件的最大圈的人数。

例如：  
输入：  
9  
3 4 2 5 3 8 4 6 9

则程序应该输出：  
4

解释：  
如图p1.png所示，崇拜关系用箭头表示，红色表示不在圈中。  
显然，最大圈是\[2 4 5 3\] 构成的圈  
![在这里插入图片描述][20210402092915815.png]

再例如：  
输入：  
30  
22 28 16 6 27 21 30 1 29 10 9 14 24 11 7 2 8 5 26 4 12 3 25 18 20 19 23 17 13 15

程序应该输出：  
16

#### 分析： ####

![在这里插入图片描述][20210402101419555.png]  
当小朋友入圈即在标记数组内做一个标记，  
当出现循环即跳出，最大环即为最优解。

#### 代码： ####

import java.util.ArrayList;
    import java.util.Scanner;
    
    public class I小朋友崇拜圈 { 
    	public static int arr[];
    	public static boolean buf[];
    	public static int find(int x){ 
    		ArrayList<Integer> list=new ArrayList<Integer>();
    		while(!list.contains(arr[x])){ 
    			list.add(arr[x]);
    			buf[x]=true;
    			x=arr[x];
    		}
    		return list.size()-list.indexOf(arr[x]);
    	}
    	public static void main(String[] args) { 
    		Scanner sc=new Scanner(System.in);
    		int n=sc.nextInt();
    		arr=new int[n+1];
    		buf=new boolean[n+1];
    		for(int i=1;i<=n;i++){ 
    			arr[i]=sc.nextInt();
    		}
    		int ans=1;
    		for(int i=1;i<=n;i++){ 
    			if(!buf[i]){ 
    				ans=Math.max(ans, find(i));
    			}
    		}
    		System.out.println(ans);
    	}
    }

### J：耐摔指数（难度：★★★★★） ###

#### 题目： ####

x星球的居民脾气不太好，但好在他们生气的时候唯一的异常举动是：摔手机。  
各大厂商也就纷纷推出各种耐摔型手机。x星球的质监局规定了手机必须经过耐摔测试，并且评定出一个耐摔指数来，之后才允许上市流通。

x星球有很多高耸入云的高塔，刚好可以用来做耐摔测试。塔的每一层高度都是一样的，与地球上稍有不同的是，他们的第一层不是地面，而是相当于我们的2楼。

如果手机从第7层扔下去没摔坏，但第8层摔坏了，则手机耐摔指数=7。  
特别地，如果手机从第1层扔下去就坏了，则耐摔指数=0。  
如果到了塔的最高层第n层扔没摔坏，则耐摔指数=n

为了减少测试次数，从每个厂家抽样3部手机参加测试。

如果已知了测试塔的高度，并且采用最佳策略，在最坏的运气下最多需要测试多少次才能确定手机的耐摔指数呢？

输入数据，一个整数n（3<n<10000）,表示测试塔的高度。  
输出一个整数，表示最多测试多少次。

例如：  
输入：  
3

程序应该输出：  
2

解释：  
手机a从2楼扔下去，坏了，就把b手机从1楼扔；否则a手机继续3层扔下

再例如：  
输入：  
7

程序应该输出：  
3

解释：  
a手机从4层扔，坏了，则下面有3层，b,c 两部手机2次足可以测出指数；  
若是没坏，手机充足，上面5,6,7 三层2次也容易测出。

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

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

笨笨有话说：  
我觉得3个手机太难了，要是2个手机还可以考虑一下。

歪歪有话说：  
想什么呢，你！要是1部手机还用你编程啊？那样的话只好从下往上一层一层测。

#### 分析： ####

![在这里插入图片描述][20210402101601370.png]  
这是一个DP问题，  
因为我们只有三部手机，所以二分的做法明显是错误的。  
首先我们假设我们只有一部手机，那么我们只能一层一层的试，才能保证在手机摔坏之前测出耐摔指数。  
再假设我们只有两部手机，假设楼高为 i ，第一次摔手机的楼层为 j。  
则有两种情况（手机坏了 or 手机没坏）  
手机坏了：则剩余（ j - 1 ）层楼只能一层一层的试上去。  
手机没坏：则剩余（ i - j ）层楼依旧可以使用此等跳跃的方式。  
三部手机同理。  
所以我们可以推导出DP公式

> arr\[i\]\[k\] = Math.min(arr\[i\]\[k\], Math.max(arr\[j - 1\]\[k - 1\], arr\[i - j\]\[k\]) + 1);

#### 代码： ####

package JC2018;
    
    import java.util.Scanner;
    
    public class J耐摔指数 { 
    	public static void main(String[] args) { 
    		Scanner sc = new Scanner(System.in);
    		int n = sc.nextInt();
    		int arr[][] = new int[n + 1][4];
    		for (int i = 1; i <= n; i++) { 
    			for(int j=1;j<4;j++){ 
    				arr[i][j]=i;
    			}
    		}
    		for (int k = 2; k < 4; k++){ 
    			for (int i = 1; i <= n; i++) { 
    				for (int j = 1; j <= (i+1)/2; j++) { 
    					arr[i][k] = Math.min(arr[i][k], Math.max(arr[j - 1][k - 1], arr[i - j][k]) + 1);
    				}
    			}
    		}
    		System.out.println(arr[n][3]);
    	}
    }

### 算法交流群 ###

![在这里插入图片描述][20210402101902999.png]

[Link 1]: https://blog.csdn.net/qq_43652327/article/details/104899994
[20210402092505778.png]: /images/20221022/528d9d8208a64865bd41af5f28abd000.png
[20210402101319978.png]: /images/20221022/312d623c323e433686af292e5335144c.png
[20210402092649510.png]: /images/20221022/d775dd3b6c7b4b928c46033ae41daf47.png
[20210402092737964.png]: https://img-blog.csdnimg.cn/20210402092737964.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2021040209280875.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20210402092832481.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3,size_16,color_FFFFFF,t_70
[20210402101253888.png]: https://img-blog.csdnimg.cn/20210402101253888.png
[20210402092915815.png]: https://img-blog.csdnimg.cn/20210402092915815.png
[20210402101419555.png]: https://img-blog.csdnimg.cn/20210402101419555.png
[20210402101601370.png]: https://img-blog.csdnimg.cn/20210402101601370.png
[20210402101902999.png]: https://img-blog.csdnimg.cn/20210402101902999.png