Java 大学 B 组
【考生须知】 考试开始后,选手首先下载题目,并使用考场现场公布的解压密码解压试 题。 考试时间为 4 小时。考试期间选手可浏览自己已经提交的答案,被浏览的 答案允许拷贝。时间截止后,将无法继续提交或浏览答案。 对同一题目,选手可多次提交答案,以最后一次提交的答案为准。 选手必须通过浏览器方式提交自己的答案。选手在其它位置的作答或其它 方式提交的答案无效。 试题包含“结果填空”和“程序设计”两种题型。 结果填空题:要求选手根据题目描述直接填写结果。求解方式不限。不要 求源代码。把结果填空的答案直接通过网页提交即可,不要书写多余的内容。 程序设计题:要求选手设计的程序对于给定的输入能给出正确的输出结果。 考生的程序只有能运行出正确结果才有机会得分。 注意:在评卷时使用的输入数据与试卷中给出的示例数据可能是不同的。 选手的程序必须是通用的,不能只对试卷中给定的数据有效。 所有源码必须在同一文件中。调试通过后,拷贝提交。 注意:不要使用 package 语句。 注意:选手代码的主类名必须为:Main,否则会被判为无效代码。 注意:如果程序中引用了类库,在提交时必须将 import 语句与程序的其 他部分同时提交。只允许使用 Java 自带的类库。
试题 A: 星期计算本题总分:5 分
【问题描述】
已知今天是星期六,请问 2022 天后是星期几? 注意用数字 1 到 7 表示星期一到星期日。
【答案提交】 这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一 个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。
试题 B: 山本题总分:5 分
【问题描述】
这天小明正在学数数。 他突然发现有些正整数的形状像一座“山”,比如 123565321、145541,它 们左右对称(回文)且数位上的数字先单调不减,后单调不增。 小明数了很久也没有数完,他想让你告诉他在区间 [2022, 2022222022] 中有多少个数的形状像一座“山”。
【答案提交】 这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一 个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。
试题 C: 字符统计时间限制: 1.0s 内存限制: 512.0MB 本题总分:10 分
【问题描述】
给定一个只包含大写字母的字符串 S,请你输出其中出现次数最多的字母。 如果有多个字母均出现了最多次,按字母表顺序依次输出所有这些字母。
【输入格式】
一个只包含大写字母的字符串 S【输出格式】
若干个大写字母,代表答案。【样例输入】
BABBACAC【样例输出】
AB【评测用例规模与约定】
对于 100% 的评测用例,1 ≤ |S | ≤ 106 试题 D: 最少刷题数时间限制: 1.0s 内存限制: 512.0MB 本题总分:10 分
【问题描述】
小蓝老师教的编程课有 N 名学生,编号依次是 1 . . . N。第 i 号学生这学期 刷题的数量是 Ai。 对于每一名学生,请你计算他至少还要再刷多少道题,才能使得全班刷题 比他多的学生数不超过刷题比他少的学生数。
【输入格式】
第一行包含一个正整数 N。第二行包含 N 个整数:A1, A2, A3, . . . , AN.【输出格式】
输出 N 个整数,依次表示第 1 . . . N 号学生分别至少还要再刷多少道题。【样例输入】
5 12 10 15 20 6【样例输出】
0 3 0 0 7【评测用例规模与约定】
对于 30% 的数据,1 ≤ N ≤ 1000, 0 ≤ Ai ≤ 1000. 对于 100% 的数据,1 ≤ N ≤ 100000, 0 ≤ Ai ≤ 100000. 试题 E: 求阶乘时间限制: 1.0s 内存限制: 512.0MB 本题总分:15 分
【问题描述】
满足 N! 的末尾恰好有 K 个 0 的最小的 N 是多少? 如果这样的 N 不存在输出 −1。
【输入格式】
一个整数 K。【输出格式】
一个整数代表答案。【样例输入】
2【样例输出】
10【评测用例规模与约定】
对于 30% 的数据,1 ≤ K ≤ 106 对于 100% 的数据,1 ≤ K ≤ 1018 试题 F: 最大子矩阵时间限制: 1.0s 内存限制: 512.0MB 本题总分:15 分
【问题描述】
小明有一个大小为 N × M 的矩阵,可以理解为一个 N 行 M 列的二维数组。 我们定义一个矩阵 m 的稳定度 f(m) 为 f(m) = max(m) − min(m),其中 max(m) 表示矩阵 m 中的最大值,min(m) 表示矩阵 m 中的最小值。现在小明想要从这个矩阵中找到一个稳定度不大于 limit 的子矩阵,同时他还希望这个子矩阵的面 积越大越好(面积可以理解为矩阵中元素个数)。 子矩阵定义如下:从原矩阵中选择一组连续的行和一组连续的列,这些行 列交点上的元素组成的矩阵即为一个子矩阵。
【输入格式】
第一行输入两个整数 N,M,表示矩阵的大小。 接下来 N 行,每行输入 M 个整数,表示这个矩阵。 最后一行输入一个整数 limit,表示限制。【输出格式】
输出一个整数,分别表示小明选择的子矩阵的最大面积。【样例输入】
3 4 2 0 7 9 0 6 9 7 8 4 6 4 8【样例输出】
6【样例说明】
满足稳定度不大于 8 的且面积最大的子矩阵总共有三个,他们的面积都是 6(粗体表示子矩阵元素): 2 0 7 9 0 6 9 7 8 4 6 4 2 0 7 9 0 6 9 7 8 4 6 4 2 0 7 9 0 6 9 7 8 4 6 4【评测用例规模与约定】
评测用例编号 N M 1, 2 1 ≤ N ≤ 10 1 ≤ M ≤ 10 3, 4 N = 1 M ≤ 100000 5 ∼ 12 1 ≤ N ≤ 10 M ≤ 10000 13 ∼ 20 1 ≤ N ≤ 80 1 ≤ M ≤ 80 对于所有评测用例,0 ≤ 矩阵元素值, limit ≤ 105。 试题 G: 数组切分时间限制: 1.0s 内存限制: 512.0MB 本题总分:20 分
【问题描述】
已知一个长度为 N 的数组:A1, A2, A3, …AN 恰好是 1 ∼ N 的一个排列。现 在要求你将 A 数组切分成若干个 (最少一个,最多 N 个) 连续的子数组,并且 每个子数组中包含的整数恰好可以组成一段连续的自然数。 例如对于 A = {1, 3, 2, 4}, 一共有 5 种切分方法: {1}{3}{2}{4}:每个单独的数显然是 (长度为 1 的) 一段连续的自然数。 {1}{3,2}{4}:{3, 2} 包含 2 到 3,是 一段连续的自然数,另外 {1} 和 {4} 显然 也是。 {1}{3, 2, 4}:{3,2, 4} 包含 2 到 4,是 一段连续的自然数,另外 {1} 显然也是。 {1, 3, 2}{4}:{1, 3, 2} 包含 1 到3,是 一段连续的自然数,另外 {4} 显然也是。 {1, 3, 2, 4}:只有一个子数组,包含 1 到 4,是 一段连续的自然数。
【输入格式】
第一行包含一个整数 N。第二行包含 N 个整数,代表 A 数组。【输出格式】
输出一个整数表示答案。由于答案可能很大,所以输出其对 1000000007 取 模后的值【样例输入】
4 1 3 2 4【样例输出】
5【评测用例规模与约定】
对于 30% 评测用例,1 ≤ N ≤ 20. 对于 100% 评测用例,1 ≤ N ≤ 10000. 试题 H: 回忆迷宫时间限制: 1.0s 内存限制: 512.0MB 本题总分:20 分
【问题描述】
爱丽丝刚从一处地下迷宫中探险归来,你能根据她对于自己行动路径的回 忆,帮她画出迷宫地图吗? 迷宫地图是基于二维网格的。爱丽丝会告诉你一系列她在迷宫中的移动步 骤,每个移动步骤可能是上下左右四个方向中的一种,表示爱丽丝往这个方向 走了一格。你需要根据这些移动步骤给出一个迷宫地图,并满足以下条件: 1、爱丽丝能在迷宫内的某个空地开始,顺利的走完她回忆的所有移动步 骤。 2、迷宫内不存在爱丽丝没有走过的空地。 3、迷宫是封闭的,即可通过墙分隔迷宫内与迷宫外。任意方向的无穷远处 视为迷宫外,所有不与迷宫外联通的空地都视为是迷宫内。(迷宫地图为四联 通,即只有上下左右视为联通) 4、在满足前面三点的前提下,迷宫的墙的数量要尽可能少。
【输入格式】
第一行一个正整数 N,表示爱丽丝回忆的步骤数量。 接下来一行 N 个英文字符,仅包含 UDLR 四种字符,分别表示上(Up)、 下(Down)、左(Left)、右(Right)。【输出格式】
请通过字符画的形式输出迷宫地图。迷宫地图可能包含许多行,用字符 ‘*’ 表示墙,用 ‘ ’(空格)表示非墙。 你的输出需要保证以下条件: 1、至少有一行第一个字符为 ‘*’。 2、第一行至少有一个字符为 ‘*’。 3、每一行的最后一个字符为 ‘*’。 4、最后一行至少有一个字符为 ‘*’。【样例输入】
17 UUUULLLLDDDDRRRRU【样例输出】
***** * * * *** * * *** * * *** * * * *****【样例说明】
爱丽丝可以把第六行第六个字符作为起点。 外墙墙墙墙墙外 墙内内内内内墙 墙内墙墙墙内墙 墙内墙墙墙内墙 墙内墙墙墙内墙 墙内内内内内墙 外墙墙墙墙墙外【评测用例规模与约定】
对于所有数据,0 < N ≤ 100. 试题 I: 红绿灯时间限制: 1.0s 内存限制: 512.0MB 本题总分:25 分
【问题描述】
爱丽丝要开车去上班,上班的路上有许多红绿灯,这让爱丽丝很难过。为 了上班不迟到,她给自己的车安装了氮气喷射装置。现在她想知道自己上班最短需要多少时间。 爱丽丝的车最高速度是 1 V 米每秒,并且经过改装后,可以瞬间加速到小于 等于最高速的任意速度,也可以瞬间停止。 爱丽丝家离公司有 N 米远,路上有 M 个红绿灯,第 i 个红绿灯位于离爱丽丝家 Ai 米远的位置,绿灯持续 Bi 秒,红灯持续 Ci 秒。在初始时(爱丽丝开 始计时的瞬间),所有红绿灯都恰好从红灯变为绿灯。如果爱丽丝在绿灯变红的瞬间到达红绿灯,她会停下车等红灯,因为她是遵纪守法的好市民。 氮气喷射装置可以让爱丽丝的车瞬间加速到超光速(且不受相对论效应的影响!),达到瞬移的效果,但是爱丽丝是遵纪守法的好市民,在每个红绿灯前 她都会停下氮气喷射,即使是绿灯,因为红绿灯处有斑马线,而使用氮气喷射装置通过斑马线是违法的。此外,氮气喷射装置不能连续启动,需要一定时间 的冷却,表现为通过 K 个红绿灯后才能再次使用。(也就是说,如果 K= 1,就能一直使用啦!)初始时,氮气喷射装置处于可用状态。
【输入格式】
第一行四个正整数 N、M、K、V,含义如题面所述。 接下来 M 行,每行三个正整数 Ai、Bi、Ci,含义如题面所述。【输出格式】
输出一个正整数 T,表示爱丽丝到达公司最短需要多少秒。【样例输入】
90 2 2 2 30 20 20 60 20 20【样例输出】
80【样例说明】
爱丽丝在最开始直接使用氮气喷射装置瞬间到达第一个红绿灯,然后绿灯通过, 以最高速行进 60 秒后到达第二个红绿灯,此时绿灯刚好变红,于是她等待20 秒再次变为绿灯后通过该红绿灯,此时氮气喷射装置冷却完毕,爱丽丝再次使用 瞬间到达公司,总共用时 80 秒。【评测用例规模与约定】
对于 30% 的数据,N ≤ 100; M ≤ 10; M < K; V = 1. 对于 60% 的数据,N ≤ 1000; M ≤ 100; K ≤ 50; Bi,Ci ≤ 100; V ≤ 10. 对于 100% 的数据,0 < N ≤ 10的8次方; M ≤ 1000; K ≤ 1000; 0 < Bi, Ci ≤ 10的6次方; 0