第一题 【深基7.例9】最厉害的学生
题目描述
现有 N名同学参加了期末考试，并且获得了每名同学的信息：姓名（不超过 8个字符的仅有英文小写字母的字符串）、语文、数学、英语成绩（均为不超过 150 的自然数）。总分最高的学生就是最厉害的，请输出最厉害的学生各项信息（姓名、各科成绩）。如果有多个总分相同的学生，输出靠前的那位。
输入格式
第一行输入一个正整数 N，表示学生个数。
第二行开始，往下 N 行，对于每一行首先先输入一个字符串表示学生姓名，再输入三个自然数表示语文、数学、英语的成绩。均用空格相隔。
输出格式
输出最厉害的学生。
样例 #1
样例输入 #1
3 senpai 114 51 4 lxl 114 10 23 fafa 51 42 60
样例输出 #1
senpai 114 51 4
提示
数据保证，1 ≤ N ≤ 1000，姓名为长度不超过 8 88 的字符串，语文、数学、英语成绩均为不超过 150 的自然数。
解题思路
1）记录每个人的姓名和成绩。
2）依次遍历，和最大成绩比较，若大于最大成绩，则替换最大成绩。
3）若相等或小于最大成绩不用操作。
4）输出答案。
参考代码
#include<bits/stdc++.h> using namespace std; string name[1005]; int cg[1005],mg[1005],eg[1005]; int main(){ int n,max=-999999,ans; scanf("%d",&n); for(int a=0;a<n;a++) cin>>name[a]>>cg[a]>>mg[a]>>eg[a]; for(int b=0;b<n;b++) { if(cg[b]+mg[b]+eg[b]>max) { max=cg[b]+mg[b]+eg[b]; ans=b; } } cout<<name[ans]<<" "<<cg[ans]<<" "<<mg[ans]<<" "<<eg[ans]; return 0; }
第二题 [NOIP2006 普及组] 开心的金明
题目描述
金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数1 − 5表示，第5 等最重要。他还从因特网上查到了每件物品的价格（都是整数元）。他希望在不超过N元（可以等于N 元）的前提下，使每件物品的价格与重要度的乘积的总和最大。
请你帮助金明设计一个满足要求的购物单。
输入格式
第一行，为2个正整数，用一个空格隔开：n , m（其中N ( < 30000 ) 表示总钱数，m ( < 25 ) 为希望购买物品的个数。）
从第2行到第m + 1行，第j行给出了编号为j − 1 的物品的基本数据，每行有2 个非负整数$ v p（其中v表示该物品的价格 表示该物品的价格表示该物品的价格(v \le 10000)，p$表示该物品的重要度(1 − 5)
输出格式
1个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值( < 100000000 ) 。
样例 #1
样例输入 #1
1000 5 800 2 400 5 300 5 400 3 200 2
样例输出 #1
3900
解题思路
1）简单的01背包问题，直接背板子。
参考代码
#include<bits/stdc++.h> using namespace std; int dp[105000]; int main() { int n,m; cin>>n>>m; for(int i=1;i<=m;i++) { int v,p; cin>>v>>p; for(int j=n;j>=v;j--) { dp[j]=max(dp[j],dp[j-v]+v*p); } } cout<<dp[n]; return 0; }
第三题 组合的输出
题目描述
排列与组合是常用的数学方法，其中组合就是从 n个元素中抽出 r 个元素（不分顺序且 r ≤ n ），我们可以简单地将 n个元素理解为自然数 1 , 2 , … , n ，从中任取 r个数。
现要求你输出所有组合。
例如 n = 5 , r = 3 ，所有组合为：
123 , 124 , 125 , 134 , 135 , 145 , 234 , 235 , 245 , 345 。
输入格式
一行两个自然数 n , r ( 1 < n < 21 , 0 ≤ r ≤ n ) 。
输出格式
所有的组合，每一个组合占一行且其中的元素按由小到大的顺序排列，每个元素占三个字符的位置，所有的组合也按字典顺序。
注意哦！输出时，每个数字需要 3 33 个场宽。以 C++ 为例，你可以使用下列代码：
cout << setw(3) << x;
输出占 3 33 个场宽的数 x xx。注意你需要头文件 iomanip。
样例 #1
样例输入 #1
5 3
样例输出 #1
1 2 3 1 2 4 1 2 5 1 3 4 1 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5
解题思路
1）深度优先搜索题目。
2）每个数字只能出现一次，我们从小到大搜索。
3）如果该数字没有被使用，我们将该数字填入答案，标记为使用过，然后调用下一层。
4）当步数为题目要求，输出然后回溯。
参考代码
#include<bits/stdc++.h> using namespace std; int used[100]; int n,r; int a[200]; void dfs(int num,int step) { if(step==r) { for(int i=0;i<r;i++) { cout<<setw(3)<<a[i]; } cout<<endl; return; } for(int i=num;i<=n;i++) { if(!used[i]) { used[i]=1; a[step]=i; dfs(i+1,step+1); used[i]=0; } } } int main() { cin>>n>>r; dfs(1,0); return 0; }
第四题 【深基18.例3】查找文献
题目描述
小K 喜欢翻看洛谷博客获取知识。每篇文章可能会有若干个（也有可能没有）参考文献的链接指向别的博客文章。小K 求知欲旺盛，如果他看了某篇文章，那么他一定会去看这篇文章的参考文献（如果他之前已经看过这篇参考文献的话就不用再看它了）。
假设洛谷博客里面一共有 n ( n ≤ 
) 篇文章（编号为 1 到 n）以及 m ( m ≤ 
) 条参考文献引用关系。目前小 K 已经打开了编号为 1 的一篇文章，请帮助小 K 设计一种方法，使小 K 可以不重复、不遗漏的看完所有他能看到的文章。
这边是已经整理好的参考文献关系图，其中，文献 X → Y 表示文章 X 有参考文献 Y。不保证编号为 1 的文章没有被其他文章引用。
请对这个图分别进行 DFS 和 BFS，并输出遍历结果。如果有很多篇文章可以参阅，请先看编号较小的那篇(因此你可能需要先排序)。
输入格式
共 m + 1 行，第 1 行为 2 个数，n和 m，分别表示一共有 n ( n ≤ 
) 篇文章（编号为 1 到 n）以及m ( m ≤ 
)条参考文献引用关系。
接下来 m 行，每行有两个整数 X , Y 表示文章 X 有参考文献 Y。
输出格式
共 2 行。
第一行为 DFS 遍历结果，第二行为 BFS 遍历结果。
样例 #1
样例输入 #1
8 9 1 2 1 3 1 4 2 5 2 6 3 7 4 7 4 8 7 8
样例输出 #1
1 2 5 6 3 7 8 4 1 2 3 4 5 6 7 8
解题思路
1）非常基础的图论的题目。
2）可以看看这篇文章
参考代码
#include<bits/stdc++.h> using namespace std; int n,m; bool flag[100005]; vector<int > a[100005]; void dfs(int x,int r) { flag[x]=true; if(!r) { cout<<x<<' '; return ; } cout<<x<<' '; for(int i=0;i<a[x].size();i++) if(!flag[a[x][i]]) dfs(a[x][i],r-1); } void bfs() { queue<int> q; q.push(1);flag[1]=true; while(!q.empty()) { int s=q.front(); q.pop(); cout<<s<<' '; for(int i=0;i<a[s].size();i++) if(flag[a[s][i]]==false) { q.push(a[s][i]); flag[a[s][i]]=true; } } } int main() { cin>>n>>m; for(int i=1;i<=m;i++) { int x,y; cin>>x>>y; a[x].push_back(y); } for(int i=1;i<=n;i++) sort(a[i].begin(),a[i].end()); dfs(1,n); cout<<endl; for(int i=1;i<=n;i++) flag[i]=false; bfs(); return 0; }
