发帖
雷达卡
2025年南京大学计算机复试上机真题解析
子序列问题
时间限制：1000 ms
内存限制：256 mb
在字符串处理中，“子序列”指的是从原字符串中按原有字符顺序选取若干字符形成的新字符串，不要求连续。例如，对于字符串 "XianYuDalaoTaiQiangLa!"，"XDoi"、"XianYu!"、"loa" 等都是其合法的子序列。
若一个字符串 t 同时是两个字符串 s1 和 s2 的子序列，则称 t 为它们的公共子序列。我们定义 s1 与 s2 的相似度为其最长公共子序列（LCS）的长度。
现给出一个主文本串 S 及一组模式串 T[1] 到 T[n]，要求找出其中与 S 相似度最高的那个模式串，并输出该最大相似度值。所有字符串仅包含小写字母。
输入格式说明：
首行为字符串 S；
第二行为整数 n（1 ≤ n ≤ 100）；
接下来 n 行每行一个模式串 T[i]；
S 和每个 T[i] 的长度均不超过 2000。
输出格式说明：
第一行为与 S 最相似的模式串（若有多个取第一个）；
第二行为对应的最高相似度数值。
样例输入：
abcdef 4 acfaff appont emmm bdxeuf
样例输出：
bdxeuf 4
奶牛位置追踪
时间限制：1000 ms
内存限制：256 mb
农夫 John 正在寻找他走失的奶牛。假设地图是一条无限长的数轴，John 起始位于位置 s，而奶牛静止不动地待在位置 t（0 ≤ s, t ≤ 100000）。每分钟，John 可以选择以下三种移动方式之一：
- 从当前位置 x 移动到 x + 1
- 从 x 移动到 x - 1
- 从 x 瞬间移动到 2 * x
由于奶牛不会移动，目标是计算 John 到达位置 t 所需的最短时间（单位：分钟）。
输入格式说明：
一行两个整数 s 和 t，表示 John 的初始位置和奶牛的位置。
输出格式说明：
第一行为最少所需时间（分钟数）；
第二行为一条可行的最短路径示例（用箭头连接各步骤位置）。
样例输入：
5 17
样例输出：
4 5->4->8->16->17
京公网安备 11010802022788号
