YLT C++ 8级 2024.03

N4137 [CIE 202403 八级 T1] 道路

题目描述

$N$ 个以 $1 ... N$ 标号的城市通过单向的道路相连。每条道路包含两个参数：道路的长度和需要为该路付的通行费（以金币的数目来表示）。
Bob and Alice 过去住在城市 $1$。在注意到 Alice 在他们过去喜欢玩的纸牌游戏中作弊后，Bob 和她分手了，并且决定搬到城市 $N$。他希望能够尽可能快地到那，但是他囊中羞涩。我们希望能够帮助 Bob 找到从 $1$ 到 $N$ 最短的路径，前提是他能够付得起通行费。

输入格式

第一行包含一个整数 $K$，$0 \leq K \leq 10000$，代表 Bob 能够在他路上花费的最大的金币数。
第二行包含整数 $N$，$2 \leq N \leq 100$，指城市的数目。
第三行包含整数 $R$，$1 \leq R \leq 10000$，指路的数目。
接下来的 $R$ 行，每行具体指定几个整数 $S$、$D$、$L$ 和 $T$ 来说明关于道路的一些情况，这些整数之间通过空格间隔：$S$ 是道路起始城市，$1 \leq S \leq N$；$D$ 是道路终点城市，$1 \leq D \leq N$；$L$ 是道路长度，$1 \leq L \leq 100$；$T$ 是通行费（以金币数量形式度量），$0 \leq T \leq 100$。注意，不同的道路可能有相同的起点和终点。

输出格式

输入结果应该只包括一行，即从城市 $1$ 到城市 $N$ 所需要的最小的路径长度（花费不能超过 $K$ 个金币）。如果这样的路径不存在，结果应该输出 $-1$。

样例

样例 1
输入：

5
6
7
1 2 2 3
2 4 3 3
3 4 2 4
1 3 4 1
4 6 2 1
3 5 2 0
5 4 3 2

输出：

11

N4138 [CIE 202403 八级 T2] Freda 的越野跑

题目描述

Freda 报名参加了学校的越野跑。越野跑共有 $N$ 人参加，在一条笔直的道路上进行。这 $N$ 个人在起点处站成一列，相邻两个人之间保持一定的间距。比赛开始后，这 $N$ 个人同时沿着道路向相同的方向跑去。换句话说，这 $N$ 个人可以看作 $x$ 轴上的 $N$ 个点，在比赛开始后，它们同时向 $x$ 轴正方向移动。
假设越野跑的距离足够远，这 $N$ 个人的速度各不相同且保持匀速运动，那么会有多少对参赛者之间发生“赶超”的事件呢？

输入格式

第一行 $1$ 个整数 $N$。
第二行为 $N$ 个非负整数，按从前到后的顺序给出每个人的跑步速度。
对于 $50\%$ 的数据，$2 \leq N \leq 1000$。
对于 $100\%$ 的数据，$2 \leq N \leq 10^5$。

输出格式

一个整数，表示有多少对参赛者之间发生赶超事件。

样例

样例 1
输入：

5
1 3 10 8 5

输出：

7

提示

我们把这 $5$ 个人依次编号为 $A$, $B$, $C$, $D$, $E$，速度分别为 $1$, $3$, $10$, $8$, $5$。
在跑步过程中：
$B$, $C$, $D$, $E$ 均会超过 $A$，因为他们的速度都比 $A$ 快；
$C$, $D$, $E$ 都会超过 $B$，因为他们的速度都比 $B$ 快；
$C$, $D$, $E$ 之间不会发生赶超，因为速度快的起跑时就在前边。

N4139 [CIE 202403 八级 T3] Rainbow 的商店

题目描述

Rainbow 开了一家商店，在一次进货中获得了 $N$ 个商品。
已知每个商品的利润和过期时间。
Rainbow 每天只能卖一个商品，并且过期商品不能再卖。
Rainbow 也可以选择在每天出售哪个商品，并且一定可以卖出。
由于这些限制，Rainbow 需要制定一份合理的售卖计划。请你计算一下，Rainbow 最终可以获得的最大收益。

输入格式

第一行两个整数 $N$。 接下来 $N$ 行每行两个整数，分别表示每个商品的利润、过期时间。 $1 \leq N, \text{利润, 时间} \leq 10000$。

输出格式

输出一个整数，表示 Rainbow 最终可以获得的最大收益。

样例

样例 1
输入：

7
20 1
2 1
10 3
100 2
8 2
5 20
50 10

输出：

185

提示

$1.$ 第 $1$ 天卖出 $20$
$2.$ 第 $2$ 天卖出 $100$
$3.$ 第 $3$ 天卖出 $10$
$4.$ 第 $4$ 天卖出 $50$（实际上只要在第 $10$ 天卖就可以）
$5.$ 第 $5$ 天卖出 $5$ （实际上只要在第 $20$ 天前卖就可以）
总计 $185$。其它 $2$ 件商品由于过期、每天只能卖一个的限制，在最优策略下应该不出售。

N4140 [CIE 202403 八级 T4] 冰阔落

题目描述

老王喜欢喝冰阔落。
初始时刻，桌面上有 $n$ 杯阔落，编号为 $1$ 到 $n$。老王总想把其中一杯阔落倒到另一杯中，这样他一次性就能喝很多很多阔落，假设杯子的容量是足够大的。
有 $m$ 次操作，每次操作包含两个整数 $x$ 与 $y$。
若原始编号为 $x$ 的阔落与原始编号为 $y$ 的阔落已经在同一杯，请输出 Yes；否则，我们将原始编号为 $y$ 所在杯子的所有阔落，倒往原始编号为 $x$ 所在的杯子，并输出 No。
最后，老王想知道哪些杯子有冰阔落。

输入格式

有多组测试数据，少于 $5$ 组。
每组测试数据，第一行两个整数 $n, m$ ($n, m \leq 50000$)。
接下来 $m$ 行，每行两个整数 $x, y$ ($1 \leq x, y \leq n$)。

输出格式

每组测试数据，前 $m$ 行输出 Yes 或者 No。
第 $m+1$ 行输出一个整数，表示有阔落的杯子数量。
第 $m+2$ 行有若干个整数，从小到大输出这些杯子的编号。

样例

样例 1
输入：

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

输出：

No
Yes
2
1 3
No
No
2
1 4