第一题 【深基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
2
3
4
5

样例输出 #1

Excellent
Not excellent
Not excellent
Excellent
1
2
3
4

提示

数据保证，$1\le N\le 1000$，学号为不超过 $100000$ 的正整数，学业成绩和素质拓展成绩为 $0\sim 100$ 之间的正整数。

解题思路

• 1）用结构体储存学生信息。
• 2）按照题目条件判断是否优秀，进行输出。

参考代码

#include
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

第二题 5 倍经验日

题目背景

现在乐斗有活动了！每打一个人可以获得 5 倍经验！absi2011 却无奈的看着那一些比他等级高的好友，想着能否把他们干掉。干掉能拿不少经验的。

题目描述

现在 absi2011 拿出了 $x$ 个迷你装药物（嗑药打人可耻…），准备开始与那些人打了。

由于迷你装药物每个只能用一次，所以 absi2011 要谨慎的使用这些药。悲剧的是，用药量没达到最少打败该人所需的属性药药量，则打这个人必输。例如他用 $2$ 个药去打别人，别人却表明 $3$ 个药才能打过，那么相当于你输了并且这两个属性药浪费了。

现在有 $n$ 个好友，给定失败时可获得的经验、胜利时可获得的经验，打败他至少需要的药量。

要求求出最大经验 $s$，输出 $5s$。

输入格式

第一行两个数，$n$ 和 $x$。

后面 $n$ 行每行三个数，分别表示失败时获得的经验 ${lose}_i$，胜利时获得的经验 ${win}_i$ 和打过要至少使用的药数量 ${use}_i$。

输出格式

一个整数，最多获得的经验的五倍。

样例 #1

样例输入 #1

6 8
21 52 1
21 70 5
21 48 2
14 38 3
14 36 1
14 36 2
1
2
3
4
5
6
7

样例输出 #1

1060
1

提示

【Hint】

五倍经验活动的时候，absi2011 总是吃体力药水而不是这种属性药。

【数据范围】

• 对于 $10\%$ 的数据，保证 $x=0$。
• 对于 $30\%$ 的数据，保证 $0\le n\le 10$，$0\le x\le 20$。
• 对于 $60\%$ 的数据，保证 $0\le n,x\le 100$， $10<los{e}_i,wi{n}_i\le 100$，$0\le us{e}_i\le 5$。
• 对于 $100\%$ 的数据，保证 $0\le n,x\le 10^3$，$0<los{e}_i\le wi{n}_i\le 10^6$，$0\le us{e}_i\le 10^3$。

解题思路

• 1）变形的01背包问题。
• 2）分两种情况，第一种是能打过，可以选择打或不打，第二种是打不过。

参考代码

#include
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

第三题 最大约数和

题目描述

选取和不超过S的若干个不同的正整数，使得所有数的约数（不含它本身）之和最大。

输入格式

输入一个正整数S。

输出格式

输出最大的约数之和。

样例 #1

样例输入 #1

11
1

样例输出 #1

9
1

提示

样例说明

取数字4和6，可以得到最大值(1+2)+(1+2+3)=9。

数据规模

S<=1000
1

解题思路

• 1）看起来像数学题，其实还是背包问题。
• 2）先进行预处理，求每个数最大公约数的和。
• 3）01背包解决问题。

参考代码

#include
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；
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

第四题 【深基16.例3】二叉树深度

题目描述

有一个 $n(n\le 10^6)$ 个结点的二叉树。给出每个结点的两个子结点编号（均不超过 $n$），建立一棵二叉树（根节点的编号为 $1$），如果是叶子结点，则输入 0 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
2
3
4
5
6
7
8

样例输出 #1

4
1

解题思路

• 1）建立二叉树结点，输入结点信息。
• 2）深度优先搜索遍历出二叉树深度。

参考代码

#include
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21