蓝桥杯2018年省赛[第七届]-JavaB组赛题解析
蓝桥杯官方讲解视频：https://www.lanqiao.cn/courses/2737
真题文档：https://www.lanqiao.cn/courses/2786/learning/?id=67811

时间：4小时
题量：3个简单填空题+1个中等填空题+1个代码填空题+5个编程题
总分：150分

由于篇幅原因，本篇只有1-5题（所有填空题）的解析，6-10题解析见下篇文章
蓝桥杯2018年省赛[第九届]-JavaB组赛题解析（下）

题1.第几天[填空][3分]（★）

1.题目描述

2000年的1月1日，是那一年的第1天。
那么，2000年的5月4日，是那一年的第几天？

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

2.简要分析

• 日期间隔非常少，可以一个月一个月的数，也可以用Calendar类计算。
• 2000年是闰年，所以是：31+29+31+30+4=125.

3.实现代码

public class _01第几天 {public static void main(String[] args) {Calendar calendar=Calendar.getInstance();calendar.set(Calendar.YEAR,2000);calendar.set(Calendar.MONTH,4);calendar.set(Calendar.DAY_OF_MONTH,4);System.out.println(calendar.get(Calendar.DAY_OF_YEAR));//125}
}

4.答案

125

题2.方格计数[填空][7分]（★★）

1.题目描述

如图p1.png所示，在二维平面上有无数个1x1的小方格。

我们以某个小方格的一个顶点为圆心画一个半径为1000的圆。
你能计算出这个圆里有多少个完整的小方格吗？

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

2.简要分析

• 尝试找规律，发现没有什么明显的规律，那么我们可以用代数的方式判断一个点是否在圆内，如果一个正方形的左下角和右上角都在圆内，那么可以肯定这个正方形在圆内，因为圆是上下左右对称的，所以我们只需要判断第一象限。

3.实现代码

public class _02方格计数 {public static void main(String[] args) {long ans=0;//枚举第一象限每个正方形的左下角顶点for(int x=0;x<=1000;x++){for(int y=0;y<=1000;y++){if(x*x+y*y<=1000*1000&&(x+1)*(x+1)+(y+1)*(y+1)<=1000*1000){ans++;}}}System.out.println(4*ans);//3137548}
}

4.答案

3137548

3.复数幂[13分]（★★）

1.题目描述

设i为虚数单位。对于任意正整数n，(2+3i)^n 的实部和虚部都是整数。
求 (2+3i)^123456 等于多少？ 即(2+3i)的123456次幂，这个数字很大，要求精确表示。

答案写成 "实部±虚部i"的形式，实部和虚部都是整数（不能用科学计数法表示），中间任何地方都不加空格，实部为正时前面不加正号。(2+3i)^2 写成: -5+12i，
(2+3i)^5 的写成: 122-597i

注意：需要提交的是一个很庞大的复数，不要填写任何多余内容。

2.简要分析

• 单纯就这个计算来说一点都不难，只要把复数的计算公式写在旁边就行了。(a+bi)(c+di)=ac-bd+(ad+bc)i
• 但是很多人是真的低估了这个数字的大小了，用long类型计算，最后得出结果是：

4043220979119144065-7374402350132176768i

• 还说验算了一些数据是对的。
• 其实验算的是前面的小数据，还可以，稍微大点的数据就不行了，必须使用BigInteger类来计算。
• 实际上在35次方的时候，long类型就会溢出了。
• 最后的结果很长，如果重定向输出流到为文件，应该是个135k左右的文件。

3.实现代码

/*(a+bi)(c+di)=ac-bd+(ad+bc)ic=2,d=3*/
public class _03复数幂 {public static void main(String[] args) {Scanner sc=new Scanner(System.in);int n=sc.nextInt();//当n35,开始出现越界情况solve(n);}/*** BigInteger类计算负数2+3i的n次方* @param n*/static void solve(int n){BigInteger a=new BigInteger("2");BigInteger b=new BigInteger("3");for(int i=1;i<n;i++){BigInteger olda=a;a=a.multiply(new BigInteger("2")).add(b.multiply(new BigInteger("-3")));b=olda.multiply(new BigInteger("3")).add(b.multiply(new BigInteger("2")));}System.out.println(a.toString());System.out.println(b.toString());}
}

4.答案

• 数据太大，我复制到博客上导致卡死了，哈哈哈，大概是这样135k的文件就对了。

题4.测试次数[填空][17分]（★★★）

1.题目描述

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

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

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

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

某次测试的塔高为1000层，如果我们总是采用最佳策略，在最坏的运气下最多需要测试多少次才能确定手机的耐摔指数呢？

请填写这个最多测试次数。

注意：需要填写的是一个整数，不要填写任何多余内容。

2.简要分析

• 这个问题的关键是对最佳策略和最坏运气的理解。
• 最佳策略就时指最好的方法，最坏的运气就是指最多需要尝试的次数，也可以理解为：有n种可能尝试的方法，每种方法最多需要尝试的次数是m[i]，那么采用最佳策略，并且是最坏运气的情况下，我们需要测试min{m[i]}次
• 具体使用的方法是动态规划。
• dp[i][j]表示一共有 i 层楼梯的情况下，使用 j 个鸡蛋的最少实验的次数。
• 状态转移方程：dp[i][j]=min{max(dp[k-1][j-1],dp[i-k][j]+1)} (1<=k<=i)
• 其实这个问题也就是鸡蛋掉落问题，有关这个问题的分析，可以查看：鸡蛋掉落–一步一步的dp

3.实现代码

public class _04测试次数 {public static void main(String[] args) {System.out.println(superEggDrop(3,1000));}public static int superEggDrop(int K, int N) {int dp[][]=new int[N+1][K+1];for(int j=0;j<=K;j++){dp[0][j]=0;dp[1][j]=1;}dp[1][0]=0;for(int i=2;i<=N;i++){Arrays.fill(dp[i],i);dp[i][0]=0;}for(int i=2;i<=N;i++){for(int j=2;j<=K;j++){int left = 1;int right=i;while(left<right){int mid = left + (right - left + 1) / 2;if(dp[mid-1][j-1]>dp[i-mid][j]){right=mid-1;}else{left=mid;}}dp[i][j]=Math.max(dp[left-1][j-1],dp[i-left][j])+1;}}return dp[N][K];}}

4.答案

19

题5.快速排序[代码填空][9分]（★★）

1.简要分析

以下代码可以从数组a[]中找出第k小的元素。

它使用了类似快速排序中的分治算法，望时间复杂度是O(N)的。期

请仔细阅读分析源码，填写划线部分缺失的内容。

import java.util.Random;
public class Main{public static int quickSelect(int a[], int l, int r, int k) {Random rand = new Random();int p = rand.nextInt(r - l + 1) + l;int x = a[p];int tmp = a[p]; a[p] = a[r]; a[r] = tmp;int i = l, j = r;while(i < j) {while(i < j && a[i] < x) i++;if(i < j) {a[j] = a[i];j--;}while(i < j && a[j] > x) j--;if(i < j) {a[i] = a[j];i++;}}a[i] = x;p = i;if(i - l + 1 == k) return a[i];if(i - l + 1 < k) return quickSelect( _________________________________ ); //填空else return quickSelect(a, l, i - 1, k);}public static void main(String args[]) {int [] a = {1, 4, 2, 8, 5, 7};System.out.println(quickSelect(a, 0, 5, 4));}
}

注意：只提交划线部分缺少的代码，不要抄写任何已经存在的代码或符号。

2.简要分析

• 这个问题需要对分治算法比较了解。
• 刚开始比较难以理解，我们可以一步一步的写些注释，或者拿个例子仔细的试一下，理解一下代码的主要思想，再尝试着去填那个空，多写些测试数据试一下。
• 对于这种递归类的题，我们只要弄明白参数的含义和本层递归的用途就行了。
• 着重分析直接返回结果的那里，如果那个区间[l,i]的长度等于k，就直接返回，我们就可以知道，区间[l.i]是有序了的，所以如果[l,i]的长度要小于k，说明还要继续找下个区间的第k-(i-l+1)个最小值，并且从[i+1,r]开始找。
• 题目较迷惑的行为是后面的p=i没有实际用途，哈哈哈。

3.实现代码

public class _05快速排序 {public static int quickSelect(int a[], int l, int r, int k) {Random rand = new Random();//取区间[l,r]的一个随机下标int p = rand.nextInt(r - l + 1) + l;//x是上一步取出的随机数int x = a[p];//交换a[p]和a[r] 实际上是交换取的范围内的随机数和区间最右边的一个数int tmp = a[p]; a[p] = a[r]; a[r] = tmp;//i从l开始,j从r开始，代表左右指针int i = l, j = r;while(i < j) {//如果ixwhile(i < j && a[i] < x) i++;//如果是a[i]>x的情况if(i < j) {//此时a[j]等于a[i]a[j] = a[i];//j左移j--;}//如果iwhile(i < j && a[j] > x) j--;//如果是a[j]if(i < j) {//此时的a[i]等于a[j]a[i] = a[j];//i右移i++;}}a[i] = x;p = i;//到这一步为止，可以确定区间[l,i]是有序的//(i-l+1)是区间[l,i]的长度 如果区间的长度等于k,说明找到了第k小的数,返回a[i]if(i - l + 1 == k) return a[i];//如果区间的长度小于kif(i - l + 1 < k) return quickSelect(a,i+1,r,k-(i-l+1)); //填空//如果区间的长度大于kelse return quickSelect(a, l, i - 1, k);}public static void main(String args[]) {int [] a = {1, 4, 2, 8, 5, 7};System.out.println(quickSelect(a, 0, 5, 4));}}

4.答案

a,i+1,r,k-(i-l+1)

由于篇幅原因，本篇只有1-5题（所有填空题）的解析，6-10题解析见下篇文章
蓝桥杯2018年省赛[第九届]-JavaB组赛题解析（下）

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！