第十二届蓝桥杯软件类省赛试题(C/C++大学B组)

发布于 2021-04-18  2307 次阅读


填空部分题解已更新:点击这里前往

剩下的让我再摸会儿鱼o(* ̄▽ ̄*)ブ

试题 A: 空间

本题总分:

【问题描述】

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

【答案提交】

这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。

试题 B: 卡片

本题总分:

【问题描述】

小蓝有很多数字卡片,每张卡片上都是数字 到 9。小蓝准备用这些卡片来拼一些数,他想从 开始拼出正整数,每拼一个,就保存起来,卡片就不能用来拼其它数了。小蓝想知道自己能从 拼到多少。

例如,当小蓝有 30 张卡片,其中 到 各 张,则小蓝可以拼出 到 10,但是拼 11 时卡片 已经只有一张了,不够拼出 11

现在小蓝手里有 到 的卡片各 2021 张,共 20210 张,请问小蓝可以从 1拼到多少?

提示:建议使用计算机编程解决问题。

【答案提交】

这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。

试题 C: 直线

本题总分:10 

【问题描述】

在平面直角坐标系中,两点可以确定一条直线。如果有多点在一条直线上,那么这些点中任意两点确定的直线是同一条。

给定平面上 × 个整点 {(xy)|≤ 2≤ 3∈ Z∈ Z},即横坐标是 到 (包含 和 1之间的整数、纵坐标是 到 (包含 和 2之间的整数的点。这些点一共确定了 11 条不同的直线。

给定平面上 20 × 21 个整点 {(xy)|≤ 20≤ 21∈ Z∈ Z},即横坐标是 到 19 (包含 和 19之间的整数、纵坐标是 到 20 (包含 和 20之间的整数的点。请问这些点一共确定了多少条不同的直线。

【答案提交】

这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。

试题 D: 货物摆放

本题总分:10 

【问题描述】

小蓝有一个超大的仓库,可以摆放很多货物。

现在,小蓝有 箱货物要摆放在仓库,每箱货物都是规则的正方体。小蓝规定了长、宽、高三个互相垂直的方向,每箱货物的边都必须严格平行于长、宽、高。

小蓝希望所有的货物最终摆成一个大的立方体。即在长、宽、高的方向上分别堆 LW的货物,满足 × × H给定 n,请问有多少种堆放货物的方案满足要求。

例如,当 = 4 时,有以下 种方案:× × 4× × 2× × 1× × 2× × 1× × 1

请问,当 = 2021041820210418 (注意有 16 位数字)时,总共有多少种方案?

提示:建议使用计算机编程解决问题。

【答案提交】

这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。

试题 E: 路径

本题总分:15 

【问题描述】

小蓝学习了最短路径之后特别高兴,他定义了一个特别的图,希望找到图中的最短路径。

小蓝的图由 2021 个结点组成,依次编号 至 2021

对于两个不同的结点 ab,如果 和 的差的绝对值大于 21,则两个结点之间没有边相连;如果 和 的差的绝对值小于等于 21,则两个点之间有一条长度为 和 的最小公倍数的无向边相连。

例如:结点 和结点 23 之间没有边相连;结点 和结点 24 之间有一条无向边,长度为 24;结点 15 和结点 25 之间有一条无向边,长度为 75

请计算,结点 和结点 2021 之间的最短路径长度是多少。提示:建议使用计算机编程解决问题。

【答案提交】

这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。

试题 F: 时间显示

时间限制: 1.0s 内存限制: 256.0MB 本题总分:15 

【问题描述】

小蓝要和朋友合作开发一个时间显示的网站。在服务器上,朋友已经获取了当前的时间,用一个整数表示,值为从 1970 年 月 日 00:00:00 到当前时刻经过的毫秒数。

现在,小蓝要在客户端显示出这个时间。小蓝不用显示出年月日,只需要显示出时分秒即可,毫秒也不用显示,直接舍去即可。

给定一个用整数表示的时间,请将这个时间对应的时分秒输出。

【输入格式】

输入一行包含一个整数,表示时间。

【输出格式】

输出时分秒表示的当前时间,格式形如 HH:MM:SS,其中 HH 表示时,值为 0 到 23MM 表示分,值为 到 59SS 表示秒,值为 到 59。时、分、秒不足两位时补前导 0

【样例输入 1

46800999

【样例输出 1

13:00:00

【样例输入 2

1618708103123

【样例输出 2

01:08:23

【评测用例规模与约定】

对于所有评测用例,给定的时间为不超过 1018 的正整数。

试题 G: 砝码称重

时间限制: 1.0s 内存限制: 256.0MB 本题总分:20 

【问题描述】

你有一架天平和 个砝码,这 个砝码重量依次是 W1W2· · · WN。请你计算一共可以称出多少种不同的重量?

注意砝码可以放在天平两边。

【输入格式】

输入的第一行包含一个整数 N

第二行包含 个整数:W1W2W3· · · WN

【输出格式】

输出一个整数代表答案。

【样例输入】

3

1 4 6

【样例输出】

10

【样例说明】

能称出的 10 种重量是:123456791011

1 = 1

2 = 6 − (天平一边放 6,另一边放 4)

3 = 4 − 1

4 = 4

5 = 6 − 1

6 = 6

7 = 1 + 6

9 = 4 + 6 − 1

10 = 4 + 6

11 = 1 + 4 + 6

【评测用例规模与约定】

对于 50的评测用例,≤ ≤ 15

对于所有评测用例,≤ ≤ 100个砝码总重不超过 100000

试题 H: 杨辉三角形

时间限制: 1.0s 内存限制: 256.0MB 本题总分:20 

【问题描述】

下面的图形是著名的杨辉三角形:

:杨辉三角:

如果我们按从上到下、从左到右的顺序把所有数排成一列,可以得到如下数列:

1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 1, ...

给定一个正整数 N,请你输出数列中第一次出现 是在第几个数?

【输入格式】

输入一个整数 N

【输出格式】

输出一个整数代表答案。

【样例输入】

6

【样例输出】

13

【评测用例规模与约定】

对于 20% 的评测用例,≤ ≤ 10

对于所有评测用例,≤ ≤ 1000000000

试题 I: 双向排序

时间限制: 1.0s 内存限制: 256.0MB 本题总分:25 

【问题描述】

给定序列 (a1a2· · · an) = (12· · · n),即 ai i

小蓝将对这个序列进行 次操作,每次可能是将 a1a2· · · aq降序排列,或者将 aqaqi+1· · · an 升序排列。

请求出操作完成后的序列。

【输入格式】

输入的第一行包含两个整数 nm,分别表示序列的长度和操作次数。

接下来 行描述对序列的操作,其中第 行包含两个整数 piqi 表示操作类型和参数。当 pi = 0 时,表示将 a1a2· · · aq降序排列;当 pi = 1 时,表示将 aqaqi+1· · · an 升序排列。

【输出格式】

输出一行,包含 个整数,相邻的整数之间使用一个空格分隔,表示操作完成后的序列。

【样例输入】

3 3

0 3

1 2

0 2

【样例输出】

3 1 2

【样例说明】

原数列为 (123)

第 步后为 (321)

第 步后为 (312)

第 步后为 (312)。与第 步操作后相同,因为前两个数已经是降序了。

【评测用例规模与约定】

对于 30的评测用例,n≤ 1000;对于 60的评测用例,n≤ 5000

对于所有评测用例,≤ n≤ 100000≤ ai ≤ 1≤ bi ≤ n

试题 J: 括号序列

时间限制: 1.0s 内存限制: 256.0MB 本题总分:25 

【问题描述】

给定一个括号序列,要求尽可能少地添加若干括号使得括号序列变得合法,当添加完成后,会产生不同的添加结果,请问有多少种本质不同的添加结果。两个结果是本质不同的是指存在某个位置一个结果是左括号,而另一个是右括号。

例如,对于括号序列 (((),只需要添加两个括号就能让其合法,有以下几种不同的添加结果:()()()()(())(())()(()()) 和 ((()))

【输入格式】

输入一行包含一个字符串 s,表示给定的括号序列,序列中只有左括号和右括号。

【输出格式】

输出一个整数表示答案,答案可能很大,请输出答案除以 1000000007 (

109 + 7的余数。

【样例输入】

((()

【样例输出】

5

【评测用例规模与约定】

对于 40的评测用例,|s| ≤ 200。对于所有评测用例,≤ |s| ≤ 5000