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

蓝桥杯历年真题及解析.

目录:

    • 蓝桥杯历年真题及解析.
      • 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
2018第九届蓝桥杯省赛JAVA C组真题解析(带源码及解析)_第1张图片

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

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

代码:

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

分析:

在这里插入图片描述

两层循环模拟题目所说过程即可,
直到答案长度为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时:
    2018第九届蓝桥杯省赛JAVA C组真题解析(带源码及解析)_第2张图片

输入,一个正整数n(3 输出,用数字填充的等腰三角形。

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

例如:
输入:
5

程序应该输出:
2018第九届蓝桥杯省赛JAVA C组真题解析(带源码及解析)_第3张图片

再例如:
输入:
10

程序应该输出:
2018第九届蓝桥杯省赛JAVA C组真题解析(带源码及解析)_第4张图片

再例如:
输入:
15

程序应该输出:

2018第九届蓝桥杯省赛JAVA C组真题解析(带源码及解析)_第5张图片

分析:

在这里插入图片描述

字符串问题,
我们先把所有的数拼成字符串,
然后通过字符串下标访问相应位置即可,
至于相应位置则需要找公式,
第 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个整数,由空格分开。

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

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

则程序应该输出:
4

解释:
如图p1.png所示,崇拜关系用箭头表示,红色表示不在圈中。
显然,最大圈是[2 4 5 3] 构成的圈
2018第九届蓝桥杯省赛JAVA C组真题解析(带源码及解析)_第6张图片

再例如:
输入:
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

分析:

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

代码:

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 输出一个整数,表示最多测试多少次。

例如:
输入:
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部手机还用你编程啊?那样的话只好从下往上一层一层测。

分析:

在这里插入图片描述
这是一个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]);
	}
}

算法交流群

2018第九届蓝桥杯省赛JAVA C组真题解析(带源码及解析)_第7张图片

你可能感兴趣的