2025年上海交通大学计算机保研机试真题
本文整理上海交通大学计算机保研机试真题，并提供详细解析与代码实现，帮助同学们了解保研机试的难度与题型分布
最长连续递增序列
题目描述
给定一个未经排序的整数数组，找到最长且连续递增的子序列，并返回该序列的长度。
连续递增的子序列可以由两个下标 $l$ 和 $r$ ($l < r$) 确定，如果对于每个 $l <= i < r$，都有 $nums[i] < nums[i + 1]$，那么子序列 $[nums[l], nums[l + 1], ..., nums[r - 1], nums[r]]$ 就是连续递增子序列。
输入格式
第一行输入一个整数 $n$ 表示数组的长度。
第二行输入 $n$ 个数 $nums[i]$。
($1 <= n <= 10^4$, $-10^9 <= nums[i] <= 10^9$)
输出格式
输出最长连续递增子序列长度。
输入样例
5
1 3 5 4 7
输出样例
3
Fibonacci
题目描述
The Fibonacci Numbers $ {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...} $ are defined by the recurrence:
$ F_0 = 0 $, $ F_1 = 1 $, $ F_n = F_{n-1} + F_{n-2} $ $ (n \geq 2) $.
Write a program to calculate the Fibonacci Numbers.
输入格式
Each case contains a number $ n $, and you are expected to calculate $ F_n $ $ (0 \leq n \leq 30) $.
输出格式
For each case, print a number $ F_n $ on a separate line, which means the $ n $th Fibonacci Number.
输入样例
1
输出样例
1
整除问题
题目描述
给定 $n$, $a$，求最大的 $k$，使 $n!$ 可以被 $a^k$ 整除但不能被 $a^{k+1}$ 整除。
输入格式
两个整数 $n$ $(2 \leq n \leq 1000)$, $a$ $(2 \leq a \leq 1000)$
输出格式
一个整数。
输入样例
6 10
输出样例
1
WERTYU
题目描述
A common typing error is to place the hands on the keyboard one row to the right of the correct position. So $ Q $ is typed as $ W $ and $ J $ is typed as $ K $ and so on. You are to decode a message typed in this manner.
输入格式
Input consists of several lines of text. Each line may contain digits, spaces, upper case letters (except $ Q $, $ A $, $ Z $), or punctuation shown above [except back-quote ($ '$)]. Keys labelled with words [Tab, Backsp, Control, etc.] are not represented in the input.
输出格式
You are to replace each letter or punctuation symbol by the one immediately to its left on the $ QWERTY $ keyboard shown above. Spaces in the input should be echoed in the output.
输入样例
O S,GOMR YPESU/
输出样例
I AM FINE TODAY.
棋盘游戏
题目描述
有一个 $6 \times 6$ 的棋盘，每个棋盘上都有一个数值。
现在有一个起始位置和终止位置，请找出一个从起始位置到终止位置代价最小的路径：
-
只能沿上下左右四个方向移动。
-
总代价是每走一步的代价之和。
-
每步（从 $(a,b)$ 到 $(c,d)$）的代价是 $(c,d)$ 上的值与其在 $(a,b)$ 上的状态的乘积。
-
初始状态为 $1$，每走一步，状态按如下公式变化：（走这步的代价 $mod$ $4$）$+$ $1$。
输入格式
每组数据一开始为 $6 \times 6$ 的矩阵，矩阵的值为大于等于 $1$ 小于等于 $10$ 的值，然后四个整数表示起始坐标和终止坐标。
输出格式
输出最小代价。
输入样例
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
0 0 5 5
输出样例
23