第十二届蓝桥杯填空题

第十二届蓝桥杯填空题

版权
目录

空间

卡片

直线

路径

空间
问题描述：

小蓝准备用 256MB 的内存空间开一个数组，数组的每个元素都是 32 位二进制整数，如果不考虑程序占用的空间和维护内存需要的辅助空间，请问256MB 的空间可以存储多少个 32 位二进制整数？

思路分析：

先将MB转换为字节Byte，也就是Byte（B），1MB = 1024KB， 1KB = 1024B，1B = 8bit（位）所以256 MB = 256 * 1024 * 1024B，32位二进制整数的存储空间也即32bit = 32 / 8 = 4B，所以可以存在 256 * 1024 * 1024 / 4，使用程序计算出结果为：67108864

if __name__ == ‘__main__’:
print(256 * 1024 * 1024 // 4)
卡片
问题描述：小蓝有很多数字卡片，每张卡片上都是数字 0 到 9。小蓝准备用这些卡片来拼一些数，他想从 1 开始拼出正整数，每拼一个，就保存起来，卡片就不能用来拼其它数了。小蓝想知道自己能从 1 拼到多少。例如，当小蓝有 30 张卡片，其中 0 到 9 各 3 张，则小蓝可以拼出 1 到 10，但是拼 11 时卡片 1 已经只有一张了，不够拼出 11。现在小蓝手里有 0 到 9 的卡片各 2021 张，共 20210 张，请问小蓝可以从1拼到多少？提示：建议使用计算机编程解决问题。

思路分析：

分析题目可以知道模拟整个过程即可，我们可以使用一个循环，只要可以拼出当前的数字i那么循环继续，否则break输出i – 1（本来是送分题在比赛的时候不知道啥情况模拟这个过程还是算错了），使用一个方法check来检查当前数字i是否可以拼出即可，使用check方法来检查会比较保险，我可能在一开始的时候没有使用方法来检查导致所有代码写在一起错了。答案为3181。

cards = [2021] * 10

# 检查当前的数字n是否是拼出来
def check(n: int):
while n:
t = n % 10
if cards[t] – 1 < 0: return False
cards[t] -= 1
n //= 10
return True

if __name__ == ‘__main__’:
i = 1
while True:
if check(i):
i += 1
else:
print(i – 1)
break
直线
问题描述：

在平面直角坐标系中，两点可以确定一条直线。如果有多点在一条直线上，那么这些点中任意两点确定的直线是同一条。给定平面上 2 × 3 个整点 {(x,y)|0 ≤ x < 2; 0 ≤ y < 3; ，即横坐标是 0 到 1 (包含 0 和 1) 之间的整数、纵坐标是 0 到 2 (包含 0 和 2) 之间的整数的点。这些点一共确定了 11 条不同的直线。给定平面上 20 × 21 个整点 {(x,y)|0 ≤ x < 20; 0 ≤ y < 21; ，即横坐标是 0 到 19 (包含 0 和 19) 之间的整数、纵坐标是 0 到 20 (包含 0 和 20) 之间的整数的点。请问这些点一共确定了多少条不同的直线？

思路分析：

一开始的是没有想出来，其实可以枚举所有可能的点的坐标，计算两点确定的直线斜率k与截距b，因为使用的是python语言，所以可以将k,b作为元组（k,b确定的就是一条直线）存储到列表中，然后对列表进行排序，先对斜率排序，斜率相同对截距排序，因为浮点数在存储的时候是有误差的所以需要判断两条直线的斜率或者截距大于1e-8那么判定为不同的直线。答案为：40257

if __name__ == ‘__main__’:
# 使用列表中元组作为元素这样方便后面方便排序
lines = list()
for x1 in range(20):
for y1 in range(21):
for x2 in range(20):
for y2 in range(21):
# x1 == x2的时候斜率不存在
if x1 != x2:
k = (y2 – y1) / (x2 – x1)
b = y1 – k * x1
lines.append((k, b))
# lambda表达式规定先对元组的*个元素斜率k排序, k相同那么则对b排序
lines.sort(key=lambda x: (x[0], x[1]))
# 循环中是从第二条直线开始的
res = 1
for i in range(1, len(lines)):
# 误差大于1e-8判定为不是同一条直线
if lines[i][0] – lines[i – 1][0] > 10 ** -8 or lines[i][1] – lines[i – 1][1] > 10 ** -8:
res += 1
# 加上斜率不存在的20条直线
print(res + 20)
路径
问题描述：

小蓝学习了*短路径之后特别高兴，他定义了一个特别的图，希望找到图中的*短路径。小蓝的图由 2021 个结点组成，依次编号 1 至 2021。对于两个不同的结点 a, b，如果 a 和 b 的差的*对值大于 21，则两个结点之间没有边相连；如果 a 和 b 的差的*对值小于等于 21，则两个点之间有一条长度为 a 和 b 的*小公倍数的无向边相连。例如：结点 1 和结点 23 之间没有边相连；结点 3 和结点 24 之间有一条无向边，长度为 24；结点 15 和结点 25 之间有一条无向边，长度为 75。请计算，结点 1 和结点 2021 之间的*短路径长度是多少。
提示：建议使用计算机编程解决问题。

思路分析：

① 分析题目可以知道我们就可以将节点的边看成是有向边，我们要求解的是从起点1到终点2021的*短路径，所以本质上求解的是*短路径，使用dijkstra算法或者是spfa算法都可以求解，下面使用spfa算法求解单源*短路径，可以知道题目没有任何限制条件所以直接使用spfa算法模板求解接即可（*短路径的裸题）。首先需要创建图，因为使用的是python语言所以使用字典来构建图，键表示顶点，值为列表类型，将顶点能够到达的终点以及对应的权重作为元组的元素添加到字典键对应的列表中即可。创建图之后接下来使用spfa算法的模板即可。

import collections
import sys

# 求解*大公约数
def gcd(a: int, b: int):
while b:
a, b = b, a % b
return a

if __name__ == ‘__main__’:
# 使用spfa单源路径进行求解
# 首先是建图, 看成是有向图
graph = collections.defaultdict(list)
n = 2100
for i in range(1, 2022):
for j in range(i + 1, 2022):
if abs(i – j) <= 21:
# 权重为两个顶点的*小公倍数, 即为两个数相乘除以他们的*大公约数
w = i * j // gcd(i, j)
# 构建当前顶点对应的终点以及边的权重
graph[i].append((j, w))
queue = collections.deque()
s = 1
queue.append(s)
dis = [sys.maxsize] * (n + 1)
dis[s] = 0
used = [0] * (n + 1)
used[s] = 1
while queue:
cur = queue.popleft()
used[cur] = 0
for next in graph[cur]:
if dis[cur] + next[1] < dis[next[0]]:
dis[next[0]] = dis[cur] + next[1]
if used[next[0]] == 0:
used[next[0]] = 1
queue.append(next[0])
print(dis[2021])
② 上面的*短路径还是很容易看出来的，而且题目中求解的问题就是*短路径，除了*短路径算法我们还可以使用动态规划的思路求解。这道题目有点类似于多叉树，从起点出发有很多条路径到达下一个顶点，我们每到达一个顶点那么计算从之前的顶点到达当前顶点的*短路径从而每一次都更新节点的*短距离，这样通过一步步的递推一直到第2021个顶点。

import sys

# 求解*大公约数
def gcd(a: int, b: int):
while b:
a, b = b, a % b
return a

if __name__ == ‘__main__’:
dis = [sys.maxsize] * 2100
dis[1] = 0
for i in range(2, 2022):
for j in range(1, i):
if abs(i – j) <= 21:
# 看成是有向边, 从当前节点之前的节点来更新到达当前节点的*短路径
dis[i] = min(dis[i], dis[j] + i * j // gcd(i, j))
print(dis[2021])