2018蓝桥杯C/C++真题题解
目录
A:这几天
题目描述
本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果输出即可。
20002000 年的 11 月 11 日,是那一年的第 11 天。
那么,20002000 年的 55 月 44 日,是那一年的第几天?
运行限制
- 最大运行时间:1s
- 最大运行内存: 128M
没啥说的
B:明码
题目描述
本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果输出即可。
汉字的字形存在于字库中,即便在今天,16 点阵的字库也仍然使用广泛。
16 点阵的字库把每个汉字看成是 16×16 个像素信息。并把这些信息记录在字节中。
一个字节可以存储 88 位信息,用 32 个字节就可以存一个汉字的字形了。 把每个字节转为 2 进制表示,11 表示墨迹,0 表示底色。每行 2 个字节,一共 16行,布局是:
这道题目是给你一段多个汉字组成的信息,每个汉字用 3232 个字节表示,这里给出了字节作为有符号整数的值。
题目的要求隐藏在这些信息中。你的任务是复原这些汉字的字形,从中看出题目的要求,并根据要求填写答案。
这段信息是(一共 1010 个汉字):
运行限制
- 最大运行时间:1s
- 最大运行内存: 128M
语文理解题,将这个转为二进制,一行打印两个数。
C:乘积尾零
本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果输出即可。
如下的 10 行数据,每行有 10 个整数,请你求出它们的乘积的末尾有多少个零?
运行限制
- 最大运行时间:1s
- 最大运行内存: 128M
100个数乘积,求末尾有多少个0;
D:测试次数
题目描述
本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果输出即可。
X 星球的居民脾气不太好,但好在他们生气的时候唯一的异常举动是:摔手机。
各大厂商也就纷纷推出各种耐摔型手机。x星球的质监局规定了手机必须经过耐摔测试,并且评定出一个耐摔指数来,之后才允许上市流通。
X 星球有很多高耸入云的高塔,刚好可以用来做耐摔测试。塔的每一层高度都是一样的,与地球上稍有不同的是,他们的第一层不是地面,而是相当于我们的 2 楼。
如果手机从第 7 层扔下去没摔坏,但第 8 层摔坏了,则手机耐摔指 =7。 特别地,如果手机从第 1 层扔下去就坏了,则耐摔指数 =0。 如果到了塔的最高层第 n 层扔没摔坏,则耐摔指数 =n。
为了减少测试次数,从每个厂家抽样 3 部手机参加测试。
某次测试的塔高为 1000 层,如果我们总是采用最佳策略,在最坏的运气下最多需要测试多少次才能确定手机的耐摔指数呢?
请填写这个最多测试次数。
运行限制
- 最大运行时间:1s
- 最大运行内存: 128M
采用最佳策略,意思是把三个手机都摔坏。因为摔坏来试探,肯定比从第一个一个个测评要快。也可以理解为最佳策略时,一定三个手机都摔坏。最坏运气是指采用了步数最多的那一个耐摔指数。首先随意高度遍历一个手机扔下去,有两种可能。摔坏了和没摔坏。假设此时为k层。那么摔坏了,耐摔指数一定在0到k-1;之间。没摔坏一定在1000到k之间。
递推公式:dp[i]=min(dp[i][j],max(dp[k-1][j-1],dp[i-k][j]));
E:快速排序
题目描述
本题为代码补全填空题,请将题目中给出的源代码补全,并复制到右侧代码框中,选择对应的编译语言(C/Java)后进行提交。若题目中给出的源代码语言不唯一,则只需选择其一进行补全提交即可。复制后需将源代码中填空部分的下划线删掉,填上你的答案。提交后若未能通过,除考虑填空部分出错外,还需注意是否因在复制后有改动非填空部分产生错误。
以下代码可以从数组 a[ ] 中找出第 k小的元素。
它使用了类似快速排序中的分治算法,期望时间复杂度是O(N)的。
请仔细阅读分析源码,填写划线部分缺失的内容。
源代码
C
Java
运行限制
- 最大运行时间:1s
- 最大运行内存: 256M
我是用的c,首先添加头文件#include <stdlib.h>,随机函数rand()用。
首先快速排序要找一个基点,题目中是随机的,然后放到最后一位。左指针向右移动直到找到一个大于基数的数,将其复制到最后,随后右指针向左移动,直到找到一个小于基数的数,将其赋予左指针,以此循环,最后左右指针碰头,将基点赋予该位置。这样导致基点右边都是大于基点,左边都是小于基点。然后判断基点下标(以未移动的左指针开始算)适合符合。
F:递增三元组
题目描述
给定三个整数数组
A = A1,A2,⋯AN],
B=[B1,B2,⋯BN],
C=[C1,C2,⋯CN],
请你统计有多少个三元组 (i,j,k) 满足:
N1≤i,j,k≤N;
Ai<Bj<Ck。
输入描述
第一行包含一个整数 N。
第二行包含 N 个整数 A1,A2,⋯AN。
第三行包含 N 个整数 B1,B2,⋯BN。
第四行包含 N 个整数 C1,C2,⋯CN。
其中1≤N≤105,0≤Ai,Bi,Ci≤105。
输出描述
输出一个整数表示答案。
输入输出样例
示例
输入
输出
运行限制
- 最大运行时间:2s
- 最大运行内存: 256M
G:螺旋折线
题目描述
如下图所示的螺旋折线经过平面上所有整点恰好一次。
对于整点 (X,Y),我们定义它到原点的距离dis(X,Y) 是从原点到 (X,Y)的螺旋折线段的长度。
例如 dis(−2,−1)=9。
给出整点坐标 (X,Y),你能计算出 dis(X,Y) 吗?
输入描述
输入格式:
输入一行,X 和 Y ,−109≤X,Y≤109。
输出描述
输出 dis(X,Y)。
输入输出样例
示例
输入
输出
运行限制
- 最大运行时间:1s
- 最大运行内存: 256M
曼哈顿距离方法比较简单,一开始我是每个象限推导,好麻烦的。然后看到网上有曼哈顿距离。
H:日志统计
题目描述
小明维护着一个程序员论坛。现在他收集了一份"点赞"日志,日志共有 N 行。其中每一行的格式是:
ts id
表示在 ts 时刻编号 id 的帖子收到一个"赞"。
现在小明想统计有哪些帖子曾经是"热帖"。如果一个帖子曾在任意一个长度为 DD 的时间段内收到不少于 KK 个赞,小明就认为这个帖子曾是"热帖"。
具体来说,如果存在某个时刻 T 满足该帖在 T,T+D) 这段时间内(注意是左闭右开区间)收到不少于 K 个赞,该帖就曾是"热帖"。
给定日志,请你帮助小明统计出所有曾是"热帖"的帖子编号。
输入描述
输入格式:
第一行包含三个整数N,D,K。
以下 N 行每行一条日志,包含两个整数 ts 和 id。
其中,1≤K≤N≤105,0≤ts≤105,0≤id≤105。
输出描述
按从小到大的顺序输出热帖 id。每个 id 一行。
输入输出样例
示例
输入
输出
运行限制
- 最大运行时间:1s
- 最大运行内存: 256M
找了半天都没找出问题来。啊啊啊啊
I:全球变暖
题目描述
你有一张某海域 NxNNxN 像素的照片,"."表示海洋、"#"表示陆地,如下所示:
.......
.##....
.##....
....##.
..####.
...###.
.......
其中"上下左右"四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有 2 座岛屿。
由于全球变暖导致了海面上升,科学家预测未来几十年,岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋),它就会被淹没。
例如上图中的海域未来会变成如下样子:
.......
.......
.......
.......
....#..
.......
.......
请你计算:依照科学家的预测,照片中有多少岛屿会被完全淹没。
输入描述
第一行包含一个整数 (1≤N≤1000)。
以下 N 行 N 列代表一张海域照片。
照片保证第 1 行、第 1 列、第 N 行、第 N 列的像素都是海洋。、
输出一个整数表示答案。
输入输出样例
示例
输入
输出
运行限制
- 最大运行时间:1s
- 最大运行内存: 256M
dfs深搜,立一个flag,没有淹没为ture
J:乘积最大
题目描述
给定 NN 个整数 A1,A2,⋯AN。请你从中选出 K 个数,使其乘积最大。
请你求出最大的乘积,由于乘积可能超出整型范围,你只需输出乘积除以 10^9+9109+9 的余数。
注意,如果 X<0,我们定义 X 除以 09+9 的余数是负(−X)除以 10^9+9109+9 的余数。
即:0−((0−x)%109+9)。
输入描述
输入格式:
第一行包含两个整数N,K。
以下 NN 行每行一个整数Ai。
其中,1≤K≤N≤105,−105≤Ai≤105。
输出描述
输出一个整数,表示答案。
输入输出样例
示例
输入
输出
运行限制
- 最大运行时间:1s
- 最大运行内存: 256M
分类讨论,排序后考虑都是正数,都是负数,和正负数都有
- 点赞
- 收藏
- 关注作者
评论(0)