第二次集中练习翻译

Hello_World

A. 暴力

你的朋友有 $n$ 张卡片。
你已经知道，每张卡片的一面有一个小写字母，另一面有一个一位数字。
现在，你的朋友把卡片平放在一张桌子上，所以你只能看到卡片的其中一面。
你想要知道这些卡片是否满足下面的条件：“如果一张卡片的一面是元音字母，那么它的另一面是一个一位偶数”。特别地，一个元音字母是 $'a','e','i','o','u'$ 中的一个字母，一位偶数是 $'0','2','4','6','8'$ 中的一个。
比如，如果一张卡片的一面是 $'a'$，并且它的另一面是 $'6'$，或者对于两面分别为 $'b','4'$ 或 $'b','3'$ （对于一个非元音字母的情况），它的状态就为“真”。再比如，一张卡片的两面分别为 $'e','5'$，那么它的状态就为“假”。你对于所有的卡片是否都为“真”很感兴趣。特别地，如果没有一张卡片有元音字母，那么它们的状态也为“真”。
为了确定这一点，你可以把一些卡片翻面以看到它的另一面。你想要知道，如果要确定所有卡片的状态，最坏情况下，你最少需要翻多少张卡片，来确认所有卡片的状态是否为“真”。

输入

第一行只包含一个字符串 $s(1\leq\left|s\right|\leq50)$，表示当前桌面上卡片的张数。每个字符不是一个小写字母就是一个一位数。

输出

输出一个整数，表示为了确定你的猜测，你最少需要翻的卡片数。

样例输入

ee

样例输出

2

样例输入

z

样例输出

0

样例输入

0ay1

样例输出

2

提示

对于第一个样例，我们必须把两张卡片都翻过来。注意，虽然两张卡片的字母都是一样的，但是它们的另一面的数字可能不是相同的。
对于第二个样例，我们不需要将任何一张卡片翻面。因为你知道你的朋友没有元音字母的卡片，所以这个状态一定为“真”。
对于第三个样例，我们要把第二张卡片和第四张卡片翻面。

B. 贪心

$Mahmoud$ 有 $n$ 条线段，第 $i$ 条线段的长度为 $a_i$。$Ehab$ 向他提出挑战：让他利用三条线段来构成一个非退化的三角形。$Mahmoud$ 如果不能保证自己能赢，他就不会接受挑战，所以他来求助你，告诉他能否接受这个挑战。给出所有线段的长度，检查他是否能够选择三条线段来构成一个非退化的三角形。
$Mahmoud$ 必须要用上三条线段，他不能把两条线段连接起来或者改变任何一条线段长度。一个非退化的三角形是一个面积为正数的三角形。

输入

第一行包含一个整数 $n(3\leq n\leq10^5)$ —— $Mahmoud$ 所拥有的线段数量。
第二行包含 $n$ 个整数 $a_1,a_2,\cdots,a_n(1\leq a_i\leq10^9)$ —— $Mahmoud$ 所拥有的线段的长度。

输出

输出仅包含一行，如果他能够选择三条边构成一个非退化的三角形，就输出 "$YES$"，否则就输出 "$NO$"。

样例输入

5
1 5 3 2 4

样例输出

YES

样例输入

3
4 1 2

样例输出

NO

提示

对于第一个样例，他可以选用长度为 $2,4$ 和 $5$ 的线段来构成一个非退化的三角形。

C. 并查集

严重急性呼吸综合征 $(SARS)$，一种病因不明的非典型肺炎，被认为是 $2003$ 年 $3$ 月中旬的全球性威胁。为了尽量减少传播给他人，最好的策略是将潜在的患者与他人分开。在“不传你病大学$(NSYSU)$” ，有许多学生组织。在同一个组织中的学生经常互相接触，并且一个学生可能加入多个组织。为了防止 $SARS$ 的传播，$NSYSU$ 收集了所有学生组织的名单，并且在他们的标准操作规程 $(SOP)$ 下，进行了如下操作：在一个组织中的某个学生一旦有患病的可能，这个组织中所有的成员都是潜在的患者。然而，他们发现鉴定所有人是否是潜在的患者是一项艰巨的工作。你的工作是写一个程序，来找到所有潜在的患者。

输入

在一个输入文件中包含多组测试数据。每一组测试数据第一行以 $n,m$ 开头，$n$ 表示学生的数量，$m$ 表示组织的数量。你可以假设 $0<n\leq30000$ 且 $0\leq m\leq500$。每个学生都用一个从 $0$ 到 $n-1$ 的数字单独表示。在所有的测试数据中，$0$ 在最开始被视为一个潜在的患者。这一行之后跟着 $m$ 个学生组织的名单，一行一个组织。每一行都以一个数字 $k$ 开头，表示这个组织中学生的数量，后面跟着 $k$ 个整数，表示在这个组织中的学生。一行中所有的数字都至少被一个空格分隔。
当碰到一个 $n=0$ 且 $m=0$ 的行时，表示输入已经结束，且这一行不需要处理。

输出

对于每个测试数据，输出一个数字表示潜在的患者数量，占单独一行。

样例输入

100 4
2 1 2
5 10 13 11 12 14
2 0 1
2 99 2
200 2
1 5
5 1 2 3 4 5
1 0
0 0

样例输出

4
1
1

D. dp

在一个 $n\times n$ 的棋盘上，王子和公主在玩一个游戏。棋盘上所有的数字被分别表示为 $1，2，3，\cdots,n\times n$，如下图所示：
【题目中的第一张图】
王子站在方格 $1$，跳了 $p$ 步最后到达方格 $n\times n$，他最多进入一个方格一次。所以如果我们用 $x_i$ 表示他所进入的第 $i$ 个方格，那么 $x_1,x_2,\cdots,x_{p+1}$ 所有数字都是不同的。注意 $x_1=1$ 且 $x_{p+1}=n\times n$。公主做了类似的事情——站在方格 $1$ 跳了 $q$ 步最终到达方格 $n\times n$。我们用 $y_1,y_2,\cdots,y_{q+1}$ 这个序列来表示，并且所有 $q+1$ 个数字都不相同。
下面的图 $2$ 展示了一个 $3\times 3$ 的方格，上面显示了王子可能的路线与公主可能的路线。
【题目中的 $Figure_2$ 与 $Figure_3$】
王子按照这个序列来移动：$1$ → $7$ → $5$ → $4$ → $8$ → $3$ → $9$（黑色箭头），而公主按照这个序列来移动：$1$ → $4$ → $3$ → $5$ → $6$ → $2$ → $8$ → $9$（白色箭头）。
皇帝——他们的父亲来了。“为什么分别移动？你们是兄妹啊”，皇帝说，“忽视一些跳步，让你们总是在相同的格子里吧”。
例如，若王子忽视了他的第 $2$ 步，第 $3$ 步，第 $6$ 步，他将会按照这样的路线跳步：$1$ → $4$ → $8$ → $9$。如果公主忽视她的第 $3$ 步，第 $4$ 步，第 $5$ 和第 $6$ 步，她将会按照这样的路线跳步：$1$ → $4$ → $8$ → $9$，（他们的公共路线在图 $3$ 中显示）这样就能让皇帝满意了。皇帝想要知道他们俩最长的相同的路线，你能告诉他吗？

输入

输入的第一行包含一个整数 $t(1\leq t\leq10)$，表示接下来测试数据的组数。
对于每组测试数据，第一行包含三个整数 $n,p$ 和 $q(2\leq n\leq250,1\leq p,q\leq n\times n)$。第二行包含 $p+1$ 个不同的整数，每个整数在 $1\cdots n\times n$ 之间，表示王子的线路。第三行包含 $q+1$ 个不同的整数，每个整数在 $1\cdots n\times n$ 之间 ，表示公主的路线。

输出

对于每组测试数据，输出组的序号，以及最长的公共路线长度。详细细节请看样例输入与输出。

样例输入

1
3 6 7
1 7 5 4 8 3 9
1 4 3 5 6 2 8 9

样例输出

Case 1: 4

E. 贪心 + set

$Helen$ 在 $Metropolis$ 机场工作，她的工作是制定航班时刻表。今天有 $n$ 个航班需要起飞，它们中的第 $i$ 个在今天的第 $i$ 分钟起飞。
$Metropolis$ 机场是 $Metropolis$ 的主要枢纽，因此很难保持时刻表的完整性。这是今天的突发状况：由于技术问题，在今天的前 $k$ 分钟飞机无法起飞，所以现在必须要制定一个新的时刻表。
所有 $n$ 架飞机必须要在第 $k+1$ 到第 $k+n$ 分钟内的不同时刻起飞。然而这并不强制所有的航班按照初始的顺序起飞——在新的时刻表中它们的起飞顺序可以不同。只有一个限制：没有一架飞机允许比它初始的起飞时间更早起飞。
$Helen$ 知道第 $i$ 个航班延误每一分钟的花费 $c_i$，请帮她找到新时刻表中，所有飞机的起飞顺序，要保证延误的总花费最少。

输入

第一行包含两个整数 $n$ 和 $k(1\leq k\leq n\leq300000)$，这里 $n$ 表示航班的数量， $k$ 表示这一天飞机不能起飞的前 $k$ 分钟。
第二行包含 $n$ 个整数 $c_1,c_2,\cdots,c_n(1\leq c_i\leq10^7)$，$c_i$ 表示延误第 $i$ 个航班一分钟的花费。

输出

第一行必须包含最小的可能延误航班花费。
第二行必须包含 $n$ 个不同的整数，$t_1,t_2.\cdots,t_n(k+1\leq t_i\leq k+n)$，这里 $t_1$ 表示第 $i$ 架飞机的起飞时间。如果有多个可行的时间表，输入其中的任何一个。

样例输入

5 2
4 2 1 10 2

样例输出

20
3 6 7 4 5

提示

我们来分析测试样例。如果 $Helen$ 保留原来的起飞顺序，将所有航班往后延迟 $2$ 分钟，延误的所有花费为 $(3-1)\times4+(4-2)\times2+(5-3)\times1+(6-4)\times10+(7-5)\times2=38$
然而，最优的时刻表安排是样例输出中所显示的，它的花费为 $(3-1)\times4+(6-2)\times2+(7-3)\times1+(4-4)\times10+(5-5)\times2=20$