0921 第 4 场 算法季度赛

• 比赛链接：https://www.lanqiao.cn/oj-contest/season-4/
• 题解回放：https://www.bilibili.com/video/BV1RysmeyEBr/

T1. 灵魂问题【算法赛】

问题描述

在面试中，你遇到了一个刁钻的面试官，他问道：“你知道计算机科学的灵魂问题吗？”

你心里一震，觉得这一定是个深奥的问题。正想着知难而退，却不料面试官接着说：“好吧，其实就是——程序员每天都在纠结的问题：咖啡要加几勺糖？”

作为一名优秀的程序员，你自然是知道，代码才是甜的来源，糖什么的根本不需要。因此，请你带着自信，输出一个整数，回答这个“灵魂问题”。

输入格式

无。

输出格式

输出一个整数，表示答案。

T2. 全栈项目小组【算法赛】

问题描述

“哈哈，终于轮到你来当面试官了，小蓝！”

看着对面强忍着笑意的小桥，你回想起一个月前你作为应聘者接受小桥“拷问”的窘境，不禁感叹风水轮流转。

“喏，这是 HR 小姐姐给你的 $N$ 份简历。小蓝，你可得好好把关”，小桥边说边拍了拍你的肩膀。

每份简历上都详细地写了应聘者的期望薪资以及应聘者期望的岗位（前端或后端）。

“真是头疼啊”，你一边翻看着简历，一边小声嘀咕着，“这么多简历，要是一个个面试过去，猴年马月才能招到合适的人啊！”

“小蓝，这次的项目比较急。要不这样，如果某两个人的期望薪资相同，并且一个人期望的岗位是前端，一个人期望的岗位是后端，那就把他们都招进来，组成一个全栈项目小组。强强联手，快速上手，如何？”小桥似乎看出了你的难处，在一旁给你出谋划策，

“有道理，那就这么办！”，你一拍大腿，决定采纳小桥的建议。

请问，这 $N$ 份简历中，最多能组成多少个全栈项目小组？

输入格式

第一行包含一个整数 $N$ ( $1 \leq N \leq 2\times 10^5$ )，表示简历的数量。

接下来的 $N$ 行，每行包含一个整数 $s$（$1\leq s \leq 10^6$） 和一个字符 $p$（$p \in \lbrace F,B \rbrace$），分别表示应聘者期望的薪资和期望的岗位（$F$ 表示前端，$B$ 表示后端）。

输出格式

输出一个整数，表示最多能够组成的全栈小组数。

样例输入

5
10000 F
10000 B
20000 F
10000 F
20000 B

样例输出

2

样例说明

在样例中：

• 有 $2$ 个前端和 $1$ 个后端应聘者期望薪资为 $10000$，可以组成 $1$ 个全栈小组。
• 有 $1$ 个前端和 $1$ 个后端应聘者期望薪资为 $20000$，可以组成 $1$ 个全栈小组。

因此，总共可以组成 $2$ 个全栈小组。

T3. 你会二分吗？【算法赛】

问题描述

你面试了一家公司，面试官淡淡地问道：“你知道什么是二分吗？”这让你心中一阵狂喜，毕竟这正是你最擅长的算法。于是，你开始滔滔不绝地分享自己对二分法的理解，仿佛那份 Offer 已经在向你招手。

然而，面试官打断了你，继续说道：“这样吧，我给你出一道题。我们公司有 $n$ 位女员工和 $n$ 位男员工，第 $i$ 位男员工的 e 人值为 $A_i$，第 $i$ 位女员工的 e 人值为 $B_i$。在即将举行的公司年度聚会上，我们需要将他们两两分为 $N$ 组，每组由一名男员工和一名女员工组成。每组的 e 人值被定义为这组内男女的 e 人值之和。请你进行分组，使得所有组的 e 人值的最小值最大，你只需要求出这个最大的最小值即可。”

你心中一震：“最小值最大？这不就是二分题的明显提示吗！”

为了顺利通过这次面试，请你尽快解决面试官的问题吧！

输入格式

第一行输入一个整数 $n$（$1\leq n \leq 10^5$） 表示公司的男员工和女员工数量。

第二行输入 $n$ 个整数 $A_1,A_2,A_3,\cdots,A_n(0 \leq A_i \leq 10^9)$ 表示每位男员工的 e 人值。

第二行输入 $n$ 个整数 $B_1,B_2,B_3,\cdots,B_n(0 \leq B_i \leq 10^9)$ 表示每位女员工的 e 人值。

输出格式

输出一个整数表示答案。

样例输入

5
1 2 3 4 5
2 1 2 3 4

样例输出

5

T4. 扫把扶不扶【算法赛】

问题描述

你正在参加一场程序员的终极面试，和你竞争的是小蓝。你们都顺利地通过了前几轮筛选，来到了最后一轮的现场面试环节。

你到达公司门口的时间是 $S_1$，和面试官约定的面试时间是 $S_2$。在约定时间到达前（$S_1 \sim S_2$），你可以选择提前开始面试。然而，如果超过了面试时间，即便只晚了 $1$ 秒，你都将失去面试机会，直接被淘汰。

你的面试会持续 $T$ 分钟。

小蓝到达公司门口的时间是 $S_3$，和面试官约定的面试时间是 $S_4$。由于你在前几轮的表现比他好，因此小蓝必须在你结束面试后才能开始他的面试。如果小蓝在他的面试时间之前没有开始面试，他也将失去面试机会，直接被淘汰。

面试存在竞争机制：如果只有你或小蓝中的一人参与了面试，那么参与面试的那个人将胜出。如果你和小蓝都没有参与面试，你们将双双失败。

“那如果两个人都参与了面试，谁将胜出呢？”你正想着，突然发现公司门口的不远处躺着一把扫把，看样子是面试官故意放的。你想扶起它，但这需要你花费 $X$ 分钟的时间。 根据你所了解的套路，如果你扶起了扫把，并参加了面试，那么你和小蓝的竞争中，你必定能够胜出。相对的，如果你没有扶起扫把，并且你和小蓝都参加了面试，那么小蓝必定能够胜出。

现在，你和小蓝都会采取最优的策略来确保自己胜出（如果无论如何也无法使自己胜出，则应优先确保双双失败）。请问最后的结果会是如何？

输入格式

输入包含多组数据。

第一行包含一个整数 $N$（$1\leq N \leq 10^3$），表示数据的组数。

接下来 $N$ 组数据，每组数据包含三行：

• 第一行包含两个时间字符串 $S_1$, $S_2$，以空格分隔，表示你到达公司门口的时间和你和面试官约定的面试时间。
• 第二行包含两个时间字符串 $S_3$, $S_4$，以空格分隔，表示小蓝到达公司门口的时间和小蓝和面试官约定的面试时间。
• 第三行包含两个整数 $T,x$（$1\leq T, x \leq 120$），以空格分隔，分别表示你的面试时长和你扶起扫把所需的时间（单位：分钟）。

时间的格式为 $\text{HH:MM:SS}$，其中 $\text{HH}$ 表示小时（$00 \le \text{HH} \le 21$），$\text{MM}$ 表示分钟（$00 \le \text{MM} \le 59$），$SS$ 表示秒（$00 \le \text{SS} \le 59$）。

输出格式

对于每组数据，输出一个字符串，表示最终的结果。

• 如果你胜出了，输出 You。
• 如果小蓝胜出了，输出 Lan。
• 如果你们双双失败了，输出 Draw。

样例输入

4
12:00:00 12:10:00
12:00:00 12:12:00
3 100
12:00:00 12:10:00
12:00:00 12:13:00
3 20
12:10:00 12:00:00
12:10:00 12:05:00
1 1
12:00:00 12:10:00
13:00:00 13:10:00
3 10

样例输出

You
Lan
Draw
You

样例说明

对于第一组数据，你可以在 $\text{12:10:00}$ 开始面试。这样，面试结束时间为 $\text{12:13:00}$，大于小蓝的面试时间。小蓝无法参与面试，直接被淘汰。因此，你胜出了。

对于第二组数据，如果你扶起了扫把，你将赶不上面试的时间，而小蓝可以参与面试，小蓝胜出。如果你不扶起扫把，那么你和小蓝都会参与面试，小蓝胜出。

对于第三组数据，你和小蓝都无法参与面试，双双失败。

对于第四组数据，你可以选择在 $\text{12:00:00}$ 时刻去扶起扫把，而后在 $\text{12:10:00}$ 时刻参与面试。由于你扶起了扫把，并参加了面试，因此你胜出了。

T5. 水杯考验【算法赛】

问题描述

面试官： "非常高兴见到你！我们公司一直在寻找创新的解决方案来优化我们的产品。我想给你一个有趣的问题，看看你如何思考。"

你： "好的，我准备好了！"

面试官： "假设你面前有 $N$ 个水杯，每个水杯中装有不同的水量，分别为 $W_1,W_2,W_3,\cdots,W_N$。你可以进行以下操作：选择两个不同的水杯 $i$ 和 $j$（$i \ e j$），然后将这两个水杯中的水量更新为它们的平均值。"

你： "明白了，这样的话两个水杯的水量会变得相同。"

面试官： "没错！请注意，水杯的数量不会改变。你可以进行任意次数的操作，也可以不进行操作。我的问题是：在进行这些操作后，$N$ 个水杯中最多会出现多少种不同的水量？"

你： "这听起来很有趣，让我思考一下。"

输入格式

第一行输入一个整数 $N(1 \leq N \leq 10^3)$ 表示水杯数量。

第二行输入 $N$ 个整数 $W_1,W_2,W_3, \cdots,W_N(1 \leq W_i \leq 10^9)$ 表示每个水杯的水量。

输出格式

输出一个整数表示答案。

样例输入

5
1 2 3 2 4

样例输出

4

样例说明

我们可以将第 $2$ 和第 $3$ 杯水进行一次操作后每个水杯的水量变为 $[1,2.5,2.5,2,4]$。

再将第 $1$ 和第 $2$ 杯水进行一次操作后每个水杯的水量变为 $[1.75,1.75,2.5,2,4]$，答案为 $4$。

T6. 面试官的刁难【算法赛】

问题描述

你面试了一个公司，面试官抬头看了你一眼，问：“你知道什么是 SQL 吗？数据库优化有了解吗？”你心里咯噔一下，感觉要跪了，但还是硬着头皮坐下。

面试官接着问：“现在我们有一个数据库表，表格里存放了 $10^n$ 个正整数，分别为 $1,2,3\dots, 10^n - 1,10^n$。你需要做的就是把这些正整数的每一位上的数字都加起来，然后告诉我这些数位和的总和。”

你觉得这个问题还挺简单，正准备动手，面试官突然补充道：“慢着，别急着写代码。我还没说完呢。你不仅要算出数位和的总和，还得把这个总和再拆成一位一位的数字，最后再告诉我这些数字的总和。”

说完，面试官拿出一杯咖啡，一副看好戏的表情，仿佛在等着你出错。

为了拿到 Offer，请你尽力搞定这题。祝你成功。

输入格式

输入的第一行包含一个整数 $t$（$1\leq t \leq 10^5$），表示有 $t$ 组测试数据。

接下来的 $t$ 行中，每行包含一个整数 $n$（$1\leq n \leq 10^9$），表示数据库表中存放的数的个数。

输出格式

对于每组测试数据，输出一个整数，表示数位和的总和的数位和。

样例输入

1
1

样例输出

10

样例说明

当 $n = 1$ 时，数据库里存放的数字为 $1$ 到 $10$，数位和的总和为 $1 + 2 + ... + 9 + 1 + 0 = 46$。$46$ 的各位数字和为 $4 + 6 = 10$。

T7. 算法工程师【算法赛】

问题描述

你是一名顶级算法工程师，刚刚参加了一家互联网药企的面试，很快优秀的你便从众多求职者中脱颖而出拿下 offer。

面试结束时，CEO 透露了公司当前面临的一个棘手问题，这让你心中一震。这个问题不仅关系到公司的利润，更直接影响到无数患者的用药成本。CEO 眼中闪烁着期待的光芒，郑重地告诉你：“如果你能解决这个药品价格优化的问题，我将让你成为此项目的 leader！”

具体地：公司的网站总共销售 $N$ 种药物，每种药物的单瓶价格为 $S_i$。同时，公司作为售卖机构，与药品生产方之间有多种合作方案。总共有 $M$ 种合作售卖方案，第 $i$ 种方案允许患者同时购买第 $A_i$ 种药物到第 $B_i$ 种药物的各一瓶（包括 $A_i$ 和 $B_i$），且购买总价格为 $C_i$。

你的任务是设计一个高效的算法，帮助用户计算出购买每种药物至少一瓶的最低总价，进而实现价格优化。

输入格式

第一行输入两个整数 $N,M( 1\leq N,M \leq 10^5)$ 表示药物种类数以及合作售卖方案数。

第二行输入 $N$ 个整数 $S_1,S_2,S_3,\cdots,S_n(1 \leq S_i \le 10^6)$ 表示第 $i$ 种药物的价格。

接下来 $M$ 行，每行三个整数 $A_i,B_i,C_i(1 \leq A_i \leq B_i \le N,1 \leq C_i \leq 10^6)$ 表示一种合作售卖方案。

输出格式

输出一个整数表示答案。

样例输入

5 3
1 10 3 7 9
1 3 4
2 5 20
4 5 13

样例输出

17

T8. SSP OFFER【算法赛】

问题描述

你是一个资深程序员，今天去某著名互联网公司参加面试。一进门，面试官就给了你一个大活儿：“我们公司有一个内部系统，由 $n$ 台服务器组成，这 $n$ 台服务器的编号分别为 $1\sim n$，且每两台服务器之间都通过一条双向传输的网线连接。最近系统频繁出现故障，主要原因是网线老化。为了提升系统稳定性，我们决定更换所有网线，你来处理一下吧。”

你略感疑惑：“只是更换网线吗？”

面试官点了点头：“没错，但需要满足一些特殊要求：

1. 我们准备了三种颜色的网线：红色、绿色和蓝色。你需要为每两台服务器之间选择其中一种颜色的网线进行连接。
2. 为了避免单点故障，不能只使用一种颜色的网线就覆盖所有服务器之间的通信。也就是说，仅通过一种颜色的网线，无法从任意一台服务器访问到其他所有服务器。
3. 为了保证网络性能，每台服务器都至少要通过一条红色网线与其他服务器连接。
4. 红色网线要尽可能多的被使用。”

你站起身准备走人。

“等等！”面试官拉住了你，“这样吧，如果你能算出满足以上条件的方案总数，我就给你开 Super Special Offer！”

“行！”

现在，请你计算出满足以上条件的方案数。由于答案可能很大，你只需要输出方案数对 $10^9 + 7$ 取模的结果即可。

如果两种网线连接方案中存在任意两台服务器之间的网线颜色不同，则被认为是两种不同的方案。

输入格式

输入的第一行包含一个整数 $t$（$1\leq t \leq 10^5$），表示有 $t$ 组测试数据。

接下来的 $t$ 行中，每行包含一个整数 $N$ $(4 \leq N \leq 10^9)$，表示服务器的数量。

输出格式

对于每组测试数据，输出一个整数，表示满足条件的方案总数对 $10^9+7$ 取模后的结果。

样例输入

1
4

样例输出

18

样例说明

图片描述