一、编程题
1、道路（2024.3八级）
N个以 1 ... N 标号的城市通过单向的道路相连:。每条道路包含两个参数：道路的长度和需要为该路付的通行费（以金币的数目来表示）
Bob and Alice 过去住在城市 1.在注意到Alice在他们过去喜欢玩的纸牌游戏中作弊后，Bob和她分手了，并且决定搬到城市N。他希望能够尽可能快的到那，但是他囊中羞涩。我们希望能够帮助Bob找到从1到N最短的路径，前提是他能够付的起通行费。
时间限制：1000
内存限制：65536
输入
第一行包含一个整数K, 0 <= K <= 10000, 代表Bob能够在他路上花费的最大的金币数。第二行包含整数N， 2 <= N <= 100, 指城市的数目。第三行包含整数R, 1 <= R <= 10000, 指路的数目. 接下来的R行，每行具体指定几个整数S, D, L 和 T来说明关于道路的一些情况，这些整数之间通过空格间隔: S is 道路起始城市, 1 <= S <= N D is 道路终点城市, 1 <= D <= N L is 道路长度, 1 <= L <= 100 T is 通行费 (以金币数量形式度量), 0 <= T <=100 注意不同的道路可能有相同的起点和终点。
输出
输入结果应该只包括一行，即从城市1到城市N所需要的最小的路径长度（花费不能超过K个金币）。如果这样的路径不存在，结果应该输出-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
参考答案：对于给定的输入，首先读取Bob能够在他路上花费的最大的金币数K，城市的数量N和道路的数量R。然后，根据输入的R条道路信息，建立从城市1到城市N的最短路径图。由于每条道路都是单向的，因此可以使用Dijkstra算法来找到最短路径。在Dijkstra算法中，我们需要维护一个距离数组，记录从起点到每个顶点的最短距离。初始时，将起点到起点的距离设为0，其他顶点的距离设为无穷大。然后，每次从未被访问过的顶点中选取距离最小的顶点，更新其邻居的距离。重复这个过程，直到找到从城市1到城市N的最短路径。最后，输出最短路径的长度。如果这样的路径不存在，输出-1。
解析：【喵呜刷题小喵解析】：
该题目要求找到从城市1到城市N的最短路径，并且要求Bob能够付得起通行费。因此，我们需要建立一个最短路径图，并使用Dijkstra算法来找到最短路径。在输入中，第一行包含一个整数K，表示Bob能够在他路上花费的最大的金币数。第二行包含整数N，表示城市的数量。第三行包含整数R，表示道路的数量。接下来的R行，每行具体指定几个整数S、D、L和T，表示道路的起点、终点、长度和通行费。
为了解决这个问题，我们可以使用Dijkstra算法来找到最短路径。在Dijkstra算法中，我们需要维护一个距离数组，记录从起点到每个顶点的最短距离。初始时，将起点到起点的距离设为0，其他顶点的距离设为无穷大。然后，每次从未被访问过的顶点中选取距离最小的顶点，更新其邻居的距离。重复这个过程，直到找到从城市1到城市N的最短路径。
在算法的实现中，我们需要使用一个优先队列来存储待访问的顶点，以及一个数组来记录每个顶点的最短距离。每次从未被访问过的顶点中选取距离最小的顶点，将其标记为已访问，并更新其邻居的距离。重复这个过程，直到找到从城市1到城市N的最短路径。
最后，我们需要检查是否存在从城市1到城市N的最短路径。如果存在，输出最短路径的长度；否则，输出-1。
需要注意的是，由于每条道路都是单向的，因此在建立最短路径图时，我们需要考虑道路的方向。另外，不同的道路可能有相同的起点和终点，因此在建立最短路径图时，我们需要考虑重复边的情况。
2、Freda的越野跑（2024.3八级）
Freda报名参加了学校的越野跑。越野跑共有N人参加，在一条笔直的道路上进行。这N个人在起点处站成一列，相邻两个人之间保持一定的间距。比赛开始后，这N个人同时沿着道路向相同的方向跑去。换句话说，这N个人可以看作x轴上的N个点，在比赛开始后，它们同时向x轴正方向移动。
假设越野跑的距离足够远，这N个人的速度各不相同且保持匀速运动，那么会有多少对参赛者之间发生“赶超”的事件呢？
时间限制：1000
内存限制：262144
输入
第一行1个整数N。 第二行为N 个非负整数，按从前到后的顺序给出每个人的跑步速度。 对于50%的数据，2<=N<=1000。 对于100%的数据，2<=N<=100000。
输出
一个整数，表示有多少对参赛者之间发生赶超事件。
样例输入
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之间不会发生赶超，因为速度快的起跑时就在前边。
参考答案：根据题目描述，我们可以使用归并排序的思想来解决这个问题。首先，我们需要对每个人的速度进行排序，然后遍历排序后的速度数组，计算赶超事件的数量。具体步骤如下：1. 对速度数组进行排序。2. 初始化赶超事件计数器为0。3. 遍历排序后的速度数组，对于第i个人，他会超过前面比他速度慢的人，赶超事件的数量等于前面比他速度慢的人数。4. 对于第i个人，前面比他速度慢的人数可以通过计算i-1-j，其中j是第一个速度大于第i个人的人的位置。5. 遍历结束后，输出赶超事件计数器。
解析：【喵呜刷题小喵解析】：
这个问题可以使用归并排序的思想来解决，也可以使用数学方法来解决。如果使用数学方法，我们可以观察到，对于第i个人，他会超过前面比他速度慢的人，赶超事件的数量等于前面比他速度慢的人数。我们可以通过计算i-1-j，其中j是第一个速度大于第i个人的人的位置，来得到这个数量。
在算法实现上，我们可以使用双指针的方法，一个指针指向当前位置，另一个指针指向后面第一个速度大于当前速度的位置。我们可以通过遍历排序后的速度数组，依次计算每个位置的赶超事件数量，最后将所有赶超事件数量相加即可得到总的赶超事件数量。
需要注意的是，由于题目中给出的数据范围较大，我们需要使用高效的算法来解决这个问题。归并排序是一种时间复杂度为O(nlogn)的排序算法，可以在较短时间内完成排序操作。同时，我们还需要注意内存限制，避免使用过多的内存空间。
在样例输入中，我们可以观察到，对于速度数组[1,3,10,8,5]，我们可以依次计算每个位置的赶超事件数量，得到赶超事件数量为7。这是因为第2个人会超过第1个人，第3个人会超过第1个人和第2个人，第4个人会超过第1个人、第2个人和第3个人，第5个人会超过第1个人、第2个人、第3个人和第4个人，而第3个人、第4个人和第5个人之间不会发生赶超事件。因此，赶超事件的数量为7。
3、Rainbow的商店（2024.3八级）
Rainbow开了一家商店，在一次进货中获得了N个商品。
已知每个商品的利润和过期时间。
Rainbow每天只能卖一个商品，并且过期商品不能再卖。
Rainbow也可以选择在每天出售哪个商品，并且一定可以卖出。
由于这些限制，Rainbow需要制定一份合理的售卖计划。请你计算一下，Rainbow最终可以获得的最大收益。
时间限制：1000
内存限制：262144
输入
第一行两个整数N。 接下来N行每行两个整数，分别表示每个商品的利润、过期时间。 1<=N,利润,时间<=10000。
输出
输出一个整数，表示Rainbow最终可以获得的最大收益。
样例输入
7 20 1 2 1 10 3 100 2 8 2 5 20 50 10
样例输出
185
提示
第1天卖出20 第2天卖出100 第3天卖出10 第4天卖出50（实际上只要在第10天卖就可以） 第5天卖出5（实际上只要在第20天前卖就可以） 总计185 其它2件商品由于过期、每天只能卖一个的限制，在最优策略下应该不出售。
参考答案：对于这个问题，我们可以使用动态规划来解决。我们可以定义一个数组dp，其中dp[i]表示在前i天可以获得的最大收益。对于每个商品，我们可以计算它的过期时间，然后将其按照过期时间从早到晚排序。然后，我们可以遍历每个商品，对于每个商品，我们可以选择在当天出售它，或者不出售它。如果我们选择出售这个商品，那么dp[j] = max(dp[j], dp[j-1] + 利润)，其中j是商品的过期时间。如果我们选择不出售这个商品，那么dp[j] = dp[j-1]。最后，dp[N]就是Rainbow最终可以获得的最大收益。
解析：【喵呜刷题小喵解析】：
这个问题是一个典型的动态规划问题，可以使用动态规划来解决。我们可以定义一个数组dp，其中dp[i]表示在前i天可以获得的最大收益。对于每个商品，我们可以计算它的过期时间，然后将其按照过期时间从早到晚排序。这样，我们就可以保证在每一天，Rainbow都有机会出售所有过期的商品。然后，我们可以遍历每个商品，对于每个商品，我们可以选择在当天出售它，或者不出售它。如果我们选择出售这个商品，那么dp[j] = max(dp[j], dp[j-1] + 利润)，其中j是商品的过期时间。如果我们选择不出售这个商品，那么dp[j] = dp[j-1]。最后，dp[N]就是Rainbow最终可以获得的最大收益。由于这个问题中，Rainbow每天只能卖一个商品，并且过期商品不能再卖，所以我们需要按照商品的过期时间从早到晚排序，这样可以保证在每一天，Rainbow都有机会出售所有过期的商品，从而获得最大的收益。
4、冰阔落 I（2024.3八级）
老王喜欢喝冰阔落。
初始时刻，桌面上有n杯阔落，编号为1到n。老王总想把其中一杯阔落倒到另一杯中，这样他一次性就能喝很多很多阔落，假设杯子的容量是足够大的。
有m 次操作，每次操作包含两个整数x与y。
若原始编号为x 的阔落与原始编号为y的阔落已经在同一杯，请输出"Yes"；否则，我们将原始编号为y 所在杯子的所有阔落，倒往原始编号为x 所在的杯子，并输出"No"。
最后，老王想知道哪些杯子有冰阔落。
时间限制：10000
内存限制：65536
输入
有多组测试数据，少于 5 组。 每组测试数据，第一行两个整数 n, m (n, m<=50000)。接下来 m 行，每行两个整数 x, y (1<=x, y<=n)。
输出
每组测试数据，前 m 行输出 "Yes" 或者 "No"。 第 m+1 行输出一个整数，表示有阔落的杯子数量。 第 m+2 行有若干个整数，从小到大输出这些杯子的编号。
样例输入
3 2 1 2 2 1 4 2 1 2 4 3
样例输出
No Yes 2 1 3 No No 2 1 4
参考答案：br />对于每组测试数据，首先初始化一个大小为n的数组，用于记录每个杯子是否含有阔落。然后，对于每次操作，检查编号为x的阔落与编号为y的阔落是否已经在同一杯中，如果在同一杯中则输出"Yes"，否则将编号为y所在杯子的所有阔落倒往编号为x所在的杯子，并输出"No"。最后，统计含有阔落的杯子数量，并输出这些杯子的编号。
解析：【喵呜刷题小喵解析】
这个问题可以用一个数组来解决。我们可以创建一个大小为n的布尔数组，其中n是杯子的数量。数组的索引是杯子的编号，值是一个布尔值，表示该杯子是否含有阔落。初始时，所有的杯子都不含有阔落，所以数组的所有元素都应该设置为false。
然后，对于每次操作，我们检查编号为x的阔落与编号为y的阔落是否已经在同一杯中。如果它们已经在同一杯中，那么输出"Yes"，否则，我们将编号为y所在杯子的所有阔落倒往编号为x所在的杯子。我们可以通过遍历数组来实现这一点，如果y所在的杯子含有阔落，我们将这个杯子的阔落标记为false，并将x所在的杯子的阔落标记为true。然后，我们输出"No"。
最后，我们统计含有阔落的杯子数量，并输出这些杯子的编号。我们可以通过遍历数组来实现这一点，如果某个杯子的阔落标记为true，那么我们就将它的编号添加到结果列表中，并将含有阔落的杯子数量加1。最后，我们按照编号从小到大的顺序输出这些杯子的编号。
需要注意的是，这个问题有多组测试数据，我们需要对每组测试数据都进行上述操作。我们可以在每次读取一组测试数据之前，清空数组，然后进行上述操作。
在代码实现时，我们需要读取输入，并根据上述算法进行操作，最后输出结果。具体的代码实现可以根据具体的编程语言和环境进行编写。
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
