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 符号信息密码
题目描述
给定一段符号信息, 由多个英文单词构成其中, 有些单词是英语中表示数字的单词, 为了脱困需要依次完成如下操作任务:
- 从符号信息中找到所有表示数字的单词, 这些数字单词形式上可能是大小写混合的, 例如
ZeRo OnE tWelve等 - 对于上述任务中找到的每个数字单词, 计算它包含的所有字符的 ASCII 码值之和
- 对于上述任务中得到的数值序列, 将其中每个数值都对 $1004$ 取模
- 将上述任务取模得到的数按数值从小到大排序
- 将上述任务排序后的数值拼接成一个新的数. 规则为
- 如果被拼接的数小于 $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