2020计算机专业保研夏令营面经：复旦计算机（含机考题目详细题解）

整体安排机考

第1题

题目题解测试用例代码 第2题

题目题解测试用例代码 第3题

题目题解测试用例代码 英语口试专业面试

7.13号各个实验室通过腾讯会议介绍，晚上登陆系统填写志愿。7.14号上午机考，下午英语口试，7.15号专业面试。

（头铁，报了人工智能方向学硕…

要求如下：

编程能力摸底测试完成后，请按照以下要求进行打包提交：
1）提供名为“解题思路与测试情况”的PDF文件，按顺序针对每道题解释解题思路，并列举已经使用并通过的测试用例；
2）提供每道题的完整源代码文件，文件名为题目号，如“第1题”、“第2题”；
3）以上文件一起压缩打包，压缩包命名为“报名号”+空格+“姓名”。

某学校的计算机系一共有n门专业课程，依次被标记为0、1、……、n-1。某些课程只能在前置课程修读完之后才能进行修读，例如课程0的前置课程为课程1，表示为[0，1]。给定专业课程数量以及专业课程之间的前置关系，输出课程的正确修读顺序从而满足课程之间的前置关系。
例子：
输入：
4，[1，0]，[2，0]，[3，1]，[3，2]（其中4为课程数量，[1，0]，[2，0]，[3，1]，[3，2]为课程之间的前置关系）
输出：
0，1，2，3或者0，2，1，3

典型的DAG拓扑排序。查找没有前驱的顶点输出就行，直至将所有结点输出。
这里我用了set数组记录每个节点的前驱节点，而不是像邻接表一样记录后继节点。
这样每次判断结点对应的set长度是不是0，就知道其有没有前驱节点了。
每找到一个节点，将该节点从其他所有节点的set中删除。
注意输入格式为[a,b]，需要把无关的符号处理一下。
这道题是special judge，选择一个正确答案输出。

注：这道题目PDF中给的输入用例是中文符号，导致一直报错，调试了很久才发现。
警醒！警醒！

测试用例1：
输入：4,[1,0],[2,0],[3,1],[3,2]
输出：0,1,2,3
测试结果：通过

测试用例2：
输入：5,[1,0],[2,1],[3,1],[1,4]
输出：0,4,1,2,3
测试结果：通过

测试用例3：
输入：5,[1,0],[2,1],[3,1],[1,4],[0,4]
输出：4,0,1,2,3
测试结果：通过

测试用例4：
输入：3,[2,1]
输出：0,1,2
测试结果：通过

#include 
#include 
using namespace std;
int main() {
	int n;
	cin>>n;
	set s[n];
	bool mark[n];
	for(int i=0; i>temp;
	while(temp!='n') {
		cin>>temp>>hou>>temp>>qian>>temp;
		s[hou].insert(qian);
		temp=cin.get();
	}
	int count=0;
	while(count 
第2题 
题目 
给定一个2维矩阵，矩阵里的每个元素是0或者1，找出该矩阵中的最大正方子矩阵（即行数和列数相同），使得该正方子矩阵中的元素都是1，并输出该正方子矩阵的行数。
 例子：
 输入：
 1 0 1 0 0
 1 0 1 1 1
 1 1 1 1 1
 1 0 0 1 0
 输出：
 2
 
题解 
寻找最大正方形子矩阵，当然可以暴力搜索。
 但是考虑动规，那么子问题就是dp[i][j]代表以(i,j)为右下角顶点的最大正方形长度。
 递推式：
 如果num[i][j]==0，那么dp[i][j]=0
 如果num[i][j]==1，那么dp[i][j]当新引入的对应长度的同一行和同一列均为1时为dp[i-1][j-1]+1，否则为1，该条件可以转换为dp[i][j]=min(dp[i-1][j],dp[i][j-1], dp[i-1][j-1])+1。这样转换可以避开复杂的循环判断。
 
注意：由于题目输入没有指定矩阵的行数与列数，因此用while(cin>>xx)，并假设矩阵大小不超过100 x 100。如果手工输入测试用例，那么需要键入Ctrl+Z，即EOF结束，若为OJ测试，请忽略。
 
测试用例 
测试用例1：
 输入：
 1 1 0 0 0
 1 0 1 1 1
 1 0 1 1 1
 0 0 1 1 1
 1 1 0 0 0
 输出：3
 测试结果：通过
 
测试用例2：
 输入：
 0
 输出：0
 测试结果：通过
 
测试用例3：
 输入：
 1
 输出：
 1
 测试结果：通过
 
测试用例4：
 输入：
 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
 输出：5
 测试结果：通过
 
测试用例5：
 输入：
 0 0 0 0 0
 0 0 0 0 0
 0 0 0 0 0
 0 0 0 0 0
 0 0 0 0 0
 输出：0
 测试结果：通过
 
测试用例6：
 输入：
 1 0 0 0 0 1 1 0 0 0 1
 0 1 1 1 0 0 0 0 1 1 1
 输出：1
 测试结果：通过
 
测试用例7：
 输入：
 1 1 0 0 1 1 0 1 1 1
 0 1 1 1 1 1 1 1 1 1
 0 1 1 1 0 0 0 1 1 0
 0 0 1 1 1 1 1 1 1 1
 输出：2
 测试结果：通过
 
代码 
#include 
#include 
using namespace std;

int main() {
	int num[100][100];
	int dp[100][100];
	
	int i=0,j=0;
	int temp;
	char t='x';
	int m=0,n=0,rs=0;
	while(cin>>temp) {
		num[i][j]=temp;
		t=cin.get();
		if(t==' ') {
			j++;
		} else {
			n=j+1;
			i++;
			j=0;
		}
	}
	if(j==0) {
		m=i;
	} else {
		m=i+1;
	}
	
	for(i=0; i0&&j>0)
					dp[i][j]=min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
				else
					dp[i][j]=1;
				rs=max(rs,dp[i][j]);
			} else {
				dp[i][j]=0;
			}
		}
	}

	cout< 
第3题 
题目 
给定一棵有n个节点的树，依次被标记为0、1、……、n-1，其中节点0是根节点。每个节点可以染上黑色或者白色，初始时所有节点都是白色。对任意节点c可以进行如下两个操作：染色操作，即将节点c染为黑色；查询操作，即输出节点c到所有黑色节点的距离之和。给定m个操作，需要对所有的查询操作进行相应的输出。该程序的输入具体包括：第一行包含整数n和m；第二行包含n-1个整数，第i个整数代表节点i的父节点；第三行包含n-1个整数，第i个整数代表节点i到父节点的边的长度；其余的m行每行包含两个整数t和c，t=1表示染色操作，t=2表示查询操作，c代表节点c，即在节点c上进行操作t。
 
例子：
 输入：
 4 5
 0 1 2
 2 1 3
 2 2
 1 3
 2 2
 2 3
 2 1
 输出：
 0
 3
 0
 4
 
题解 
这道题目读完之后，感觉关键在于数据结构（怎样表示每个节点的父节点关系和每条边的长度），以及怎样寻找到其他所有节点的最短距离。因为树的形状是固定的，变化的只是每个结点的颜色，所以可以预处理结点之间的距离，用二维数组存储起来，以后每次用到的时候直接查询数组。
 
怎样存储树呢？这道题目其实并不关心树的结构，只关心结点与结点之间的最短距离，所以直接将树与最短距离存储到一个二维矩阵中。分析到这里，基本上就是Floyd算法了。因为需要计算所有结点之间的最短距离，所以用该算法是合适的。使用一个标记数组记录每个结点的染色情况，对于每次查询操作，只要将查询节点与所有已染色结点的距离相加即可。
 
测试用例 
测试用例1：
 输入：
 4 5
 0 1 2
 2 1 3
 2 2
 1 3
 2 2
 2 3
 2 1
 输出：
 0
 3
 0
 4
 测试结果：通过
 
测试用例2：
 输入：
 7 6
 0 1 2 0 4 4
 1 5 4 3 2 1
 1 2
 2 1
 1 4
 2 3
 1 0
 2 5
 输出：
 5
 17
 18
 测试结果：通过
 
测试用例3：
 输入：
 5 6
 0 0 1 3
 1 1 1 1
 1 0
 2 4
 1 1
 2 4
 2 3
 2 2
 输出：
 3
 5
 3
 3
 测试结果：通过
 
测试用例4：
 输入：
 3 4
 0 0
 1 3
 1 1
 2 1
 2 2
 2 0
 输出：
 0
 4
 1
 测试结果：通过
 
代码 
#include 
#include 
#include 
using namespace std;
int main() {
	int n,m;
	cin>>n>>m;
	int G[n][n];
	bool mark[n];
	for(int i=0; i v;
	for(int i=0; i>temp;
		v.push_back(temp);
	}
	for(int i=0; i>temp;
		G[i+1][v[i]]=temp;
		G[v[i]][i+1]=temp;
	}
	for(int k=0; kG[i][k]+G[k][j])
					G[i][j]=G[i][k]+G[k][j];
	vector rs;
	for(int i=0; i>order>>a;
		if(order==1) {
			mark[a]=true;
		} else {
			int sum=0;
			for(int j=0; j 
英语口试 
introduce yourselflatest projectintroduce your hometown 
专业面试 
2分钟自我介绍最小生成树可以加边或者加点，那么最大生成树应该怎样求？Krusal算法是贪心算法，正确性怎样证明？你机考题目都做出来了吗，描述一下机考题目的解题思路描述一下你的项目你项目里的的“智能”体现在哪个方面？引申到了让我设计学生录取算法，根据学习成绩与获奖 
  
我说确定每个指标的权重，老师说不是我说放到二维坐标里面去，用桶，或者用堆，老师没表态