2020复旦夏令营机试题个人理解

2020复旦夏令营机试题个人理解

第一题

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

例子：

输入：

4，[1，0]，[2，0]，[3，1]，[3，2]

输出：

0，1，2，3或者0，2，1，3 

显然这是拓扑排序问题，这种有典型的思路：

1. 找到当前入度为0的结点输出
2. 它的直接后序节点入度减一
3. 直至节点全部输出

 代码实现：

#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> child(1000001);
int rudu[1000001];
int visit[1000001];
int main() {int n;scanf("%d",&n);int a,b;while(~scanf("[%d，%d]",&a,&b)){child[a].push_back(b);rudu[b]++;}int cnt=0,now;while(cnt<n){for(int i=0;i<n;i++){if(rudu[i]==0&&visit[i]==0){if(cnt==n-1){cout<<i;}else{cout<<i<<"，";}for(int j=0;j<child[i].size();j++){rudu[child[i][j]]--;}visit[i]=1;cnt++;}}}return 0;
}

一下子写了一个o(n^2)的算法出来，感觉还有改进空间：

#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> child(1000001);
int rudu[1000001];
queue<int>q;
int main() {int n;scanf("%d",&n);if(n==1)cout<<n-1;int a,b;while(scanf("[%d，%d]",&a,&b)){child[a].push_back(b);rudu[b]++;}for(int i=0;i<n;i++)if(rudu[i]==0)q.push(i);int cnt=0;while(!q.empty()){int now=q.front();q.pop();cnt++;if(cnt!=n)cout<<now<<"，";else cout<<now;for(int j=0;j<child[now].size();j++){rudu[child[now][j]]--;if(rudu[child[now][j]]==0){q.push(child[now][j]);}}}return 0;
}

用队列就好一些了o(n)爽！

第二题

给定一个二维矩阵，矩阵里的每个元素是0或者1，找出该矩阵中的最大正方子矩阵（即行数和列数相同），使得该正方子矩阵中的元素都是1，并输出该正方子矩阵的行数。

例子：

输入：

1 0 1 0 0

1 0 1 1 1

1 1 1 1 1

1 0 0 1 0

输出：

2

 一开始就想到暴力搜索，但是有预感会爆掉，仔细思考后使用动态规划（yyds）：

从左上角往右下角开始扫描计算，用一个二维数组表示每个元素位置包含的最大全1子矩阵阶数，显然第一行和第一列的最大子矩阵阶数等于数值本身。

递推关系为：

1. 当前元素如果是0则二维数组值为0
2. 如果为1，当前位置值取它上面元素和左边元素二维数组值最小值再加一。

 代码：

#include <bits/stdc++.h>
using namespace std;
int dp[10001][10001];
int matrix[10001][10001];
int data[10001];
int main() {int n=0,m;string tp;while(getline(cin,tp)){m=(tp.length()+1)/2;for(int i=0;i<tp.length();i+=2){matrix[n][i/2]=tp[i]-'0';}n++;}for(int i=0;i<n;i++){dp[0][i]=matrix[0][i];}for(int i=1;i<m;i++){dp[i][0]=matrix[i][0];}int max_n=1;for(int i=1;i<n;i++){for(int j=1;j<m;j++){if(matrix[i][j]){int now=min(dp[i-1][j],dp[i][j-1]);dp[i][j]=now+1;max_n=max(max_n,now+1);}}}cout<<max_n;return 0;
}

😓一开始数组开大了还报错惹，空间还是不能太任性奥

第三题

给定一棵有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

代码：

#include <bits/stdc++.h>
using namespace std;
map<int,int>mp;//初始值为0
int father[10001];
int dis[10001];
vector<int>black;
int dist(int a,int b){int l1=0,l2=0;int tp1=a,tp2=b;while(father[tp1]!=-1){l1++;tp1=father[tp1];}while(father[tp2]!=-1){l2++;tp2=father[tp2];}tp1=a,tp2=b;int ans=0;for(int i=0;i<l1-l2;i++){ans+=dis[tp1];tp1=father[tp1];}for(int i=0;i<l2-l1;i++){ans+=dis[tp2];tp2=father[tp2];}while(tp1!=tp2){ans+=dis[tp1];ans+=dis[tp2];tp1=father[tp1];tp2=father[tp2];}return ans;}
int main() {father[0]=-1;int n,m;cin>>n>>m;//0为根节点for(int i=1;i<n;i++){cin>>father[i];//方便找共同祖先}for(int i=1;i<n;i++){cin>>dis[i];//加权边}int op,node;while(m--){cin>>op>>node;if(op==1&&mp[node]!=1){//染色mp[node]=1;black.push_back(node);}else{if(black.size()==0)cout<<0<<endl;else{int sum=0;for(int i=0;i<black.size();i++){if(black[i]!=node){sum+=dist(node,black[i]);}cout<<sum<<endl;}}}}return 0;
}