【2024暑假】-普及2

wflengxuenong · 2024-07-05 18:35:05 · 个人记录

A:Bronze Count

时间限制 3.00s 内存限制 512.00MB

题目描述

一次比赛结束后，您可能迫切地想知道有多少参赛者获得了铜牌？

金牌会授予所有获得最高分的参赛者。银牌会授予获得第二高分的所有参赛者。铜牌会授予获得第三高分的所有参赛者。

给定一份参赛选手的成绩列表，请求出获得铜牌所需的分数以及有多少人正好得到这一分数。

输入格式

输入的第一行包含一个正整数 N 表示参赛者的数量。

接下来 N 行包含一个整数表示一个参赛者的分数。

保证每个分数都在 0 到 75 之间（包含）并且至少存在三个不同的分数。

输出格式

输出一个非负整数 S 和一个正整数 P 用空格隔开。其中 S 是得到铜牌所需要的分数，P 是正好得到这个分数的参赛者数量。

样例 #1

样例输入 #1

样例输出 #1

62 1

样例 #2

样例输入 #2

样例输出 #2

60 2

提示

【样例 1 解释】

得到铜牌需要 62 分并且有一个参赛者正好得到这一分数。

【样例 2 解释】

得到铜牌需要 60 分并且有两个参赛者正好得到这一分数。

【数据范围】

本题采用捆绑测试。

对于所有数据，保证 1\leq N\leq 2.5\times 10^5，分数 s 满足 0\leq s\leq 75，至少存在三个不同的分数。

下面的表格显示了 15 分的分配方案：

分值	描述	范围
6	分数互不相同并且参赛者数量很少。	N \leq 50
7	分数可能存在相同并且参赛者数量很少。	N \leq 50
2	分数可能存在相同并且参赛者数量可以很大。	N \leq 2.5 \times 10^5

B: Troublesome Keys

时间限制 3.00s 内存限制 512.00MB

题目描述

Alex 的键盘很奇怪。有两个字母按键出现了问题：

键盘上有一个按键，每次按下它的时候总是显示另一个错误的字母。Alex 把这个按键称为愚蠢的按键。奇怪的是，Alex 从来没有尝试过输入这个错误的字母。
键盘上还有一个按键，按下它的时候则不会显示任何内容。Alex 把这个按键称为安静的按键。

Alex 至少按下了一次愚蠢的按键，但不一定按下了安静的按键。

你需要确定出现问题的按键和按下它时显示的错误的字母。幸运的是，这是可能的，因为 Alex 从来没有在按下愚蠢的按键之后立即按下安静的按键，也没有再按下安静的按键之后立即按下愚蠢的按键。

输入格式

输入共两行。输入的第一行包含 Alex 按下的 N 个按键。第二行包含屏幕上显示的字母。

输出格式

输出共两行。

第一行输出用空格分开的两个字母表示愚蠢的按键和按下时显示的错误字母。

第二行输出一个字符，如果安静的按键被按下，输出安静的按键，否则输出一个短横线（-）。

样例 #1

样例输入 #1

forloops
fxrlxxps

样例输出 #1

o x
-

样例 #2

样例输入 #2

forloops
fxrlxxp

样例输出 #2

o x
s

样例 #3

样例输入 #3

forloops
frlpz

样例输出 #3

s z
o

提示

【样例 1 解释】

与愚蠢的按键对应的字母是 o，每次按下会显示错误的字母 x。安静的按键没有被按下过。

【样例 2 解释】

与愚蠢的按键对应的字母是 o，每次按下会显示错误的字母 x。没有显示的安静的按键对应的字母是 s。

【样例 3 解释】

与愚蠢的按键对应的字母是 s，每次按下会显示错误的字母 z。没有显示的安静的按键对应的字母是 o。

【数据范围】

本题采用捆绑测试。

对于所有数据，保证输入中每行都只包含小写字母，1\leq N\leq 5\times 10^5。

下面的表格显示了 15 分的分配方案：

分值	描述	范围
3	安静的按键没有被按下过，按键次数很少。	N \leq 50
3	按下的第一个有问题的按键是愚蠢的按键，按键次数很少。	N \leq 50
5	按下的第一个有问题的按键可能是愚蠢的按键或者安静的按键，按键次数很少。	N \leq 50
4	按下的第一个有问题的按键可能是愚蠢的按键或者安静的按键，按键次数可能很多。	N \leq 5 \times 10^5

C: Harvest Waterloo

时间限制 3.00s 内存限制 512.00MB

题目描述

有一款新出现的广受欢迎的收割模拟游戏叫做 Harvest Waterloo。游戏在一块矩形南瓜地上进行，南瓜地里有成捆的干草和不同大小的南瓜。游戏开始时，一个农民在其中一个南瓜的位置上。

农民通过在整片土地上向左、向右、向上或向下移动来收割南瓜。农民不能斜着移动，不能穿过干草，也不能离开田地。

你的工作是确定农民收获的南瓜的总价值。其中一个小南瓜值 1 美元，一个中等大小的南瓜值 5 美元，而一个大南瓜值 10 美元。

输入格式

输入的第一行是一个整数 R > 0 表示南瓜地的行数。

第二行是一个整数 C > 0 表示南瓜地的列数。

接下来 R 行描述了整个南瓜地。每行包含 C 个字符并且每个字符要么表示一个南瓜，要么表示干草：S 表示小南瓜，M 表示中等大小的南瓜，L 表示一个大南瓜，* 表示干草。

下一行包含一个整数 A 满足 0 \leq A < R，最后一行是一个整数 B 满足 0 \leq B < C。表示农民一开始在第 A 行第 B 列的位置。南瓜地的左上角称为第 0 行第 0 列。

输出格式

输出一个整数 V 表示农民能够收割的南瓜的总价值。

样例 #1

样例输入 #1

6
6
**LMLS
S*LMMS
S*SMSM
******
LLM*MS
SSL*SS
5
1

样例输出 #1

样例 #2

样例输入 #2

6
6
**LMLS
S*LMMS
S*SMSM
***SLL
LLM*MS
SSL*SS
2
4

样例输出 #2

提示

【样例 1 解释】

农民在第 5 行第 1 列开始可以收割 6 个南瓜。可以收割到 2 个小南瓜，1 个中等大小的南瓜和 3 个大南瓜。收割的南瓜的总价值是 2 \times 1 + 1 \times 5 + 3 \times 10 = 37。

【样例 2 解释】

农民在第 2 行第 4 列开始可以收割 19 个南瓜。可以收割到 8 个小南瓜，6 个中等大小的南瓜和 5 个大南瓜。收割的南瓜的总价值是 8 \times 1 + 6 \times 5 + 5 \times 10 = 88。

【数据范围】

本题采用捆绑测试。

对于所有数据，保证 1\leq R,C\leq 10^5，1\leq R\times C\leq 10^5。

下面的表格显示了 15 分的分配方案：

分值	描述	范围
1	南瓜地很小并且不存在干草。	R \times C \leq 100
4	南瓜地很小并且干草把南瓜地分割为一些矩形区域。	R \times C \leq 100
5	南瓜地很小并且干草可以在任意位置。	R \times C \leq 100
5	南瓜地可能很大并且干草可以在任意位置。	R \times C \leq 10^5

D: 超速

时间限制 1.00s 内存限制 128.00MB

题目描述

超速行驶是一种危险的犯法行为，大大增加了交通事故导致悲惨后果的可能性。不幸的是使用使用雷达和相机控制速度并不能完全解决问题。为了防止这种行为的出现，根据汽车在一段道路上的行驶时间来罚款，可以对超速行为进行限制。

现在有 n 段从 1\sim n 编号的公路。第 i 段公路长 l_i 米，其限速为 v_i 米每秒。超速就要罚款，但是为了体现按劳分配，还要对不同程度的超速设置不同的罚款金额。

具体来说，如果不超速则不收罚款；否则，用 e 表示汽车在这段公路上的最大速度减去限速的值：

如果 0<e\leq a_1，则惩罚为 f_1 个货币单位。
如果 a_1<e\leq a_2，则惩罚为 f_2 个货币单位。
...
如果 a_{m-2}<e\leq a_{m-1}，则惩罚为 f_{m-1} 个货币单位。
如果 a_{m-1}<e，则惩罚为 f_m 个货币单位。

目前，有 q 辆车要经过这 n 段道路，每辆车在 s_i 时间到达 1 号路段，在 t_i 时间离开 n 号路段。

你需要计算每辆车在所有路段中最高被罚款的金额至少是多少。

时间从道路开放起计算，即从 0 开始计算。

输入格式

第一行一个正整数 n，表示道路段数。

接下来的两行，每行 n 个数，第一行为 v_i，第二行为 l_i。

第四行为一个正整数 m，表示罚款的 m 种不同范围。

接下来的两行，第一行 m-1 个数，为 a_i；第二行 m 个数，为 f_i。

第七行为一个正整数 q，表示共有 q 辆车。

接下来的 q 行，每行两个整数 s_i,t_i。

输出格式

输出共 q 行。

对于每辆车，输出它最少被罚款的金额。

样例 #1

样例输入 #1

3
10 20 30
400 500 600
6
1 5 10 12 16
100 300 600 800 1000 1500
3
10 100
20 70
45 100

样例输出 #1

0
800
600

提示

对于 100\% 的数据，1\leq n\leq 10，1\leq v_i,l_i,a_i,f_i\leq 10^9，1\leq m\leq 10^5，1\le q\le 10^5，1\leq s_i<t_i\leq 10^9。

任务编号	特殊限制	分值
1	n=1,m=1	5
2	m=1	10
3	n=1,m\leq 10	9
4	n=1	12
5	m\leq 10,a_i\leq 10	13
6	m\leq 10	14
7	无特殊限制	37

E: Painting Roads

时间限制 1.00s 内存限制 512.00MB

题目描述

Kitchener 市的市长 Alanna 成功地改进了该市的道路规划。然而，来自 RedBlue 市的一位售货员仍然抱怨道路的颜色不够丰富。Alanna 的下一个任务就是粉刷一些道路。

Kitchener 市的道路规划可以表示为 N 个十字路口和 M 条道路，第 i 条道路连接第 u_i 个十字路口和第 v_i 个十字路口。一开始所有道路都是灰色的。Alanna 想要把一些道路染成红色或者蓝色，满足以下条件：

对于每一条灰色道路，假设其连接十字路口 u_i 和十字路口 v_i，一定存在一条从十字路口 u_i 到十字路口 v_i 的路径，满足路径上的道路颜色红色和蓝色交替出现，任何道路都不是灰色的。

为了降低城市的支出，Alanna 希望尽可能少地对道路进行染色。请帮助 Alanna 设计一个符合要求的染色方案。

输入格式

输入的第一行包含两个整数 N 和 M（1\leq N, M \leq 2 \times 10^5）。

接下来 M 行中的第 i 行包含两个整数 u_i 和 v_i 表示存在一条连接十字路口 u_i 和十字路口 v_i 的道路（1 \leq u_i, v_i \leq N，u_i \neq v_i）。

任意两个十字路口之间至多存在一条道路。

输出格式

输出一个长度为 M 的字符串，表示染色的方案。第 i 个字符表示第 i 条道路的颜色，R 表示红色，B 表示蓝色，G 表示灰色（未染色）。

注意你必须在满足条件的情况下最小化染色的道路数目。如果存在多个这样的染色方案，输出任意一个。

样例 #1

样例输入 #1

样例输出 #1

BRGBBGG

样例 #2

样例输入 #2

4 2
1 2
3 4

样例输出 #2

BB

提示

【样例 1 解释】

十字路口以及有效的道路的示意图如下所示，该方案最小化了染色道路的数量。请注意，每条道路上的颜色显示为 R（红色）、B（蓝色）或 G（灰色）。

所有为染色的道路都满足条件：

第二条路标记为 G_2 连接了十字路口 2 和 4，路径 2, 1, 4 上的道路被染上红色、蓝色。
第三条路标记为 G_3 连接了十字路口 5 和 2，路径 5, 4, 1, 2 上的道路被染上红色、蓝色、红色。
第五条路标记为 G_5 连接了十字路口 4 和 3，路径 4, 1, 3 上的道路被染上蓝色、红色。

【样例 2 解释】

请注意 Kitchener 的道路可能不是连通的。

【数据范围】

本题采用捆绑测试。

对于所有数据，保证 1\leq N, M \leq 2 \times 10^5，1 \leq u_i, v_i \leq N，u_i \neq v_i。

下面的表格显示了 15 分的分配方案：

分值	附加条件
2	对任意 1 \leq i < N 存在一条连接 i 和 i + 1 的道路（还可能存在其他道路）
3	图连通并且 N = M
3	任何道路都不同时属于至少两个简单环（见下文定义）
7	无

定义：若用 u \leftrightarrow v 表示一条连接 u 和 v 的道路，则称 k \geq 3 且所有 w_i 互不相同是序列 w_1 \leftrightarrow w_2 \leftrightarrow \cdots \leftrightarrow w_k \leftrightarrow w_1 为简单环。