蓝桥题目汇总41-52
Last Update:
出差
问题描述
$\mathrm{A}$ 国有 $N$ 个城市, 编号为 $1 \ldots N$ 。小明是编号为 1 的城市中一家公司的员 工, 今天突然接到了上级通知需要去编号为 $N$ 的城市出差。
由于疫情原因, 很多直达的交通方式暂时关闭, 小明无法乘坐飞机直接从 城市 1 到达城市 $N$, 需要通过其他城市进行陆路交通中转。小明通过交通信息 网, 查询到了 $M$ 条城市之间仍然还开通的路线信息以及每一条路线需要花费的 时间。
同样由于疫情原因, 小明到达一个城市后需要隔离观察一段时间才能离开 该城市前往其他城市。通过网络, 小明也查询到了各个城市的隔离信息。(由于 小明之前在城市 1 , 因此可以直接离开城市 1 , 不需要隔离）
由于上级要求, 小明希望能够尽快赶到城市 $\mathrm{N}$, 因此他求助于你, 希望你 能帮他规划一条路线, 能够在最短时间内到达城市 $N$ 。
输入格式
第 1 行: 两个正整数 $N, M, N$ 表示 A 国的城市数量, $M$ 表示末关闭的路 线数量
第 2 行: $N$ 个正整数, 第 $i$ 个整数 $C_{i}$ 表示到达编号为 $\mathrm{i}$ 的城市后需要隔离 的时间
第 $3 \ldots M+2$ 行: 每行 3 个正整数, $u, v, c$, 表示有一条城市 $u$ 到城市 $v$ 的 双向路线仍然开通着, 通过该路线的时间为 $c$
输出格式
第 1 行: 1 个正整数, 表示小明从城市 1 出发到达城市 $N$ 的最短时间（到 达城市 $N$, 不需要计算城市 $N$ 的隔离时间）
样例输入
1 | |
样例输出
1 | |
样例说明
评测用例规模与约定
对于 $100 %$ 的数据, $1 \leq N \leq 1000,1 \leq M \leq 10000,1 \leq C_{i} \leq 200,1 \leq u, v \leq$ $N, 1 \leq c \leq 1000$
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 1s | 512M |
| C | 1s | 512M |
| Python3 | 1s | 512M |
| Java | 1s | 512M |
聪明的猴子
题目描述
在一个热带雨林中生存着一群猴子，它们以树上的果子为生。昨天下了一场大雨，现在雨过天晴，但整个雨林的地表还是被大水淹没着，部分植物的树冠露在水面上。猴子不会游泳，但跳跃能力比较强，它们仍然可以在露出水面的不同树冠上来回穿梭，以找到喜欢吃的果实。
现在，在这个地区露出水面的有 $N$ 棵树，假设每棵树本身的直径都很小，可以忽略不计。我们在这块区域上建立直角坐标系，则每一棵树的位置由其所对应的坐标表示(任意两棵树的坐标都不相同)。
在这个地区住着的猴子有 $M$ 个，下雨时，它们都躲到了茂密高大的树冠中，没有被大水冲走。由于各个猴子的年龄不同、身体素质不同，它们跳跃的能力不同。有的猴子跳跃的距离比较远(当然也可以跳到较近的树上)，而有些猴子跳跃的距离就比较近。这些猴子非常聪明，它们通过目测就可以准确地判断出自己能否跳到对面的树上。
现已知猴子的数量及每一个猴子的最大跳跃距离，还知道露出水面的每一棵树的坐标，你的任务是统计有多少个猴子可以在这个地区露出水面的所有树冠上觅食。
输入描述
第 $1$ 行为一个整数，表示猴子的个数 $M(2 \leq M \leq 500)$；
第 $2$ 行为 $M$ 个整数，依次表示猴子的最大跳跃距离（每个整数值在 $1 \sim 1000$之间）；
第 $3$ 行为一个整数表示树的总棵数 $N(2 \leq N \leq 1000)$；
第 $4$ 行至第 $N+3$ 行为 $N$ 棵树的坐标（横纵坐标均为整数，范围为：$-1000 \sim 1000$）。
（同一行的整数间用空格分开）
输出描述
输出一个整数，表示可以在这个地区的所有树冠上觅食的猴子数。
输入输出样例
示例 1
输入
1 | |
输出
1 | |
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 1s | 128M |
| C | 1s | 128M |
| Python3 | 1s | 128M |
| Java | 1s | 128M |
通电
题目描述
2015 年，全中国实现了户户通电。作为一名电力建设者，小明正在帮助一带一路上的国家通电。
这一次，小明要帮助 $n$ 个村庄通电，其中 1 号村庄正好可以建立一个发电站，所发的电足够所有村庄使用。
现在，这 $n$ 个村庄之间都没有电线相连，小明主要要做的是架设电线连接这些村庄，使得所有村庄都直接或间接的与发电站相通。
小明测量了所有村庄的位置（坐标）和高度，如果要连接两个村庄，小明需要花费两个村庄之间的坐标距离加上高度差的平方，形式化描述为坐标为($x_1, y_1$) 高度为 $h_1$ 的村庄与坐标为 ($x_2, y_2$) 高度为 $h_2$ 的村庄之间连接的费用为
$\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}+(h_1-h_2)^2$
高度的计算方式与横纵坐标的计算方式不同。
由于经费有限，请帮助小明计算他至少要花费多少费用才能使这 $n$ 个村庄都通电。
输入描述
输入的第一行包含一个整数 $n$ ，表示村庄的数量。
接下来 $n$ 行，每个三个整数 $x, y,h$，分别表示一个村庄的横、纵坐标和高度，其中第一个村庄可以建立发电站。
其中，$1 \leq n \leq 1000，0 \leq x, y, h \leq 10000$。
输出描述
输出一行，包含一个实数，四舍五入保留 2 位小数，表示答案。
输入输出样例
示例
输入
1 | |
输出
1 | |
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 1s | 256M |
| C | 1s | 256M |
| Python3 | 1s | 256M |
| Java | 1s | 256M |
机房
问题描述
这天, 小明在机房学习。
他发现机房里一共有 $n$ 台电脑, 编号为 1 到 $n$, 电脑和电脑之间有网线连 接, 一共有 $n-1$ 根网线将 $n$ 台电脑连接起来使得任意两台电脑都直接或者间 接地相连。
小明发现每台电脑转发、发送或者接受信息需要的时间取决于这台电脑和 多少台电脑直接相连, 而信息在网线中的传播时间可以忽略。比如如果某台电脑 用网线直接连接了另外 $d$ 台电脑, 那么任何经过这台电脑的信息都会延迟 $d$ 单 位时间 (发送方和接收方也会产生这样的延迟, 当然如果发送方和接收方都是 同一台电脑就只会产生一次延迟)。
小明一共产生了 $m$ 个疑问: 如果电脑 $u_{i}$ 向电脑 $v_{i}$ 发送信息, 那么信息从 $u_{i}$ 传到 $v_{i}$ 的最短时间是多少?
输入格式
输入共 $n+m$ 行, 第一行为两个正整数 $n, m$ 。
后面 $n-1$ 行, 每行两个正整数 $x, y$ 表示编号为 $x$ 和 $y$ 的两台电脑用网线 直接相连。
后面 $m$ 行, 每行两个正整数 $u_{i}, v_{i}$ 表示小明的第 $i$ 个疑问。
输出格式
输出共 $m$ 行, 第 $i$ 行一个正整数表示小明第 $i$ 个疑问的答案。
样例输入
1 | |
样例输出
1 | |
样例说明
这四台电脑各自的延迟分别为 $2,2,1,1$ 。
对于第一个询问, 从 2 到 3 需要经过 $2,1,3$, 所以时间和为 $2+2+1=5$ 。
对于第二个询问, 从 3 到 4 需要经过 $3,1,2,4$, 所以时间和为 $1+2+2+1=6$。
对于第三个询问, 从 3 到 3 只会产生一次延迟, 所以时间为 1 。
评测用例规模与约定
对于 $30 %$ 的数据, 保证 $n, m \leq 1000$;
对于 $100 %$ 的数据, 保证 $n, m \leq 100000$ 。
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 1s | 512M |
| C | 1s | 512M |
| Python3 | 1s | 512M |
| Java | 1s | 512M |
环境治理
问题描述
LQ 国拥有 $n$ 个城市, 从 0 到 $n-1$ 编号, 这 $n$ 个城市两两之间都有且仅有 一条双向道路连接, 这意味着任意两个城市之间都是可达的。每条道路都有一 个属性 $D$, 表示这条道路的灰尘度。当从一个城市 $A$ 前往另一个城市 $B$ 时, 可 能存在多条路线, 每条路线的灰尘度定义为这条路线所经过的所有道路的灰尘 度之和, LQ 国的人都很讨厌灰尘, 所以他们总会优先选择灰尘度最小的路线。
LQ 国很看重居民的出行环境, 他们用一个指标 $P$ 来衡量 LQ 国的出行环 境, $P$ 定义为:
$P=\sum_{i=0}^{n-1} \sum_{j=0}^{n-1} d(i, j)$
其中 $d(i, j)$ 表示城市 $i$ 到城市 $j$ 之间灰尘度最小的路线对应的灰尘度的值。 为了改善出行环境, 每个城市都要有所作为, 当某个城市进行道路改善时, 会将与这个城市直接相连的所有道路的灰尘度都减少 1 , 但每条道路都有一个 灰尘度的下限值 $L$, 当灰尘度达到道路的下限值时, 无论再怎么改善, 道路的 灰尘度也不会再减小了。
具体的计划是这样的:
第 1 天, 0 号城市对与其直接相连的道路环境进行改善;
第 2 天, 1 号城市对与其直接相连的道路环境进行改善;
$\cdots$
第 $n$ 天, $n-1$ 号城市对与其直接相连的道路环境进行改善;
第 $n+1$ 天, 0 号城市对与其直接相连的道路环境进行改善;
第 $n+2$ 天, 1 号城市对与其直接相连的道路环境进行改善;
LQ 国想要使得 $P$ 指标满足 $P \leq Q$ 。请问最少要经过多少天之后, $P$ 指标 可以满足 $P \leq Q$ 。如果在初始时就已经满足条件, 则输出 0 ; 如果永远不可能 满足, 则输出 $-1$ 。
输入格式
输入的第一行包含两个整数 $n, Q$, 用一个空格分隔, 分别表示城市个数和 期望达到的 $P$ 指标。
接下来 $n$ 行, 每行包含 $n$ 个整数, 相邻两个整数之间用一个空格分隔, 其 中第 $i$ 行第 $j$ 列的值 $D_{i j}\left(D_{i j}=D_{j i}, D_{i i}=0\right)$ 表示城市 $i$ 与城市 $j$ 之间直接相连 的那条道路的灰尘度。
接下来 $n$ 行, 每行包含 $n$ 个整数, 相邻两个整数之间用一个空格分隔, 其 中第 $i$ 行第 $j$ 列的值 $L_{i j}\left(L_{i j}=L_{j i}, L_{i i}=0\right)$ 表示城市 $i$ 与城市 $j$ 之间直接相连的 那条道路的灰尘度的下限值。
输出格式
输出一行包含一个整数表示答条。
样例输入
1 | |
样例输出
1 | |
评测用例规模与约定
对于 $30 %$ 的评测用例, $1 \leq n \leq 10 ， 0 \leq L_{i j} \leq D_{i j} \leq 10$ ；
对于 $60 %$ 的评测用例, $1 \leq n \leq 50 ， 0 \leq L_{i j} \leq D_{i j} \leq 100000$;
对于所有评测用例, $1 \leq n \leq 100,0 \leq L_{i j} \leq D_{i j} \leq 100000,0 \leq Q \leq 2^{31}-1$ 。
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 10s | 512M |
| C | 10s | 512M |
| Python3 | 10s | 512M |
| Java | 10s | 512M |
刷题统计
问题描述
小明决定从下周一开始努力刷题准备蓝桥杯竞赛。他计划周一至周五每天 做 $a$ 道题目, 周六和周日每天做 $b$ 道题目。请你帮小明计算, 按照计划他将在 第几天实现做题数大于等于 $n$ 题?
输入格式
输入一行包含三个整数 $a, b$ 和 $n$.
输出格式
输出一个整数代表天数。
样例输入
1 | |
样例输出
1 | |
评测用例规模与约定
对于 $50 %$ 的评测用例, $1 \leq a, b, n \leq 10^{6}$.
对于 $100 %$ 的评测用例, $1 \leq a, b, n \leq 10^{18}$.
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 1s | 256M |
| C | 1s | 256M |
| Python3 | 1s | 256M |
| Java | 1s | 256M |
快速幂
题目描述
输入 $b，p，k$ 的值，求 $b^p \mod k$ 的值。其中 $2 \leq b,p,k \leq 10^9$ 。
输入描述
三个整数 $b,p,k$。
输出描述
输出 $b^p \mod k=s$，$s$ 为运算结果。
输入输出样例
示例
输入
1 | |
输出
1 | |
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 1s | 128M |
| C | 1s | 128M |
| Python3 | 1s | 128M |
| Java | 1s | 128M |
核桃的数量
题目描述
小张是软件项目经理，他带领 3 个开发组。工期紧，今天都在加班呢。为鼓舞士气，小张打算给每个组发一袋核桃（据传言能补脑）。他的要求是：
各组的核桃数量必须相同
各组内必须能平分核桃（当然是不能打碎的）
尽量提供满足 1,2 条件的最小数量（节约闹革命嘛）
输入描述
输入一行 $a,b,c$，都是正整数，表示每个组正在加班的人数，用空格分开$(a,b,c<30)$。
输出描述
输出一个正整数，表示每袋核桃的数量。
输入输出样例
示例
输入
1 | |
输出
1 | |
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 1s | 64M |
| C | 1s | 64M |
| Python3 | 1s | 64M |
| Java | 1s | 64M |
质数
题目描述
给定一个正整数 $N$，请你输出 $N$ 以内（不包含 $N$）的质数以及质数的个数。
输入描述
输入一行，包含一个正整数 $N$。 $1\leq N \leq 10^3$
输出描述
共两行。
第 $1$ 行包含若干个素数，每两个素数之间用一个空格隔开，素数从小到大输出。
第 $2$ 行包含一个整数，表示N以内质数的个数。
输入输出样例
示例
输入
1 | |
输出
1 | |
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 1s | 128M |
| C | 1s | 128M |
| Python3 | 1s | 128M |
| Java | 1s | 128M |
分割立方体
题目描述
给定一个立方体，边长为 $n$，现将其分割成 $n×n×n$ 个单位立方体。
分割后任意两个单位立方体，或者有 $2$ 个公共点，或者有 $4$ 个公共点，或者没有公共点。
请问，没有公共点和有 $2$ 个公共点的立方体，共有多少对？
输入描述
输入一行包含一个整数 $n(1\leq n \leq 30)$。
输出描述
输出一个整数表示答案。
输入输出样例
示例1
输入
1 | |
输出
1 | |
示例2
输入
1 | |
输出
1 | |
示例3
输入
1 | |
输出
1 | |
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 1s | 256M |
| C | 1s | 256M |
| Python3 | 1s | 256M |
| Java | 1s | 256M |
糊涂人寄信
题目描述
有一个糊涂人，写了 $n$ 封信和 $n$ 个信封，到了邮寄的时候，把所有的信都装错了信封。求装错信封可能的种类数。
输入描述
有多行读入，每行输入一个正整数 $n$，表示一种情况。($n\leq 20$)
输出描述
输出相应的答案。
输入输出样例
示例
输入
1 | |
输出
1 | |
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 1s | 256M |
| C | 1s | 256M |
| Python3 | 1s | 256M |
| Java | 1s | 256M |
小蓝吃糖果
题目描述
小蓝有 $n$ 种糖果，每种数量已知。
小蓝不喜欢连续 $2$ 次吃同样的糖果。问有没有可行的吃糖方案。
输入描述
第一行是整数 $n(0<n<1000000)$。
第二行包含 $n$ 个数，表示 $n$ 种糖果的数量 $mi$，$0<mi<1000000$。
输出描述
输出一行，包含一个 Yes 或 No。
输入输出样例
示例
输入
1 | |
输出
1 | |
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 1s | 256M |
| C | 1s | 256M |
| Python3 | 1s | 256M |
| Java | 1s | 256M |