2025年东北大学计算机考研复试机试真题解析

以下为历年东北大学计算机相关专业研究生复试中可能出现的机试题目整理与分析，涵盖典型算法设计与数据结构应用问题。

K 上升段-0

问题描述

考虑自然数序列 1 到 n 的一个排列 A[1..n]，可以将其划分为若干个连续的单调递增子序列。每个子序列满足如下条件：

• 起始和结束位置 st 与 ed 满足：1 ≤ st, ed ≤ n；
• 在区间 [st, ed) 内，有 A[i] < A[i+1]，即严格递增；
• 该段终止于末尾（ed = n）或下一个元素更小（A[ed] > A[ed+1]）。

例如，排列 1 2 4 5 6 3 9 10 7 8 可以被划分为三个递增段：

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

因此这是一个具有 3 个上升段的排列，称为“3 上升段序列”。

现给定整数 n 和 k，要求计算从 1 到 n 的所有排列中，恰好包含 k 个上升段的排列总数。

输入格式

仅一行，包含两个整数 n 和 k，其中 1 ≤ n ≤ 20，1 ≤ k ≤ n。

输出格式

输出一个整数，表示长度为 n 的排列中，恰好有 k 个上升段的排列数量。

样例输入

3 2

样例输出

4

数组对数-0

问题描述

给定两个按升序排列的整数数组 A 和 B，以及一个目标值 x。数组下标从 0 开始计数。

需要找出一对下标 (i, j)，使得 A[i] + B[j] = x 成立。题目保证存在唯一解。

输入格式

• 第一行包含三个整数：n（数组 A 的长度）、m（数组 B 的长度）、x（目标和）；
• 第二行为 n 个升序排列的整数，代表数组 A；
• 第三行为 m 个升序排列的整数，代表数组 B。

输出格式

输出一行，包含两个整数 i 和 j，表示满足条件的下标对。

数据范围说明

• 数组长度不超过 100000；
• 同一数组内的元素互不相同；
• 所有元素的取值范围为 [1, 10^9]。

样例输入

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

样例输出

1 1