2018年第九届Java B组蓝桥杯省赛真题
2018年第九届Java B组蓝桥杯省赛真题
这里是蓝桥杯历年的题目专栏，将会陆续更新将往年真题以及解答发布出来，欢迎各位小伙伴关注我吖，你们的点赞关注就是给我最好的动力！！！ 每天更新一届真题，敬请期待
目录
第一题：第几天
题目描述 2000年的1月1日，是那一年的第1天。 那么，2000年的5月4日，是那一年的第几天？
注意：需要提交的是一个整数，不要填写任何多余内容。 题目分析 题目代码
第二题：方格计数
题目描述 如图p1.png所示，在二维平面上有无数个1x1的小方格。
我们以某个小方格的一个顶点为圆心画一个半径为1000的圆。 你能计算出这个圆里有多少个完整的小方格吗？ 题目分析 题目代码
第三题：复数幂
题目描述 设i为虚数单位。对于任意正整数n，(2+3i)^n 的实部和虚部都是整数。 求 (2+3i)^123456 等于多少？ 即(2+3i)的123456次幂，这个数字很大，要求精确表示。
答案写成 “实部±虚部i” 的形式，实部和虚部都是整数（不能用科学计数法表示），中间任何地方都不加空格，实部为正时前面不加正号。(2+3i)^2 写成: -5+12i， (2+3i)^5 的写成: 122-597i 题目分析 题目代码
第四题：测试次数
题目描述 x星球的居民脾气不太好，但好在他们生气的时候唯一的异常举动是：摔手机。 各大厂商也就纷纷推出各种耐摔型手机。x星球的质监局规定了手机必须经过耐摔测试，并且评定出一个耐摔指数来，之后才允许上市流通。
x星球有很多高耸入云的高塔，刚好可以用来做耐摔测试。塔的每一层高度都是一样的，与地球上稍有不同的是，他们的第一层不是地面，而是相当于我们的2楼。
如果手机从第7层扔下去没摔坏，但第8层摔坏了，则手机耐摔指数=7。 特别地，如果手机从第1层扔下去就坏了，则耐摔指数=0。 如果到了塔的最高层第n层扔没摔坏，则耐摔指数=n
为了减少测试次数，从每个厂家抽样3部手机参加测试。
某次测试的塔高为1000层，如果我们总是采用最佳策略，在最坏的运气下最多需要测试多少次才能确定手机的耐摔指数呢？
请填写这个最多测试次数。 题目分析 题目代码
第五题：快速排序
题目描述 以下代码可以从数组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));
}
}题目分析 题目代码
第六题：递增三元组
题目描述 给定三个整数数组 A = [A1, A2, … AN], B = [B1, B2, … BN], C = [C1, C2, … CN]， 请你统计有多少个三元组(i, j, k) 满足：
- 1 <= i, j, k <= N
- Ai < Bj < Ck
【输入格式】 第一行包含一个整数N。 第二行包含N个整数A1, A2, … AN。 第三行包含N个整数B1, B2, … BN。 第四行包含N个整数C1, C2, … CN。
对于30%的数据，1 <= N <= 100 对于60%的数据，1 <= N <= 1000 对于100%的数据，1 <= N <= 100000 0 <= Ai, Bi, Ci <= 100000
【输出格式】 一个整数表示答案
【输入样例】 3 1 1 1 2 2 2 3 3 3
【输出样例】 27
资源约定： 峰值内存消耗（含虚拟机） < 256M CPU消耗 < 1000ms 题目分析 题目代码
第七题：螺旋折线
题目描述 如图p1.pgn所示的螺旋折线经过平面上所有整点恰好一次。 对于整点(X, Y)，我们定义它到原点的距离dis(X, Y)是从原点到(X, Y)的螺旋折线段的长度。
例如dis(0, 1)=3, dis(-2, -1)=9
给出整点坐标(X, Y)，你能计算出dis(X, Y)吗？
【输入格式】 X和Y
对于40%的数据，-1000 <= X, Y <= 1000 对于70%的数据，-100000 <= X， Y <= 100000 对于100%的数据, -1000000000 <= X, Y <= 1000000000
【输出格式】 输出dis(X, Y)
【输入样例】 0 1
【输出样例】
3
资源约定： 峰值内存消耗（含虚拟机） < 256M CPU消耗 < 1000ms 题目分析 题目代码
第八题：日志统计
题目描述 小明维护着一个程序员论坛。现在他收集了一份"点赞"日志，日志共有N行。其中每一行的格式是：
ts id
表示在ts时刻编号id的帖子收到一个"赞"。
现在小明想统计有哪些帖子曾经是"热帖"。如果一个帖子曾在任意一个长度为D的时间段内收到不少于K个赞，小明就认为这个帖子曾是"热帖"。
具体来说，如果存在某个时刻T满足该帖在[T, T+D)这段时间内(注意是左闭右开区间)收到不少于K个赞，该帖就曾是"热帖"。
给定日志，请你帮助小明统计出所有曾是"热帖"的帖子编号。
【输入格式】 第一行包含三个整数N、D和K。 以下N行每行一条日志，包含两个整数ts和id。
对于50%的数据，1 <= K <= N <= 1000 对于100%的数据，1 <= K <= N <= 100000 0 <= ts <= 100000 0 <= id <= 100000
【输出格式】 按从小到大的顺序输出热帖id。每个id一行。
【输入样例】 7 10 2 0 1 0 10 10 10 10 1 9 1 100 3 100 3
【输出样例】 1 3
资源约定： 峰值内存消耗（含虚拟机） < 256M CPU消耗 < 1000ms
题目分析 题目代码
第九题：全球变暖
题目描述 你有一张某海域NxN像素的照片，".“表示海洋、”#"表示陆地，如下所示：
… .##… .##… …##. …####. …###. …
其中"上下左右"四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有2座岛屿。
由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)，它就会被淹没。
例如上图中的海域未来会变成如下样子：
… … … … …#… … …
请你计算：依照科学家的预测，照片中有多少岛屿会被完全淹没。
【输入格式】 第一行包含一个整数N。 (1 <= N <= 1000) 以下N行N列代表一张海域照片。
照片保证第1行、第1列、第N行、第N列的像素都是海洋。
【输出格式】 一个整数表示答案。
【输入样例】 7 … .##… .##… …##. …####. …###. …
【输出样例】 1
资源约定： 峰值内存消耗（含虚拟机） < 256M CPU消耗 < 1000ms 题目分析 题目代码
第十题：堆的计数
题目描述 我们知道包含N个元素的堆可以看成是一棵包含N个节点的完全二叉树。 每个节点有一个权值。对于小根堆来说，父节点的权值一定小于其子节点的权值。
假设N个节点的权值分别是1~N，你能求出一共有多少种不同的小根堆吗？
例如对于N=4有如下3种：
1
/ \
2 3
/
4
1
/ \
3 2
/
4
1
/ \
2 4
/
3由于数量可能超过整型范围，你只需要输出结果除以1000000009的余数。
【输入格式】 一个整数N。 对于40%的数据，1 <= N <= 1000 对于70%的数据，1 <= N <= 10000 对于100%的数据，1 <= N <= 100000
【输出格式】 一个整数表示答案。
【输入样例】 4
【输出样例】 3
资源约定： 峰值内存消耗（含虚拟机） < 256M CPU消耗 < 1000ms 题目分析 题目代码