YLT C++ 5级 2024.03

N4129 [CIE 202403 五级 T1] 逃离迷宫

题目描述

你在一个地下迷宫中找到了宝藏，但是也触发了迷宫机关，导致迷宫将在 $T$ 分钟后坍塌，为此你需要在 $T$ 分钟内逃离迷宫，你想知道你能不能逃离迷宫。
迷宫是一个边长为 $m$ 的正方形，其中 S 表示你所在的位置，E 表示迷宫出口，. 是可以随意走动的区域，# 是不可穿行的墙壁，每次你可以耗费 $1$ 分钟在区域间移动（上下左右四个方向）。

输入格式

输入包含多组数组，第一行是一个整数 $K$（$1 \leq K \leq 10$），表示有 $K$ 组数据。
接下来每组数组包含整数 $m$（$2 \leq m \leq 10$）和整数 $T$，$m$ 表示正方形迷宫的边长，$T$ 表示坍塌时间。
其后是一个 $m \times m$ 的字符矩阵，包含字符 S, E, . 和 #。

输出格式

每组数据输出一行，输出 YES 或者 NO，表示是否可以在坍塌之前逃离（也就是说移动次数是否可以不超过 $T$）。

样例

样例 1
输入：

2
4 7
S...
###.
.#E.
..#.
3 4
S..
..#
.#E

输出：

YES
NO

N4130 [CIE 202403 五级 T2] 密室逃脱

题目描述

小 $Y$ 喜欢玩密室逃脱，每次游戏开始时，小 $Y$ 会进入一个密室，她需要按照顺序解开各个隐藏线索才能成功逃脱密室。小 $Y$ 非常聪明，解开线索对她来说并不难，但是她有一点懒，她希望在通关过程中移动次数最少。请你帮小 $Y$ 计算她至少要移动多少次才能成功通关。
密室是 $m$ 行 $n$ 列的格子矩阵，小 $Y$ 从左上角 $(1,1)$ 进入密室，密室中有三种格子:
墙，以数字 $0$ 标记
路，以数字 $1$ 标记
隐藏线索处，以数字 $(> 1)$ 标记，代表该线索的难度
小 $Y$ 需要按照难度递增的顺序解开各个线索，逃脱密室。

输入格式

第一行是一个整数 $T$，表示输入包含 $T$ 组数据，分别是不同的游戏中小 $Y$ 所处的密室。
对于每组数据，第一行包括两个整数：$m$（$1 \leq m \leq 100$）、$n$（$1 \leq n \leq 100$）。
接下来 $m$ 行，每行有 $n$ 个数字，第 $i$ 行的第 $j$ 个数字表示密室中第 $i$ 行第 $j$ 列的格子的类型。 题目保证进入密室处 $(1,1)$ 不是墙壁，线索的难度都不相同。

输出格式

对于每组数据，你需要输出一个整数，表示小 $Y$ 在这个密室中至少要移动多少次才能成功通关。 如果小 $Y$ 不可能解开所有线索，输出 $-1$.

样例

样例 1
输入：

2
3 3
1 3 2
1 0 4
10 6 5
3 3
1 3 2
0 0 0
10 6 5

输出：

8
-1

提示

样例解释：由于需要按难度顺序解开线索，在第一组数据中，小 $Y$ 第一次移动到 $3$ 时不能解密，在完成 $2$ 之后需要回到 $3$。最后小 $Y$ 解开 $10$ 时，她成功通关。

N4131 [CIE 202403 五级 T3] 交易市场

题目描述

市场里面一共有 $n$ 种物品，有 $m$ 种交易途径，每个交易途径可以由 $(x, y, z)$ 表示，意思是可以用第 $x$ 种物品换成第 $y$ 种物品，并且得到 $z$ 元的收益（$z$ 均大于 $0$）。最开始你只有第一种物品，请问最多可以赚取多少收益。

输入格式

第一行两个正整数 $n$ 和 $m$ ($n \leq 1000$，$m \leq 4000$)。
接下来 $m$ 行，每行三个正整数 $x$、$y$、$z$，意思是可以用第 $x$ 种物品换成第 $y$ 种物品，并且得到 $z$ 元的收益。（$1 \leq x, y \leq n$, $1 \leq z \leq 100$）

输出格式

一个整数表示最大收益，如果可以赚取无穷多的收益则输出 $10^9$

样例

样例 1
输入：

3 3
1 2 2
2 3 3
1 3 4

输出：

5

N4132 [CIE 202403 五级 T4] 逆序对个数

题目描述

给定 $N$ 个数的序列 $a_1, a_2, \ldots, a_N$，定义一个数对 $(a_i, a_j)$ 为“重要逆序对”的充要条件为 $i 2a_j$。求给定序列中“重要逆序对”的个数。

输入格式

本题有多个测试点，每个测试点分为两行：
第一行为序列中数字的个数 $N$（$1 \leq N \leq 200000$），
第二行为序列 $a_1, a_2, \ldots, a_N$（$0 \leq a \leq 10000000$），由空格分开。$N=0$ 表示输入结束。

输出格式

每个测试点一行，输出一个整数，为给序列中“重要逆序对”的个数。

样例

样例 1
输入：

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

输出：

16

提示

请注意答案范围，如果使用 printf 输出 long long 类型，请用 %lld