## 24年程设期末

#### 题 1 短跑比赛

##### 题目描述

一场短跑比赛只有 A B C D 四人参加. 赛后向裁判询问排名情况, 他们分别作出如下回答:

A 说 B 是第 $i_1$ 名 C 是第 $j_1$ 名
B 说 C 是第 $i_2$ 名 D 是第 $j_2$ 名
C 说 D 是第 $i_3$ 名 A 是第 $j_3$ 名
D 说 A 是第 $i_4$ 名 B 是第 $j_4$ 名

已知每个人的回答都是对且只有一半是正确的, 即每个人说的两句话中恰好一句为真另一句为假. 且每个人的名次互不相同, 即最终排名为 $1, 2, 3, 4$ 的一个排列.

其中 $i_1, i_2, i_3, i_4, j_1, j_2, j_3, j_4$ 均为 1 到 4 的整数.

问四个人的名次有哪些可能情况.

##### 输入描述

共两行,
第一行为四个数分别对应 $i_1, i_2, i_3, i_4$ 各数之间用空格隔开,
第二行为四个数分别对应 $j_1, j_2, j_3, j_4$ 各数之间用空格隔开.

##### 输出描述

一行或多行,
每行对应一种可能情况包含 4 个数字依次代表 A B C D 的名次用空格隔开,
如果有多行就按照 ABCD 名次组成的四位整数数值由小到大排序输出,
如果输入的测试数据按题目描述得不到符合要求的排名则输出 $-1$

------

#### 2 符号信息密码

##### 题目描述

给定一段符号信息, 由多个英文单词构成其中, 有些单词是英语中表示数字的单词, 为了脱困需要依次完成如下操作任务:

1. 从符号信息中找到所有表示数字的单词, 这些数字单词形式上可能是大小写混合的, 例如` ZeRo OnE tWelve` 等
2. 对于上述任务中找到的每个数字单词, 计算它包含的所有字符的 ASCII 码值之和
3. 对于上述任务中得到的数值序列, 将其中每个数值都对 $1004$ 取模
4. 将上述任务取模得到的数按数值从小到大排序
5. 将上述任务排序后的数值拼接成一个新的数. 规则为

- 如果被拼接的数小于 $10$ 拼接时在前面补一个字符 $0$
- 如果最终拼接所得的新数开头有一个或多个 $0$ 则去掉这些 $0$
- 但如果所有数字全是 $0$ 则保留 $1$ 个 $0$

正确完成上述 $5$ 步后即可得到最终的字符串密码
数字单词表示的数字是 $0$ 到 $154 中的某一个
即 `zero one two three four five six seven eight nine ten eleven twelve thirteen fourteen fifteen`

##### 输入描述

第一行包含一个整数 $n$ ($0 < n \le 1000$) 表示符号信息中的单词个数
第二行包含 $n$ 个单词, 这些单词之间由空格隔开, 其中有 $m$ ($0 < m \le 9$) 个是表示数字的英文单词

##### 输出描述

输出一行代表最终的字符串密码

##### 样例输入

样例 1 输入

```
8
The apple price is seven point tWelve four
```

样例 2 输入

```
1
eleveN
```

------

#### 3 注意力机制计算

##### 题目描述

注意力机制是一种重要的深度学习方法, 广泛应用于自然语言处理计算机视觉等领域
设有三个二维矩阵分别代表查询矩阵 $Q$ , 键矩阵 $K$ 和值矩阵 $V$, 它们的列数均为 $d$
其中查询矩阵 $Q$ 有 $M$ 行代表 $M$ 个查询向量
键矩阵 $K$ 和值矩阵 $V$ 均有 $N$ 行代表 $N$ 个键值向量对

方法的具体计算过程如下

(1) 计算注意力得分矩阵 $S$
$$ S = \frac{Q K^T}{\sqrt{d}} $$
其中 $K^T$ 是 $K$ 矩阵的转置

(2) 计算注意力权重矩阵 $W$
将注意力得分矩阵 S 各行元素按如下式进行归一化. 该操作被称为 softmax.
对矩阵 $S$ 中的任意行该行中的 N 个元素 $x_1, x_2, ... ,x_N$ 被转换成 $N$ 个新元素 $y_1, y_2, ... ,y_N$
$$ y_i = \frac{e^{x_i}}{\sum_{j=1}^{N} e^{x_j}} \ , \ i = 1 ... N $$
这些新元素构成注意力权重矩阵 W 的相应行

(3) 计算上下文矩阵 $C$
$$ C = W V $$

提示
(1) C++ 的库函数中有原型为 double pow ( double a , double b ) 的函数, 该函数返回 a 的 b 次幂, 使用时需要 `#include<cmath>`
(2) 在编程实现归一化计算时需将公式中的自然常数 $\text{e}$ 设置为 $2.7182818$
(3) 所有测试数据保证计算时的中间结果不会超出 `double` 类型的表示范围

##### 输入描述

第一行输入 3 个正整数 $M$, $N$, $D$
接下来 $M$ 行每行 $d$ 个浮点数这 $M$ 行数据构成一个 $M \times d$ 的矩阵表示查询矩阵 $Q$
接下来 $N$ 行每行 $d$ 个浮点数这 $N$ 行数据构成一个 $N \times d$ 的矩阵表示键矩阵 $K$
接下来 $N$ 行每行 $d$ 个浮点数这 $N$ 行数据构成一个 $N \times d$ 的矩阵表示值矩阵 $V$

------

#### 题 3 矩形上下边点对最短距离

##### 题目描述

给定一个 $m \times 1$ 的矩形 ( $m$ 是正整数 ) 它的四个顶点分别是 $( 0, 0 ), ( 0, 1 ), ( m, 0 ), ( m, 1 )$

在矩形的上横边有 $p$ 个点坐标分别为 $( a_0, 1 ), ( a_1 1 ) , ... , ( a_{p-1}, 1 )$

在矩形的下横边有 q 个点坐标分别为 $( b_0, 0 ), ( b_1, 0 ), ... , ( b_{q-1}, 0 )$

其中 $a_i$ 和 $b_i$ 均为正整数且满足
$0 \le a_0 < a_1 < ... < a_{p-1} < m$
$0 \le b_0 < b_1 < ... < b_{q-1} < m$

任意的 $( a_i, 1 )$ 和 $( b_j, 0 )$ 可以组成一个点对, 请找出所有点对中距离最短的输出这个最短距离

距离的计算公式为
$$ \sqrt{ ( ai - bj )^2 + ( 1 - 0 )^2 } $$

##### 输入描述

第一行为 $3$ 个整数用空格隔开分别为 $m, p, q$
第二行为 $p$ 个整数用空格隔开分别表示 $a_0 ... a_{p-1}$
第三行为 $q$ 个整数用空格隔开分别表示 $b_0 ... b_{q-1}$

##### 输出描述

一个浮点数表示点对的最短距离要求按照四舍五入保留 2 位小数

------

#### 5 空间跳跃

##### 题目描述

Alice 是一位勇敢的宇航员最近他发现了一个神秘的星际游戏 空间跳跃 规则如下
游戏中包含一个 $N \times M$ 列的网格按行列编号格子可进行编号格点为 $(1, 1), (1, 2), ... (1, M), (2, 1),  ...  , (N, M)$
格子具有三种类型类型 $1$ , 类型 $2$ , 类型 $3$
当玩家位于 $(i, j)$ 时跳跃时受到限制如下

(1) 类型 $1$ 时允许玩家跳跃到格子 $(2i, j)$ 或 $(i, 2j)$
(2) 类型 $2$ 时允许玩家跳跃到格子 $(2i, j)$ 或 $(i, 2j)$ 或 $(i+1, j)$ 或 $(i, j + 1)$ 中的一个
(3) 类型 $3$ 时玩家无法跳跃到任何格子

注 跳跃只能在网格内进行不能跳跃到网格外

现在请你帮 Alice 编写一个程序计算从格子 $(1, 1)$ 出发最少跳跃多少次才能成功抵达格子 $(N, M)$

##### 输入描述

第一行为两个正整数 $N$ 和 $M$ 用空格隔开代表格子的行数和列数
接下来 $N$ 行每行 $M$ 个正整数用空格隔开分别代表该行对应格子的类型 $t$ ( $t$ 属于 $\{ 1 , 2 , 3 \}$ )

##### 输出描述

输出一个整数代表 Alice 从到的最少跳跃次数
当无法抵达格子 $(N , M)$ 时输出 $-1$

##### 样例输入

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