2023合肥蜀山区小学组

连续字符(char)

题目描述

输入格式

输出格式

样例

输入数据#1

输出数据#1

解释#1

输入数据#2

输出数据#2

输入数据#3

输出数据#3

解释#3

数据范围

寻找座位(seat)

题目描述

输入格式

输出格式

样例

输入数据#1

输出数据#1

解释#1

数据范围

限速路段(road)

题目描述

输入格式

输出格式

样例

输入数据#1

输出数据#1

解释#1

输入数据#2

输出数据#2

解释#2

输入数据#3

输出数据#3

解释#3

输入数据#4

输出数据#4

解释#4

数据范围

观展排队(queue)

题目描述

输入格式

输出格式

样例

输入数据#1

输出数据#1

解释#1

输入数据#2

输出数据#2

解释#2

数据范围

本题请以文件输入输出方式进行提交，输入输出文件名是 char.in / char.out

连续字符(char)

题目描述

为了吸引参观者，负责园博会信息化展厅建设的小明设计了一个互动节目，参观者找到屏幕上按字典顺序连续的字符串会有礼品，礼品价值和字符长度成正比。例如，ABC 是按字典顺序连续的字符串，而 AAB 和 ABD 都不是。屏幕上的字符串已经将所有字符排序，现在请你找出它的最长字典顺序连续子串。这里，子串指的是字符串的一部分，例如 D、AB、ABD 都是 ABD 的子串。

输入格式

第一行是 11 个整数 N，表示字符串的长度。

之后一行一个仅包括大写字母的字符串。

输出格式

输出按字典顺序连续的最长子串长度。

样例

输入数据#1

3
ABG

输出数据#1

解释#1

子串 AB 是按字典顺序连续的，且没有比它更长的符合题意的子串。

输入数据#2

5
KLMPQ

输出数据#2

输入数据#3

18
ACDEGHIKNOPQSTUWYZ

输出数据#3

解释#3

一个长度为 44 且按字典顺序连续的子串是 NOPQ。没有比它更长的符合题意的子串。

数据范围

对于全部数据，有 1≤N≤26，输入串的字符不重复并且已按字典顺序排序。
测试点 1∼6（共 60 分）：N≤5。
测试点 7∼10（共40 分）：无特殊限制。

寻找座位(seat)

本题请以文件输入输出方式进行提交，输入输出文件名是 seat.in / seat.out

题目描述

园博会的展区面积很大，接驳不同展区间的电动车需要提前预约，参观者凭成功预约信息才能坐车。因此发车前会进行频繁的订票/退票操作。现在有一辆特殊电动车，里面有 N 排，每排 5 个座位，每个座位用 1 表示已预订，0 表示未预订。小明负责安排这辆车下一趟的座位，按时间顺序收到了M 个订票（D）或者退票（T）信息，请你帮小明编写程序，看剩余座位是否能满足每一个要求。

输入格式

第一行是两个正整数 N 和 M，N 表示园博会电动车上的座位排数，M 表示系统收到的订/退票信息。

接下来是 N 行，每行 5 个数字，表示座位是否被占用，0 表示未被占用，1 表示已经占用。

N 行座位信息后是 M 行订票/退票操作，其中 D 表示订票、T 表示退票。

输出格式

针对 M 个订票/退票操作，按顺序给出座位是否能满足需求的判断结果，Yes 表示可以满足要求，No 表示不能满足。

样例

输入数据#1

输出数据#1

Yes
Yes
No
Yes

解释#1

满足了前两个需求后，不再有足够的座位满足第三个需求。第三个需求应该被拒绝并忽略其影响。

数据范围

对于全部数据，有 1≤N≤1000，1≤M≤105，1≤ 单次订退票数量≤10000。
测试点 1∼3（共 30 分）：保证一开始车辆为空（没有座位被占用）。
测试点4∼10（共 70 分）：无特殊限制。

限速路段(road)

本题请以文件输入输出方式进行提交，输入输出文件名是 road.in / road.out

题目描述

园博会的某路段上有 N 个路牌，相邻两个路牌之间间隔 1010 千米，这些路牌将这个路段划分为等间距的 N−1 个区间。路牌有两种类型：

(1)限速，接下来的全部区间的速度都不能超过标识值；
(2)取消限速，取消最近的一个与标识值相同的限速。其中，限速路牌用正整数表示，取消限速路牌用负整数表示，其真实标识值等于输入数据的绝对值。例如，60 表示限速 60 的路牌，而 −60 表示取消限速 60 的路牌。

假设车辆在通过路牌的瞬间可以立即变速，那么通过此路段且不违反限速的最短用时是多少？多个限速同时生效时，车辆的速度应不超过有效的最低限速。

本题中速度单位均为千米每小时。

输入格式

输入的第 11 行包含 22 个整数N,M，依次表示路牌的数量和车辆的最高时速。

接下来 11 行 N 个整数，按顺序表示遇到的路牌。

输出格式

输出 11 行 11 个数，表示答案。保留两位小数输出。

样例

输入数据#1

5 100
10 -10 30 20 40

输出数据#1

1.93

解释#1

在第 1 个区间速度 10，用时 1；第 2 个区间速度 100，用时 0.1；第 3 个区间速度 30，用时1/3；第 4 个区间速度 20，用时0.5。

输入数据#2

6 100
40 40 -40 30 30 30

输出数据#2

1.42

解释#2

在第 3 个区间，取消了一个限速 40，但还有另一个限速40 生效，因此速度仍然为 40。

输入数据#3

4 100
10 40 -40 1

输出数据#3

3.00

解释#3

在第 3 个区间，取消了限速 40，但限速10 仍然生效。车辆在最后一块路牌停下，因此最后一块路牌的指示没有影响。

输入数据#4

4 100
50 40 -40 1

输出数据#4

0.65

解释#4

在第 3 个区间，取消了限速 40，但限速 50 仍然生效。

数据范围

对于全部数据，有1≤N≤105，1≤M≤100，−100≤ 路牌数值 ≤100。输入数据中不含有0。
测试点 1∼4（共 40 分）：N≤4000。
测试点5∼10（共 60 分）：无特殊限制。
备注：本题使用双精度浮点型double求和并保留小数。

观展排队(queue)

本题请以文件输入输出方式进行提交，输入输出文件名是 queue.in / queue.out

题目描述

园博会吸引了很多参观者，为了保证参观质量，小明负责控制每个展区的人数，暂时无法入馆的参观者需要排队等候。小明为排队的参观者设计了一个小游戏，规则如下：

假定现在有 N 位参观者排成一列，将他们从左往右编号为 1 至 N。如果两位参观者i,j(i<j) 中间的每位参观者的身高都低于 i,j 的身高，就认为 i,j 可以互相看见。互相看到的两人可以获得一个徽章，请你编写程序帮小明计算：队列中有多少对参观者可以互相看见，便于小明发放徽章。

输入格式

输入的第 11 行包含 11 个整数 N，表示队列中的人数。

接下来 11 行 N 个整数，第 i 个数表示参观者 i 的身高。

输出格式

输出 11 行 11 个整数，表示答案。

样例

输入数据#1

4
175 160 180 165

输出数据#1

解释#1

(1,2) (2,3) (3,4) (1,3)(1,2) (2,3) (3,4) (1,3) 可以互相看见。

输入数据#2

5
10 20 30 20 10

输出数据#2

解释#2

尽管参观者 33 能够看见参观者 11，但是参观者 11 不能看见参观者 33。因此 (1,3)(1,3) 不能互相看见。

数据范围

对于全部数据，有1≤N≤106，1≤ 身高≤106。
测试点1∼3（共30 分）：N≤400。
测试点4∼8（共 50 分）：N≤4000。
测试点9∼10（共 20 分）：无特殊限制。