【2021复旦机考】三题

2021年真题
第一题
题目描述：给定一颗二叉树，树的每个节点的值为一个正整数。如果从根节点到节点 N 的路径上不存在比节点 N 的值大的节点，那么节点 N 被认为是树上的关键节点。求树上所有的关键节点的个数。请写出程序，并解释解题思路。
例子：

输入： 3, 1, 4, 3, null, 1, 5
输出：4（图中蓝色节点是关键节点）

#include
#include
using namespace std;
int main(){
	
	
	vector tree;
	int temp=0;
	while(1){
		cin >> temp;
		if(temp==-1) break;
		tree.push_back(temp);			
	}
	 
	//计数
	int count = 0; 
	for(int i = tree.size()-1; i >= 0; i--){
		//判断根节点是否大于该节点 
		if(tree[0] > tree[i] || tree[i] == 0) continue;
		
		//不断取祖先节点 
		int j=i/2;
		bool judge = true;
		while(j != 0){
			//不是关键节点	
			if(tree[j] > tree[i]){
				judge=false;
				break;  
			}
			j /= 2;
		}
		//是就计数加1 
		if(judge = true) count++;
		
	}	
	cout <<  count; 
}

第二题

题目描述：训练场上有一个台阶，总共有 n 级。一个运动员可以跳 1 级，也可以跳 2 级。求运动员有多少种跳法。请写出程序，并解释解题思路。

#include 
 using namespace std;
 int main(){
 	
 	
 	
 	
 	int n;
 	cin >> n;
 	int dp[n+1];
 	dp[0]=1;
 	dp[1]=1;
 	for(int i = 2; i <= n; i++){
 		dp[i]=dp[i-1]+dp[i-2];	
	}
 	cout << dp[n];
 	
 	
 	
 }

第三题
题目描述：给定一个非负整数序列x1,x2,x3...xn，可以给每一个整数取负数或者取原值，求有多少种取法使得这些整数的和等于期望值E。请写出程序，并解释解题思路。

输入：1, 1, 1, 1, 1, 3
输出：5

样例解释:

-1+1+1+1+1 = 3
1-1+1+1+1 = 3
1+1-1+1+1 = 3
1+1+1-1+1 = 3
1+1+1+1-1 = 3

#include
#include
#include
#include
using namespace std;
int main(){
	cout<<"输入序列（-1为结束符）："< nums;
	while(1){
		int temp;
		cin >> temp;
		if(temp == -1) break;
		nums.push_back(temp);	
	}       
	int sum = accumulate(nums.begin(),nums.end(),0);
	
	cout << "请输入期望值E："<> E;
	
	
	
	//初始化 
	vector> dp(nums.size()+1);
	for(int i = 0; i <= nums.size(); i++ ){
		for(int v = -sum; v <= sum; v++){
			if(i == 0 && v == 0){
				dp[i][v] = 1;
			}
			else{
				dp[i][v] = 0;
			}
		}
	}
	//状态转移 填表	
	for(int i = 1; i <= nums.size(); i++){
		
		for(int v = -sum; v <= sum; v++){
			//temp1  和 temp2分别为两种方法数 curdata为此时的第i个数 
			int temp1 = 0, temp2 = 0, curdata = nums[i-1];
			
			//判断 v - curdata 是否是在-sum ~ sum 内的 ，由于curdata是大于0的，因此v-curdata只可能小于-sum, v+curdata 同理 
			if(-sum <= v - curdata)	temp1 = dp[i-1][v - curdata];
			if(sum >= v + curdata) temp2 = dp[i-1][v + curdata];
			
			
			//两种方法数和为dp[i][v]结果	
			dp[i][v] = temp1 + temp2;
		}		
	}
	
	//得到最后结果 
	cout << dp[nums.size()][E];
	
	
	
	
}

【2021复旦机考】三题

C/C++/C#相关栏目本月热门文章