2025年复旦大学计算机保研机试真题

本文整理复旦大学计算机保研机试真题，并提供详细解析与代码实现，帮助同学们了解保研机试的难度与题型分布

拼出fudan

题目描述

给定一个字符串 ${s}$，只包含英文字母（大小写均有）。你可以使用字符串中的字母来拼出单词 "fudan"（不区分大小写，即可以使用 'F' 或 'f' 表示 'f'，以此类推）。每个字母在字符串中只能使用一次。问：最多能拼出多少个完整的 "fudan"？

输入格式

一行字符串 ${s}$（长度范围：${1 \le |s| \le 1000}$），仅包含大小写英文字母。

输出格式

一个整数，表示最多能拼出多少个完整的 "fudan"。

数据范围

${1 \le |s| \le 1000}$

输入样例1

FfuUddaANNn

输出样例1

非日型皇后放置

题目描述

在一个 ${n \times n}$ 的国际象棋棋盘上，放置 ${m}$ 个皇后（Queen），要求满足以下所有条件：

传统皇后约束：
任意两个皇后不在同一行；
任意两个皇后不在同一列；
任意两个皇后不在同一条主对角线或副对角线上（即 ${|r_1 - r_2| \neq |c_1 - c_2|}$）。
新增“非日型”约束（No "Sun" pattern）：
任意两个皇后不能位于一个 ${2 \times 3}$ 或 ${3 \times 2}$ 矩形的两个对角顶点上（这类形状在中文语境中被称为“日”字形，类似“日”字的外框）。

“日”型举例（两个皇后在如下位置）：

${2 \times 3}$ 情况（横向矩形）：
${(r, c)}$ 和 ${(r+1, c+2)}$
${(r, c)}$ 和 ${(r+1, c-2)}$
${(r, c)}$ 和 ${(r-1, c+2)}$，等等
${3 \times 2}$ 情况（纵向矩形）：
${(r, c)}$ 和 ${(r+2, c+1)}$
${(r, c)}$ 和 ${(r+2, c-1)}$
${(r, c)}$ 和 ${(r-2, c+1)}$，等等

注意：这是矩形对角顶点，不是“马走日”（骑士移动）。

输入格式

一行两个整数：${n}$ 和 ${m}$（${1 \leq n \leq 10}$，${0 \leq m \leq n}$）

输出格式

一个整数，表示合法的放置方案总数。

数据范围

${1 \leq n \leq 10}$，${0 \leq m \leq n}$

输入样例1

3 2

输出样例1

输入样例2

4 2

输出样例2

可达方格数查询

题目描述

给定一个 $n \times n$ 的网格区域，每个格子包含数字 0 或 1。移动规则如下：

如果当前格子是 0，则可以移动到相邻（上、下、左、右）的 1 的格子。
如果当前格子是 1，则可以移动到相邻的 0 的格子。
允许重复经过同一个格子（即路径可以自交）。

进行 $m$ 次询问，每次询问给定一个坐标 $(x, y)$ 作为起点。对于每次询问，输出从该起点出发，能够访问到的不同方格的最大数量。

关键说明：由于可以重复经过格子，但只关心不同方格的数量（即每个格子只计数一次），因此问题等价于求包含起点的连通分量大小。连通性由移动规则定义：两个格子连通当且仅当存在一条满足移动规则的路径连接它们（不考虑路径长度）。

输入格式

第一行：两个整数 $n$ 和 $m$（$1 \leq n \leq 1000$，$1 \leq m \leq 10^5$）
接下来 $n$ 行：每行一个长度为 $n$ 的字符串，由字符 '0' 和 '1' 组成，表示网格
接下来 $m$ 行：每行两个整数 $x$ 和 $y$（$0 \leq x, y < n$），表示询问的坐标

输出格式

对于每个询问，输出一个整数，表示从 $(x,y)$ 出发能访问到的不同方格的最大数量。

数据范围

$1 \leq n \leq 1000$，$1 \leq m \leq 10^5$

输入样例1

输出样例1

9
9

INTa语言解释器

题目描述

实现一个简单的编程语言解释器，用于执行INTa语言程序。该语言支持以下语句：

INTa：定义一个变量a（变量名为单个字母），初始值为0
a=exp：为变量a赋值，其中exp是表达式
PRINTexp：输出表达式exp的计算结果
IF exp...ENDIF：条件语句，如果exp的值非0，则执行IF和ENDIF之间的语句

表达式计算规则：

从左到右计算，不考虑运算符优先级
例如：${2+34}$ 计算为 ${(2+3)4 = 20}$，而不是 ${2+(3*4) = 14}$
例如：${5-32}$ 计算为 ${(5-3)2 = 4}$，而不是 ${5-(3*2) = -1}$
支持的操作符：
${+}$：加法
${-}$：减法
${*}$：乘法
${/}$：整数除法（向0取整）
${\&}$：按位与
^：按位异或
操作数类型：
立即数：0-999之间的整数
变量：单个字母（a-z）
除法规则：整数除法，向0取整
例如：${7/3 = 2}$，${-7/3 = -2}$
按位运算：按照标准规则执行

作用域规则：

每个IF语句创建一个新的作用域
允许在不同作用域内重新定义变量：
在IF内部可以重新定义变量，这些变量在ENDIF后不再存在
外部作用域的变量在内部作用域可见，但可能被覆盖
变量查找规则：
从内层到外层依次查找变量
赋值时，修改最近作用域中已存在的变量，或在当前作用域定义新变量

程序执行规则：

语句按顺序执行
IF语句根据条件决定是否执行其内部语句
变量在定义前不可使用（假设输入总是合法的）

输入格式

多行字符串，表示INTa语言的程序
每行一个语句
语句类型包括：
INTa：定义变量（a为单个字母）
a=exp：赋值语句（a为单个字母）
PRINTexp：打印语句
IF exp：条件开始
ENDIF：条件结束

输出格式

对于每个PRINT语句，输出表达式计算结果
每个结果占一行

数据范围

输入程序不超过100行
变量名均为单个小写字母（a-z）
立即数范围为0-999

输入样例1

INTa
a=5
INTb
b=3
PRINTa+b
PRINTa-b
PRINTa*b
PRINTa/b
PRINTa&b
PRINTa^b

输出样例1

最长不下降子序列

题目描述

给定一个初始为空的动态数组，支持以下两种操作：

添加操作：在数组末尾添加一个整数
删除操作：删除数组末尾的元素

每次操作后，需要输出当前数组的最长不下降子序列（Longest Non-decreasing Subsequence，简称LNDS）的长度。

什么是不下降子序列？

不下降子序列是指从原序列中选出的一个子序列（元素在原序列中不一定连续），满足其中的元素按顺序不下降（即每个元素都不小于前一个元素）。
例如，对于序列 [5, 3, 4, 1, 2]，最长不下降子序列可以是 [3, 4] 或 [1, 2]，长度为 2。

操作特点：

数组初始为空
只在末尾进行添加和删除操作
每次操作后需要立即输出当前数组的LNDS长度
保证删除操作时数组非空

输入格式

第一行：一个整数 ${q}$（${1 \leq q \leq 10^5}$），表示操作次数
接下来 ${q}$ 行：每行一个操作，格式为：
${1\ x}$：表示添加操作，${x}$ 为要添加的整数（${1 \leq x \leq 10^9}$）
${2}$：表示删除操作

输出格式

对于每个操作（包括添加和删除），输出一行，表示操作后最长不下降子序列的长度

数据范围

${1 \leq q \leq 10^5}$
${1 \leq x \leq 10^9}$

输入样例1

输出样例1

完整题目及在线评测：https://www.pgcode.cn/

拼出fudan

题目描述

输入格式

输出格式

数据范围

输入样例1

输出样例1

非日型皇后放置

题目描述

输入格式

输出格式

数据范围

输入样例1

输出样例1

输入样例2

输出样例2

可达方格数查询

题目描述

输入格式

输出格式

数据范围

输入样例1

输出样例1

INTa语言解释器

题目描述

输入格式

输出格式

数据范围

输入样例1

输出样例1

最长不下降子序列

题目描述

输入格式

输出格式

数据范围

输入样例1

输出样例1

相关机试真题