2025年华东师范大学计算机保研机试真题
本文整理华东师范大学计算机保研机试真题，并提供详细解析与代码实现，帮助同学们了解保研机试的难度与题型分布
矩阵中的第K大数
题目描述
给出一个长度为 $n$ 的数列和一个长度为 $m$ 的数列，可以构造得到一个 $n \times m$ 的矩阵 $C$，其中 $C_{ij} = A_i \times B_j$。
给出整数 $K$，你需要求出 $C$ 中的第 $K$ 大的数的值（$K$ 从 1 开始计数）。
输入格式
第一行输入三个整数 $n$, $m$, $K$ $(1 \leq n, m \leq 10^5, 1 \leq K \leq n \times m)$。
第二行输入 $n$ 个空格隔开的整数 $A_1, A_2, \ldots, A_n$ $(-10^9 < A_i < 10^9)$。
第三行输入 $m$ 个空格隔开的整数 $B_1, B_2, \ldots, B_m$ $(-10^9 < B_i < 10^9)$。
输出格式
输出一行一个整数，表示矩阵中的第 $K$ 大的数的值。
输入样例
3 3 7
5 4 1
4 5 3
输出样例
5
Minimum_Sum
题目描述
你有一个序列 $a_1$, $a_2$, $\ldots$, $a_n$，然后给你一些区间 $[l, r]$。
对于每一个区间，你需要找到下式的最小值，对于所有可能的 $x$：
$$\sum_{i=l}^{r} |x - a_i|$$
输入格式
第一行一个整数 $N$ $(N \leq 10^5)$ 代表序列长度。
接下来一行有 $N$ 个正整数 $a_i$ $(1 \leq a_i \leq 10^9)$，用空格隔开。
接下来一行一个整数 $Q$ $(1 \leq Q \leq 10^5)$，代表询问的区间次数。
接下来 $Q$ 行，每行一个区间 $l$, $r$ $(1 \leq l \leq r \leq N)$。
输出格式
输出 $Q$ 行。
每行代表对应的区间的结果。
输入样例
5
2 3 3 4 4
3
1 2
2 2
2 5
输出样例
1
0
2
阿拉伯数字转罗马数字
题目描述
罗马数字是古罗马使用的记数系统，现今仍很常见。
罗马数字有七个基本符号： $I$、 $V$、 $X$、 $L$、 $C$、 $D$、 $M$。
对应的阿拉伯数字分别为 $1$、 $5$、 $10$、 $50$、 $100$、 $500$、 $1000$。
需要注意的是罗马数字与十进位数字的意义不同，它没有表示零的数字，与进位制无关。
按照下述的规则可以表示任意正整数。
“标准”形式：
-
重复次数：一个罗马数字重复几次，就表示这个数的几倍。
-
右加左减：
-
在较大的罗马数字的右边记上较小的罗马数字，表示大数字加小数字。
-
在较大的罗马数字的左边记上较小的罗马数字，表示大数字减小数字。
-
左减的数字有限制，仅限于 $I$、 $X$、 $C$。
例如 $45$ 表示 $XLV$，而不是 $VL$。
-
左减时不可跨越一个位值。
例如， $99$ 是 $XCIX$ ($[100-10] + [10-1]$)，而不是 $IC$ ($[100-1]$)。
等同于阿拉伯数字每位数字分别表示。
-
左减数字必须为一位，比如 $8$ 是 $VIII$，而不用 $IIX$。
-
罗马数字 $V$、 $L$、 $D$ 中的任何一个放在较大的罗马数字右边只能使用一个。
-
右加连续相同数字不超过三位，比如 $14$ 是 $XIV$，而不是 $XIIII$。
现在给出一个阿拉伯数字表示的十进制正整数，输出其对应的罗马数字。
输入格式
一行十进制整数 $n$ ($1 \leq n \leq 1000$)
输出格式
一行字符串，表示对应的罗马数字
输入样例
3
输出样例
III
求30的倍数
题目描述
输入一个数，比如 $201$，让数字随意组合，是否能组合出 $30$ 的倍数。
如果能够组合成 $30$ 的倍数，就输出最大的倍数，不能就输出 $-1$。
例如输入 $201$ 可以随意组合成 $201$、$210$、$012$、$021$、$102$、$120$ 等数字，其中 $120$、$210$ 都是 $30$ 的倍数，由于要找最大的，所以答案是 $210$。
输入格式
一个整数。
输出格式
如果能组合成 $30$ 的倍数，输出最大的倍数；否则输出 $-1$。
输入样例
201
输出样例
210
差分计数
题目描述
给定 $n$ 个整数 $a_1 \ldots a_n$ 和一个整数 $x$。
求有多少有序对 $(i, j)$ 满足 $a_i - a_j = x$。
输入格式
第一行两个整数 $n$ $(1 \leq n \leq 2 \times 10^5)$，$x$ $(-2 \times 10^5 \leq x \leq 2 \times 10^5)$，分别代表整数的个数和题目中的 $x$。
第二行 $n$ 个用空格隔开的整数，第 $i$ 个代表 $-2 \times 10^5 < a_i \leq 2 \times 10^5$。
输出格式
一行一个整数，代表满足 $a_i - a_j = x$ 的有序对 $(i, j)$ 个数。
输入样例
5 1
1 1 5 4 2
输出样例
3