2018年第九届蓝桥杯真题Java B组
2018年第九届蓝桥杯真题Java B组
1、标题：第几天
2000年的1月1日，是那一年的第1天。
那么，2000年的5月4日，是那一年的第几天？
注意：需要提交的是一个整数，不要填写任何多余内容。
2、标题：方格计数
如图p1.png所示，在二维平面上有无数个1x1的小方格。
从某一个小方格的一个顶点出发绘制一个半径为1000的圆。如何确定这个圆内完整的小方格数量？
注意：需要提交的是一个整数，不要填写任何多余内容。
3、标题：复数幂
令i为虚数单位，则对于所有自然数n而言，在展开(2+3i)^n时其实部与虚部分别均为整数值。 计算(2+3i)的123456次方的具体数值是多少？也就是说，在计算(2+3i)¹²³⁴⁵⁶时需要保持精确。
其平方结果可表示为：-5 + 12i。
(2 + 3i)的五次幂计算结果为：122 - 597i。
注意：需要提交的是一个很庞大的复数，不要填写任何多余内容。
4、标题：测试次数
x星球的居民性格较为暴躁，在他们发怒时表现出的独特行为就是：将手机摔在地上。各大品牌应运而生地推出了多种抗摔手机型号。x星球的质量监督部门对手机实施了耐久性测试标准，并制定了统一的抗摔评分体系。通过这一规定后才准许投入市场销售。
在x星球上分布着成百上千座拔地而起的高塔，在这些建筑中恰好适合用来进行耐摔测试实验。这些建筑每一层的高度都完全相同，在地球上虽然也有高层建筑存在但其第一层多设为地面楼层而这里的第一层则等同于我们的二层楼位置。
当手机从第7层扔下未受损而第8层则会损坏时，则其耐摔指数被设定为7。
特别地指出，在手机从第一层掉落即坏的情况下，则其耐摔指数被设定为0。
若测试到塔顶的第n层仍能安全落地，则其耐摔指数设为n。
为了减少测试次数，从每个厂家抽样3部手机参加测试。
在进行某项测试时，在高度设定为1000层的情况下，在最不利的情况下（无论出现怎样的情况都采取最优策略），所需的最大测试次数是多少才能以确定其抗摔性能？
请填写这个最多测试次数。
注意：需要填写的是一个整数，不要填写任何多余内容。
5、标题：快速排序
以下代码可以从数组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));
}
}
注意：只提交划线部分缺少的代码，不要抄写任何已经存在的代码或符号。
6、标题：递增三元组
给定三个整数数组
A = [A1, A2, ... AN],
B = [B1, B2, ... BN],
C = [C1, C2, ... CN]，
请你统计有多少个三元组(i, j, k) 满足：
1. 1 <= i, j, k <= N
2. Ai < Bj < Ck
输入格式
对于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
请严格按照要求输出指定内容，请避免添加与任务无关的多余信息
7、标题：螺旋折线
如图所示的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
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
将全部的程序代码组织到一个完整的源文件中进行开发，并在测试成功运行的基础上方便直接复制并提交该源码。开发过程中禁止添加任何包（package）相关的语句或指令，并且不允许多线程池（concurrent）等特性。
主类的名字必须是：Main，否则按无效代码处理。
8、标题：日志统计
小明运营着一个专业的程序员交流平台。目前他整理了一份详细的点赞记录。这些记录共有N条。每一记录的具体内容如下：
ts id
表示在ts时刻编号id的帖子收到一个"赞"。
为了找出哪些帖子曾经被标记为“热门帖子”，小明致力于统计所有相关的帖子信息。当某个帖子在过去任何连续时间段内（长度为D）获得了至少K个点赞时，则根据规定将其归类为“热门帖子”。
具体来说，在一段时间内存在一个时间点T使得该帖在[T, T+D)期间内获得至少K个点赞，则称该帖为"热帖"。
给定日志，请你帮助小明统计出所有曾是"热帖"的帖子编号。
输入格式
对于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
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
将所有代码整合到一个源文件中，并在经过调试验证后将其提交至系统。
为避免在源码中使用package关键字以及不采用与 JDK 1.7 或更高版本相关的特性
主类的名字必须是：Main，否则按无效代码处理。
9、标题：全球变暖
你有一张某海域NxN像素的照片，"."表示海洋、"#"表示陆地，如下所示：
.......
.##....
.##....
....##.
..####.
...###.
.......
其中"上下左右"四周相连的一片区域构成一座岛屿。如图所示有2座岛屿
因全球变暖使海平面升高而引发这一变化趋势。科学家们预测，在未来几十年间，预计将会出现岛屿边缘区域的一个像素宽度范围被海水吞没的现象。具体而言，则是当一块陆地像素与其四周（上、下、左、右）的相邻像素中存在至少一个海洋时，则会面临被海水淹没的风险。
例如上图中的海域未来会变成如下样子：
.......
.......
.......
.......
....#..
.......
.......
请你计算：依照科学家的预测，照片中有多少岛屿会被完全淹没。
【输入格式】
第一行包含一个整数N。 (1 <= N <= 1000)
以下N行N列代表一张海域照片。
照片保证第1行、第1列、第N行、第N列的像素都是海洋。
【输出格式】
一个整数表示答案。
【输入样例】
7
.......
.##....
.##....
....##.
..####.
...###.
.......
【输出样例】
1
资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 1000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
All code should be contained within a single source file, ensuring that it is properly debugged and submitted for review.
Avoid using any package statements in your code.
Do not utilize any features from Java versions 1.7 or higher.
The main class name must strictly adhere to the specified naming convention; otherwise, the code will be deemed invalid.
10、标题：堆的计数
众所周知，具有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
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
将所有代码整合至同一个源文件中，并确保在调试阶段完成验证后进行提交。请避免在源码中包含package语句，并且应指定主类名为Main；否则将被视为无效代码。