算法竞赛 May Lunchtime 2020 Division 2

算法竞赛 May Lunchtime 2020 Division 2

参加了May Lunchtime 2020 Division 2,总时长3个小时,1个小时完成AB,第二个小时磕C,还是不行,应该是有什么知识点我没学,这次结束之后几天继续学习一下。

CodeChef自带翻译,我只需要调整一下格式即可。

A. Lost Weekends

》英文原题《

题目描述

大厨最近开始在 ABC 公司工作。让我们用从 1 到 5 的整数来表示工作日(星期一至星期五)。对于每个有效 i,大厨在工作日 i 在办公室工作的小时数为 Ai。

不幸的是,由于 COVID-19 爆发,大厨开始在家工作,工作效率明显下降。根据大厨的分析,在办公室 1 个小时完成的工作相当于在家 P 个小时完成的工作。

现在,为了按时完成工作,大厨需要花更多的时间在家工作,这可能会付出睡眠时间等其他代价。好在,他不必像在办公室工作时那样每天都要把当天的活干完。

在家工作时,他可以在提前开始某一个工作日的工作,和/或在未来的某一天完成该工作日的工作。唯一的要求是他把每周的活及时干完,即他需要在一周结束前完成该周的所有工作。每天有 24 小时。

如果大厨在五个工作日中不可能完成一周的工作,那么他必须在周末加班。大厨想知道
他是必须在周末加班,还是在工作日就能完成工作。请你帮助他回答这个问题。(就算大厨周末加班活也有可能干不完,但大厨不在乎这一点。)

输入格式

输入数据第一行包含一个整数 T,表示数据组数。接下来是 T 组数据。
每组数据只有一行包含六个整数 A1, A2, A3, A4, A5, P。

输出格式

对于每组数据,输出一行包含一个字符串,若大厨需要周末加班,输出 “Yes”,否则输出
“No”(均不含引号)。

数据范围

• 1 ≤ T ≤ 1000
• 0 ≤ Ai ≤ 24
• 1 ≤ P ≤ 24

子数据集

• 数据集 1(100 分):无特殊限制

样例数据

输入

2
14 10 12 6 18 2
10 10 10 10 10 3

输出

No
Yes

样例解释

第一组数据中,P = 2,因此大厨在办公室工作的每一天工作量在家分别需要 [28, 20, 24, 12, 36]
小时来完成。如果他在家五个工作日都工作满 24 小时,他就能干完所有活,于是不需要周末
加班。
第二组数据中,无论大厨工作日工作多久,他都需要周末加班。


B. Weird Walk

》英文原题《

题目描述

Alice 和 Bob 在一条无限长的街上走。初始时,两人都在 X = 0 处,他们向着 X 增加的方向走。N 秒后,他们停下。我们记 Alice 和 Bob 在第 i 秒中的速度分别为 Ai, Bi。

有时候,Alice 和 Bob 走在一起,即并肩(位置相同)且以相同的速度行走。我们记尴尬距离为他们走在一起经过的距离,请你求出尴尬距离。

输入格式

输入数据第一行包含一个整数 T,表示数据组数。接下来是 T 组数据。
每组数据第一行包含一个整数 N。
第二行包含 N 个整数,A1, A2, ..., AN。
第三行包含 N 个整数,B1, B2, ..., BN。

输出格式

对于每组数据,输出一行包含一个整数表示总的尴尬距离,易证这个距离总是一个整数。

数据范围

• 1 ≤ T ≤ 20
• 1 ≤ N ≤ 105
• 1 ≤ Ai, Bi ≤ 105
• 各组数据中 N 的总和不超过 106

子数据集

• 数据集 1(30 分):1 ≤ N ≤ 1000
• 数据集 2(70 分):无特殊限制

样例数据

输入

3
4
1 3 3 4
1 2 4 4
2
2 3
3 2
2
3 3
3 3

输出

5
0
6

样例解释
第一组数据中,
• 第 1 秒 Alice 和 Bob 一起走,从 X = 0 走到 X = 1。
• 第 2 秒 Alice 走得比 Bob 快,他们没有一起走。Alice 走到了 X = 4,Bob 走到了 X = 3。
• 第 3 秒他们仍然没有一起走,但这次 Bob 走得比较快,他们都到达了 X = 7。
• 第 4 秒即最后一秒,他们一起走了距离 4。
• Alice 和 Bob 在第 1 秒和第 4 秒一起走了,因此尴尬距离为 1 + 4 = 5。
第二组数据中,
• 第 1 秒 Alice 速度为 2,Bob 速度为 3,他们没有一起走,Alice 走到了 X = 2,Bob 走到了 X = 3。
• 第 2 秒 Alice 速度为 3,Bob 速度为 2,他们没有一起走。
• 尽管 2 最终 Alice 和 Bob 到达了相同的位置 X = 5,但他们没有一起走过,尴尬距离为0。
第三组数据中,Alice 和 Bob 一直一起走,尴尬距离为 3 + 3 = 6


C. Convert the String

》英文原题《

题目描述

Vivek 对居家隔离感到非常无聊,因此他提出了一个有趣的任务。他成功完成了此任务,现在,他希望你来完成它。

给定两个字符串 A 和 B,每个字符串的长度为 N。我们从 0 开始对每个字符串中的字符标号:对于每个 i(0 ≤ i < N),A 和 B 的第 i + 1 个字符用 Ai 和 Bi 表示。

你需要通过执行以下类型的操作将 A 转换为 B:
• 选择集合 {0, 1, …, N − 1} 的一个子集 S。
• 记所有 x ∈ S 的 Ax 中字典序最小的字符为 c。
• 对于每个 x ∈ S,将 Ax 替换为 c。

请你找到所需的最少操作数,或者断定不可能将 A 转换为 B。如果有解,你还需要给出一个使用最少操作将 A 转换为 B 的方案。如果有多种方案,可输出任意一种。

输入格式

输入数据第一行包含一个整数 T,表示数据组数。接下来是 T 组数据。
每组数据第一行包含一个整数 N。
第二行包含一个字符串 A。
第三行包含一个字符串 B。

输出格式

对于每组数据,若不可能将 A 变成 B,输出一行包含一个整数-1;否则,先输出一行包含一个整数 K,表示所需的最少操作数,然后输出 K 行,每行先包含一个正整数 Z,接着一个空格和 Z 个用空格隔开的在 {0, 1, …, N − 1} 之内的整数,表示子集 S。

数据范围

• 1 ≤ T ≤ 20
• 1 ≤ N ≤ 1000
• |A| = |B| = N
• A 和 B 均只包含小写英文字母

子数据集

• 数据集 1(30 分):B 中只含 ‘a’ 和 ‘b’
• 数据集 2(70 分):无特殊限制

样例数据

输入

3
5
abcab
aabab
3
aaa
aab
2
de
cd

输出

2
3 1 2 4
3 0 1 3
-1
-1

样例解释

第一组数据中,
• 首先我们取 S = (1, 2, 4),则字符 c 为 ‘b’,替换后 A 变为 “abbab”。
• 然后取 S = (0, 1, 3),c 为 ‘a‘,A 变为 “aabab”,得到 B
• 不可能只用一次操作将 A 变成 B

第二组数据中,显然不可能将 A 变成 B 因为字符 c 总为 ‘a’。

第三组数据中,不可能将 A 变为 B,因为 c 不可能为 ‘c’。


D、E两题有需要的自行前往查看


D. Tree difference

》英文原题《


E. Escape One

》英文原题《

版权声明:本文为 溪月阁 | MoBrook 博主「 皓月 」的原创文章遵循用 CC BY-NC-SA 4.0 版权协议进行许可,转载请附上原文出处链接及本声明。

本文链接https://mobrook.cn/index.php/ltime84b/

没有了,已经是最后文章

没有了,已经是最新文章