第一题 【深基7.例11】评等级
题目描述
现有 N 名同学，每名同学需要设计一个结构体记录以下信息：学号、学业成绩和素质拓展成绩、综合分数（实数）。每行读入同学的姓名、学业成绩和素质拓展成绩，并且计算综合分数（分别按照 70 %和 30 % 权重累加），存入结构体中。还需要在结构体中定义一个成员函数，返回该结构体对象的学业成绩和素质拓展成绩的总分。
然后需要设计一个函数，其参数是一个学生结构体对象，判断该学生是否“优秀”。优秀的定义是学业和素质拓展成绩总分大于 140 分，且综合分数不小于 80 分。
当然通过本题很容易啦，本题只是为了帮助你训练结构体的使用方法。
输入格式
第一行一个整数 N 。
接下来 N 行，每行 3 个整数，依次代表学号、学业成绩和素质拓展成绩。
输出格式
N行，如果第 i名学生是优秀的，输出 Excellent，否则输出 Not excellent。
样例 #1
样例输入 #1
4 1223 95 59 1224 50 7 1473 32 45 1556 86 99
样例输出 #1
Excellent Not excellent Not excellent Excellent
提示
数据保证，1 ≤ N ≤ 1000，学号为不超过 100000的正整数，学业成绩和素质拓展成绩为 0 ∼ 100之间的正整数。
解题思路
1）用结构体储存学生信息。
2）按照题目条件判断是否优秀，进行输出。
参考代码
#include<bits/stdc++.h> using namespace std; struct node{ int id; double sc1, sc2; int score; double final_score; }a[1000]; int main() { int n; cin >> n; for(int i=0; i<n; i++) { cin>>a[i].id>>a[i].sc1>>a[i].sc2; a[i].score=a[i].sc1+a[i].sc2; a[i].final_score=a[i].sc1*0.7+a[i].sc2*0.3; } for(int i=0; i<n; i++) { if(a[i].score>140&&a[i].final_score>=80) { cout <<"Excellent"<<endl; } else { cout<<"Not excellent"<<endl; } } return 0; }
第二题 5 倍经验日
题目背景
现在乐斗有活动了！每打一个人可以获得 5 倍经验！absi2011 却无奈的看着那一些比他等级高的好友，想着能否把他们干掉。干掉能拿不少经验的。
题目描述
现在 absi2011 拿出了 x个迷你装药物（嗑药打人可耻…），准备开始与那些人打了。
由于迷你装药物每个只能用一次，所以 absi2011 要谨慎的使用这些药。悲剧的是，用药量没达到最少打败该人所需的属性药药量，则打这个人必输。例如他用 2 个药去打别人，别人却表明 3 个药才能打过，那么相当于你输了并且这两个属性药浪费了。
现在有 n 个好友，给定失败时可获得的经验、胜利时可获得的经验，打败他至少需要的药量。
要求求出最大经验 s ，输出 5 s。
输入格式
第一行两个数，n 和 x。
后面 n行每行三个数，分别表示失败时获得的经验 l o s e，胜利时获得的经验wini和打过要至少使用的药数量 u s e i。
输出格式
一个整数，最多获得的经验的五倍。
样例 #1
样例输入 #1
6 8 21 52 1 21 70 5 21 48 2 14 38 3 14 36 1 14 36 2
样例输出 #1
1060
提示
【Hint】
五倍经验活动的时候，absi2011 总是吃体力药水而不是这种属性药。
【数据范围】
解题思路
1）变形的01背包问题。
2）分两种情况，第一种是能打过，可以选择打或不打，第二种是打不过。
参考代码
#include<bits/stdc++.h> using namespace std; long long dp[105000]; int main() { int n,x; cin>>n>>x; for(int i=1;i<=n;i++) { int lose,win,use; cin>>lose>>win>>use; for(int j=x;j>=use;j--) { dp[j]=max(dp[j]+lose,dp[j-use]+win); } for(int j=use-1;j>=0;j--) { dp[j]+=lose; } } cout<<dp[x]*5; return 0; }
第三题 最大约数和
题目描述
选取和不超过S的若干个不同的正整数，使得所有数的约数（不含它本身）之和最大。
输入格式
输入一个正整数S。
输出格式
输出最大的约数之和。
样例 #1
样例输入 #1
11
样例输出 #1
9
提示
样例说明
取数字4和6，可以得到最大值(1+2)+(1+2+3)=9。
数据规模
S<=1000
解题思路
1）看起来像数学题，其实还是背包问题。
2）先进行预处理，求每个数最大公约数的和。
3）01背包解决问题。
参考代码
#include<bits/stdc++.h> using namespace std; int i,j,n,a[1001],dp[1001]; int main() { cin>>n; for(i=1;i<=n/2;i++) for(j=2;i*j<=n;j++) a[i*j]+=i; for(i=1;i<=n;i++) for(j=i;j<=n;j++) dp[j]=max(dp[j],dp[j-i]+a[i]); cout<<dp[n]; return 0； }
第四题 【深基16.例3】二叉树深度
题目描述
有一个 n ( n ≤ 
) 个结点的二叉树。给出每个结点的两个子结点编号（均不超过 n），建立一棵二叉树（根节点的编号为 1），如果是叶子结点，则输入 0 。
建好树这棵二叉树之后，请求出它的深度。二叉树的深度是指从根节点到叶子结点时，最多经过了几层。
输入格式
第一行一个整数 n ，表示结点数。
之后 n行，第 i 行两个整数 l、r ，分别表示结点 i的左右子结点编号。若 l = 0 则表示无左子结点，r = 0 同理。
输出格式
一个整数，表示最大结点深度。
样例 #1
样例输入 #1
7 2 7 3 6 4 5 0 0 0 0 0 0 0 0
样例输出 #1
4
解题思路
1）建立二叉树结点，输入结点信息。
2）深度优先搜索遍历出二叉树深度。
参考代码
#include<bits/stdc++.h> using namespace std; struct node{ int l,r; }a[1001000]; int Max=-1,n; void dfs(int root,int step){ if(root==0) return; Max=max(Max,step); dfs(a[root].l,step+1); dfs(a[root].r,step+1); } int main(){ cin>>n; for(int i=1;i<=n;i++){ cin>>a[i].l>>a[i].r; } dfs(1,1); cout<<Max; return 0; }
