复旦大学计算机科学与技术/电子信息/软件工程机试题解

声 明：

1、复旦大学机试不采用OJ判定，无具体数据范围与测试数据以及输入输出规范。

2、复旦大学机试设定测试时间为150分钟，要求提交源代码+解题思路+自测数据。

3、本人所提供的题解不一定为最佳题解或唯一解法，仅供参考。输入规范、输出规范、测试用例可由考生自己设定。若有谬误，欢迎指正。

4、本次机试题，在Leetcoder上均有原题。

第 1 题

方法：深度优先搜索（DFS）

思路：由测试数据可知此题为完全二叉树，不必建树。从根节点开始向下遍历，期间维护从根节点到当前节点 xxx 的最大值 premax[x]premax[x]premax[x]，若当前节点的值大于等于 premax[x]premax[x]premax[x]，标记当前节点为关键节点，即 vis[x]vis[x]vis[x] 标记为 111。从当前节点继续向下递归左孩子 2x2x2x 与 右孩子 2x+12x+12x+1，遇到值为 −1-1−1 时 returnreturnreturn。时间复杂度为 O(N)O(N)O(N)，空间复杂度为 O(N)O(N)O(N)， NNN 为节点总数。

输入规范：给出完全二叉树节点个数 N， 接下来按照层序遍历（BFS）顺序给出每个节点的值，其中 −1-1−1 表示空节点。

输出规范：输出关键节点个数

测试用例：

输入：7 3 1 4 3 -1 1 5

输出：4

状态：通过

输入：15 8 5 6 10 15 2 7 11 11 11 11 11 11 11 11

输出：9

状态：通过

#include<iostream>using namespace std;const int maxn = 1e5;int n;//节点个数int a[maxn];//二叉树元素int vis[maxn];//标记是否为关键节点int premax[maxn];//记录到当前节点路径上的最大值void work(int x) {// DFS实现,x为当前节点ID，premax表示为从根节点到当前节点的最大值if (a[x] == -1) return;if (a[x] >= premax[x/2]) {premax[x] = a[x]; vis[x] = 1;}else {premax[x] = premax[x / 2];}work(2 * x);work(2 * x + 1);}int main() {cin >> n;memset(a, -1, sizeof a);//初始每一个节点都为NULLfor (int i = 1; i <= n; i++) {cin >> a[i];//用-1表示NULL}memset(vis, 0, sizeof vis);work(1);int Ans = 0;for (int i = 1; i <= n; i++) {if (vis[i]) Ans++;}cout << Ans << endl;//关键节点个数return 0;}

第 2 题

方法：动态规划

思路：答案为斐波那契数列，当前台阶，可以由下一层台阶跳一级而来，也可以由下两层台阶跳二级而来，由此可得状态转移方程为 dp[i]=dp[i−1]+dp[i−2]dp[i] = dp[i-1] + dp[i-2]dp[i]=dp[i−1]+dp[i−2]；初始化 dp[1]dp[1]dp[1] 为 111,dp[2]dp[2]dp[2] 为 222。可逐步递推得到 dp[n]dp[n]dp[n]。时间复杂度为 O(N)O(N)O(N), 空间复杂度为 O(N)O(N)O(N), NNN 为台阶总数。

输入规范：输入总体台阶数 NNN。

输出规范：输出总方案数。

测试用例：

输入：3

输出：3

状态：通过

输入：10

输出：89

状态：通过

测试用例：

输入：14

输出：610

状态：通过

测试用例：

输入：30

输出：1346269

状态：通过

#include<iostream>using namespace std;#define LL long long int#define ll LLconst int maxn = 1e5;LL dp[maxn];int main() {int n;cin >> n;dp[1] = 1;dp[2] = 2;for (int i = 3; i <= n; i++) {dp[i] = dp[i - 1] + dp[i - 2];}cout << dp[n] << endl;return 0;}

第 3 题

方法 1：动态规划+滚动数组优化（适用于数据量较大，但数据值不高的数据）

思路：可以将本问题转化为背包问题。期望 E=正数和−负数和的绝对值E=正数和-负数和的绝对值E=正数和−负数和的绝对值，数据总和 sum=正数和+负数和的绝对值sum=正数和+负数和的绝对值sum=正数和+负数和的绝对值。联立方程组可得：正数和Tot=（E+sum）/2正数和 Tot=（E + sum）/ 2正数和Tot=（E+sum）/2 ；则原问题转换为，在序列中选择几个数，满足和为 TotTotTot，为经典背包问题。注意，E+sumE + sumE+sum 必须为偶数，否则无解。

dp[j]dp[j]dp[j]表示为装满容量为j的背包共有多少方案，则遍历到元素a[i]的时候，状态转移方程（由于当前状态只与上一层状态有关，所以可采用一维数组优化）为 dp[j]=dp[j]+dp[j−a[i]]dp[j] = dp[j] + dp[j - a[i]]dp[j]=dp[j]+dp[j−a[i]] ;当前容量为j的方案为原来容量为j的方案数+可以通过添加a[i]转移过来的方案数。最终输出 dp[Tot]dp[Tot]dp[Tot]，Tot为转换为背包问题后的期望值。时间复杂度为 O（N∗Tot）O（N*Tot）O（N∗Tot），空间复杂度为 O（N+Tot）O（N+Tot）O（N+Tot），NNN 为序列长度，TotTotTot 为正数和。

方法 2：暴力枚举（适用于数据量较小，但数据值较高的数据）

思路：通过深度优先搜索，每一个数都只有取正取负两种可能。时间复杂度为O(2^N)，空间复杂度为O(N)。

输入规范：给出序列长度N，输入N个非负整数，输入期望值E。结果对1e9+7取模（防止方案数太多超过数据范围）。

输出规范：输出总方案数。

测试用例：

输入：5 1 1 1 1 1 3

输出：5

状态：通过

输入：10 1 2 3 4 5 6 7 8 9 10 15

输出：31

状态：通过

输入：10 1 1 1 1 1 1 1 1 1 1 5

输出：0

状态：通过

输入：10 1 1 1 1 1 1 1 1 1 1 4

输出：120

状态：通过

输入：50 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 1 1 1 1 1 1 1 1 1 1 1 1 1 1 25

输出：0

状态：通过

输入：50 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 1 1 1 1 1 1 1 1 1 1 1 1 1 1 26

输出：399650253

状态：通过

动态规划+滚动数组

#include<iostream>#include<cstdio> using namespace std;#define LL long long int#define ll LLconst int maxn = 1e5;const int mod = 1e9 + 7;LL a[maxn];int n;//序列长度LL Ans;//总方案数LL E;//期望数void work() {int sum = 0;for (int i = 1; i <= n; i++) {sum += a[i];}LL Tot = (E + sum) / 2;// 正数和if ((E + sum) % 2 != 0) {// 无解puts("0"); return;}LL *dp = new LL[Tot + 1](); // 申请dp并初始化dp[]为0dp[0] = 1;for (int i = 1; i <= n; i++) {for (int j = Tot; j >= a[i]; j--) {dp[j] = dp[j] + dp[j - a[i]];dp[j] %= mod;//取模}}cout << dp[Tot] << endl;}int main() {cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i];}cin >> E;work();return 0;}

暴力枚举

#include<iostream>using namespace std;#define LL long long int#define ll LLconst int maxn = 1e5;const int mod = 1e9 + 7;LL a[maxn];LL n;//序列长度LL Ans;//总方案数LL E;//期望数void dfs(LL x, LL sum) {if (x == n) {//递归到最后一个元素，准备返回if(sum == E) Ans++; return;}dfs(x + 1, sum + a[x + 1]);dfs(x + 1, sum - a[x + 1]);}int main() {cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i];}cin >> E;dfs(0, 0);cout << Ans << endl;return 0;}