2024中山大学研保研上机真题
2024中山大学研保研上机真题
2024中山大学研究生保研上机真题
2024中山大学研保研上机真题
中山大学计算机学院夏令营上机真题
楼层移动方案-计算机学院夏令营
题目描述
有一栋高楼，共有 H H H 层，楼层编号为 1 , 2 , … , H 1,2,\dots,H 1,2,…,H。
- 住户 1 1 1 初始在 1 1 1 楼；
- 住户 2 2 2 初始在 H H H 楼。
每天，两位住户各自选择上或下移动一层（即住户 1 1 1 可以从楼层 x x x 移动到 x − 1 x-1 x−1 或 x + 1 x+1 x+1，但不能超出 [ 1 , H ] [1,H] [1,H]；住户 2 2 2 同理）。
给定一个天数 D D D，以及目标楼层 h 1 h_1 h1, h 2 h_2 h2。请问：经过恰好 D D D 天后，住户 1 1 1 到达 h 1 h_1 h1，且住户 2 2 2 到达 h 2 h_2 h2，一共有多少种不同的移动方案？答案可能很大，请输出对 10 9 + 7 10^9+7 109+7 取模后的结果。
输入格式
H D h1 h2输出格式
ans其中 a n s ans ans 表示合法方案数。
数据范围
- 1 ≤ H ≤ 100 1 \le H \le 100 1≤H≤100
- 1 ≤ D ≤ 100 1 \le D \le 100 1≤D≤100
- 1 ≤ h 1 , h 2 ≤ H 1 \le h_1, h_2 \le H 1≤h1,h2≤H
输入样例
5 2 3 3输出样例
1样例说明
两天后住户 1 到 3 楼、住户 2 到 3 楼的方案：
- 第一天：1→2，5→4；第二天：2→3，4→3
- 第一天：1→2，5→4；第二天：2→3，4→5（不行，没到 h2）
- 第一天：1→2，5→4；第二天：2→1，4→3（不行，没到 h1）
……最终只有1种方案满足条件。
判断无向图连通性-计算机学院夏令营
题目描述
给定一个 n n n 个点、 m m m 条边的无向图。请判断给定的两点 s s s, t t t 是否连通。
输入格式
第一行包含两个整数 n n n 和 m m m，表示点数和边数。
接下来 m m m 行，每行包含两个整数 u i u_i ui, v i v_i vi，表示一条无向边。
最后一行包含两个整数 s s s 和 t t t，表示要判断的两个点。
输出格式
如果
s
s
s 与
t
t
t 连通，输出 YES，否则输出 NO。
数据范围
- 1 ≤ n ≤ 10 5 1 \leq n \leq 10^5 1≤n≤105
- 0 ≤ m ≤ 2 × 10 5 0 \leq m \leq 2 \times 10^5 0≤m≤2×105
- 1 ≤ u i , v i , s , t ≤ n 1 \leq u_i, v_i, s, t \leq n 1≤ui,vi,s,t≤n
输入样例
5 3
1 2
2 3
4 5
1 3输出样例
YES样例说明
1–2–3 连通，因此 1 和 3 可达。
字符串映射-计算机学院夏令营
题目描述
给定两个字符串 A 和 B，长度相同。
我们说 A 和 B 是 同构的，如果存在一个唯一的映射（一一对应的字符映射关系）：
- 把 A 中的每个字符用某个固定字符替换（同一字符只能替换成同一个字符，不同字符不能替换成同一个字符）；
- 经过映射后，字符串 A 变为字符串 B。
请判断是否存在这样的唯一映射。
输入格式
第一行输入字符串 A
第二行输入字符串 B
输出格式
如果存在唯一映射，输出 “YES”；否则输出 “NO”。
数据范围
- 1 ≤ ∣ A ∣ , ∣ B ∣ ≤ 10 5 1 \leq |A|, |B| \leq 10^5 1≤∣A∣,∣B∣≤105
- A, B 仅包含小写字母（a–z）
输入样例
egg
add输出样例
YES样例说明
e→a，g→d，映射唯一，成立。
括号平衡
题目描述
给定一个只包含 '[' 与 ']' 的字符串
s
s
s，长度为偶数，并且 '[' 与 ']' 的数量相等。
未被照亮的点-计算机学院夏令营
题目描述
给定一个 H × W H \times W H×W 的网格，每个格子可能是：
- ‘.’ 空点
- ‘#’ 障碍
- ‘C’ 蜡烛