理论卷2022年12月青少年软件编程(C\C++) · 四级

YLT C++ 4级 2022.12

满分 100 · 及格 60 · 时长 60 分钟 · 共 4 题 (编程题4)

试卷阅览 · 免费预览前 10 题 · 交卷后可查看答案与解析

编程题题号 #22381

分值 25

N5469 [CIE 202212 四级 T1] 开餐馆

题目描述

北大信息学院的同学小明毕业之后打算创业开餐馆.现在共有 $n$ 个地点可供选择。小明打算从中选择合适的位置开设一些餐馆。这 $n$ 个地点排列在同一条直线上。我们用一个整数序列 $m_1, m_2, ... m_n$ 来表示他们的相对位置。由于地段关系,开餐馆的利润会有所不同。我们用 $p_i$ 表示在 $m_i$ 处开餐馆的利润。为了避免自己的餐馆的内部竞争,餐馆之间的距离必须大于 $k$ 。请你帮助小明选择一个总利润最大的方案。

输入格式

标准的输入包含若干组测试数据。输入第一行是整数 $T$ $(1 \leq T \leq 1000)$ ，表明有 $T$ 组测试数据。紧接着有 $T$ 组连续的测试。每组测试数据有 $3$ 行, 第 $1$ 行:地点总数 $n$ $(n 0$ && $k mi > 0$ 且为整数,升序排列) 第 $3$ 行: $n$ 个地点的餐馆利润 $p_1 , p_2, ... p_n$ ( $1000 > pi > 0$ 且为整数)

输出格式

对于每组测试数据可能的最大利润

样例

样例 1
输入：

输出：

40
30

提示

无

编程题题号 #22382

分值 25

N5470 [CIE 202212 四级 T2] 糖果

题目描述

由于在维护世界和平的事务中做出巨大贡献， $Dzx$ 被赠予糖果公司 $2010$ 年 $5$ 月 $23$ 日当天无限量糖果免费优惠券。在这一天， $Dzx$ 可以从糖果公司的 $N$ 件产品中任意选择若干件带回家享用。糖果公司的 $N$ 件产品每件都包含数量不同的糖果。 $Dzx$ 希望他选择的产品包含的糖果总数是 $K$ 的整数倍，这样他才能平均地将糖果分给帮助他维护世界和平的伙伴们。当然，在满足这一条件的基础上，糖果总数越多越好。 $Dzx$ 最多能带走多少糖果呢？注意： $Dzx$ 只能将糖果公司的产品整件带走。

输入格式

第一行包含两个整数 $N(1\leq N\leq 100)$ 和 $K(1\leq K\leq 100)$ 以下 $N$ 行每行 $1$ 个整数，表示糖果公司该件产品中包含的糖果数目，不超过 $1000000$

输出格式

符合要求的最多能达到的糖果总数，如果不能达到 $K$ 的倍数这一要求，输出 $0$

样例

样例 1
输入：

输出：

提示

$Dzx$ 的选择是 $2+3+4+5=14$ ，这样糖果总数是 $7$ 的倍数，并且是总数最多的选择。

编程题题号 #22383

分值 25

N5471 [CIE 202212 四级 T3] 鸡蛋的硬度

题目描述

最近 $\text{XX}$ 公司举办了一个奇怪的比赛：鸡蛋硬度之王争霸赛。参赛者是来自世界各地的母鸡，比赛的内容是看谁下的蛋最硬，更奇怪的是 $\text{XX}$ 公司并不使用什么精密仪器来测量蛋的硬度，他们采用了一种最老土的办法--从高度扔鸡蛋--来测试鸡蛋的硬度，如果一次母鸡下的蛋从高楼的第 $a$ 层摔下来没摔破，但是从 $a+1$ 层摔下来时摔破了，那么就说这只母鸡的鸡蛋的硬度是 $a$ 。你当然可以找出各种理由说明这种方法不科学，比如同一只母鸡下的蛋硬度可能不一样等等，但是这不影响 $\text{XX}$ 公司的争霸赛，因为他们只是为了吸引大家的眼球，一个个鸡蛋从 $100$ 层的高楼上掉下来的时候，这情景还是能吸引很多人驻足观看的，当然， $\text{XX}$ 公司也绝不会忘记在高楼上挂一条幅，写上“ $\text{XX}$ 公司”的字样--这比赛不过是 $\text{XX}$ 公司的一个另类广告而已。
勤于思考的小 $A$ 总是能从一件事情中发现一个数学问题，这件事也不例外。“假如有很多同样硬度的鸡蛋，那么我可以用二分的办法用最少的次数测出鸡蛋的硬度”，小 $A$ 对自己的这个结论感到很满意，不过很快麻烦来了，“但是，假如我的鸡蛋不够用呢，比如我只有 $1$ 个鸡蛋，那么我就不得不从第 $1$ 层楼开始一层一层的扔，最坏情况下我要扔 $100$ 次。如果有 $2$ 个鸡蛋，那么就从 $2$ 层楼开始的地方扔……等等，不对，好像应该从 $1/3$ 的地方开始扔才对，嗯，好像也不一定啊…… $3$ 个鸡蛋怎么办， $4$ 个， $5$ 个，更多呢……”，和往常一样，小 $A$ 又陷入了一个思维僵局，与其说他是勤于思考，不如说他是喜欢自找麻烦。
好吧，既然麻烦来了，就得有人去解决，小 $A$ 的麻烦就靠你来解决了：）

输入格式

输入包括多组数据，每组数据一行，包含两个正整数 $n$ 和 $m$ $(1\leq n\leq 100,1\leq m\leq 10)$ ，其中 $n$ 表示楼的高度， $m$ 表示你现在拥有的鸡蛋个数，这些鸡蛋硬度相同（即它们从同样高的地方掉下来要么都摔碎要么都不碎），并且小于等于 $n$ 。你可以假定硬度为 $x$ 的鸡蛋从高度小于等于 $x$ 的地方摔无论如何都不会碎（没摔碎的鸡蛋可以继续使用），而只要从比 $x$ 高的地方扔必然会碎。对每组输入数据，你可以假定鸡蛋的硬度在 $0$ 至 $n$ 之间，即在 $n+1$ 层扔鸡蛋一定会碎。

输出格式

对于每一组输入，输出一个整数，表示使用最优策略在最坏情况下所需要的扔鸡蛋次数

样例

样例 1
输入：

100 1
100 2

输出：

100
14

提示

最优策略指在最坏情况下所需要的扔鸡蛋次数最少的策略。如果只有一个鸡蛋，你只能从第一层开始扔，在最坏的情况下，鸡蛋的硬度是 $100$ ，所以需要扔 $100$ 次。如果采用其他策略，你可能无法测出鸡蛋的硬度(比如你第一次在第二层的地方扔,结果碎了,这时你不能确定硬度是 $0$ 还是 $1$ )，即在最坏情况下你需要扔无限次，所以第一组数据的答案是 $100$ 。

编程题题号 #22384

分值 25

N5472 [CIE 202212 四级 T4] 山区建小学

题目描述

政府在某山区修建了一条道路，恰好穿越总共 $m$ 个村庄的每个村庄一次，没有回路或交叉，任意两个村庄只能通过这条路来往。已知任意两个相邻的村庄之间的距离为 $d_i$ （为正整数），其中， $0 < i < m$ 。为了提高山区的文化素质，政府又决定从 $m$ 个村中选择 $n$ 个村建小学（设 $0 < n \leq m < 500$ ）。请根据给定的 $m$ 、 $n$ 以及所有相邻村庄的距离，选择在哪些村庄建小学，才使得所有村到最近小学的距离总和最小，计算最小值。

输入格式

第 $1$ 行为 $m$ 和 $n$ ，其间用空格间隔第 $2$ 行为 $(m-1)$ 个整数，依次表示从一端到另一端的相邻村庄的距离，整数之间以空格间隔。例如 $10\ 3\ 2\ 4\ 6\ 5\ 2\ 4\ 3\ 1\ 3$ 表示在 $10$ 个村庄建 $3$ 所学校。第 $1$ 个村庄与第 $2$ 个村庄距离为 $2$ ，第 $2$ 个村庄与第 $3$ 个村庄距离为 $4$ ，第 $3$ 个村庄与第 $4$ 个村庄距离为 $6$ ，...，第 $9$ 个村庄到第 $10$ 个村庄的距离为 $3$ 。

输出格式

各村庄到最近学校的距离之和的最小值。

样例

样例 1
输入：

10 2
3 1 3 1 1 1 1 1 3

输出：

提示

无