【团体程序设计天梯赛 往年关键真题 详细分析&完整AC代码】搞懂了赛场上拿下就稳
【团体程序设计天梯赛 往年关键真题 25分题合集 详细分析&完整AC代码】（L2-001 - L2-024）搞懂了赛场上拿下就稳了
【团体程序设计天梯赛 往年关键真题 25分题合集 详细分析&完整AC代码】（L2-025 - L2-048）搞懂了赛场上拿下这些分就稳了
L2-026 小字辈 递归
本题给定一个庞大家族的家谱，要请你给出最小一辈的名单。
输入格式：
输入在第一行给出家族人口总数 N（不超过 100 000 的正整数） —— 简单起见，我们把家族成员从 1 到 N 编号。随后第二行给出 N 个编号，其中第 i 个编号对应第 i 位成员的父/母。家谱中辈分最高的老祖宗对应的父/母编号为 -1。一行中的数字间以空格分隔。
输出格式：
首先输出最小的辈分（老祖宗的辈分为 1，以下逐级递增）。然后在第二行按递增顺序输出辈分最小的成员的编号。编号间以一个空格分隔，行首尾不得有多余空格。
输入样例：
9
2 6 5 5 -1 5 6 4 7
输出样例：
4
1 9
分析：
先计算出所有人辈分（本文利用递归），再找到所有最小辈分的人
代码：
#include<bits/stdc++.h>
using namespace std;
#define PII pair<int,int>
const int INF = 0x3f3f3f3f;
const int N = 1e5+10;
int fa[N],bf[N];
int fun(int x){ //递归计算辈分
if ( bf[x] ) return bf[x]; //避免重复计算
if ( x == -1 ) return 0;
return bf[x] = 1+fun(fa[x]);
}
int main(){
int n; scanf("%d", &n);
for ( int i = 1 ; i <= n ; i ++ ){
int x; scanf("%d",&x);
fa[i] = x;
}
for ( int i = 1 ; i <= n ; i ++ ) //计算成员辈分
fun(i);
int ans = 0;
for ( int i = 1 ; i <= n ; i ++ ) //寻找最小辈分
ans = max(ans, bf[i]);
printf("%d\n", ans);
vector<int> v;
for ( int i = 1 ; i <= n ; i ++ ) //存答案
if ( bf[i] == ans ) v.push_back(i);
for ( int i = 0 ; i < v.size() ; i ++ )
printf("%d%c", v[i] , i == v.size()-1 ? '\n' : ' ');
return 0;
}
L2-027 名人堂与代金券 排序
对于在中国大学MOOC（http://www.icourse163.org/ ）学习“数据结构”课程的学生，想要获得一张合格证书，总评成绩必须达到 60 分及以上，并且有另加福利：总评分在 [G, 100] 区间内者，可以得到 50 元 PAT 代金券；在 [60, G) 区间内者，可以得到 20 元PAT代金券。全国考点通用，一年有效。同时任课老师还会把总评成绩前 K 名的学生列入课程“名人堂”。本题就请你编写程序，帮助老师列出名人堂的学生，并统计一共发出了面值多少元的 PAT 代金券。
输入格式：
输入在第一行给出 3 个整数，分别是 N（不超过 10 000 的正整数，为学生总数）、G（在(60,100) 区间内的整数，为题面中描述的代金券等级分界线）、K（不超过 100且不超过 N 的正整数，为进入名人堂的最低名次）。接下来 N 行，每行给出一位学生的账号（长度不超过15位、不带空格的字符串）和总评成绩（区间 [0, 100] 内的整数），其间以空格分隔。题目保证没有重复的账号。
输出格式：
首先在一行中输出发出的 PAT 代金券的总面值。然后按总评成绩非升序输出进入名人堂的学生的名次、账号和成绩，其间以 1 个空格分隔。需要注意的是：成绩相同的学生享有并列的排名，排名并列时，按账号的字母序升序输出。
输入样例：
10 80 5
cy@zju.edu.cn 78
cy@pat-edu.com 87
1001@qq.com 65
uh-oh@163.com 96
test@126.com 39
anyone@qq.com 87
zoe@mit.edu 80
jack@ucla.edu 88
bob@cmu.edu 80
ken@163.com 70
输出样例：
360
1 uh-oh@163.com 96
2 jack@ucla.edu 88
3 anyone@qq.com 87
3 cy@pat-edu.com 87
5 bob@cmu.edu 80
5 zoe@mit.edu 80
分析：
水题，直接结构体存数据再排序就好，注意排名可以并列即可
代码：
因为用的数据结构不同，所以代码有所不同，区别在于重载处比较的写法
string存邮箱
#include<bits/stdc++.h>
using namespace std;
#define PII pair<int,int>
const int INF = 0x3f3f3f3f;
const int N = 1e4+10;
struct node{
string name;
int num;
const bool operator<(const node &t) {
if (num == t.num) return name < t.name;
return num > t.num;
}
}stu[N];
int main(){
int n, g, k;
scanf("%d%d%d", &n, &g, &k);
int sum = 0;
for ( int i = 1 ; i <= n ; i ++ ){
cin >> stu[i].name >> stu[i].num;
if ( stu[i].num >= g) sum += 50;
else if ( stu[i].num >= 60 ) sum += 20;
}
printf("%d\n",sum);
sort(stu+1,stu+n+1);
int cnt = 1;
for ( int i = 1 ; i <= n ; i ++ ){
if ( stu[i].num < stu[i-1].num ) cnt=i;
if ( cnt > k ) break;
cout << cnt << " " << stu[i].name << " " << stu[i].num << endl;
}
return 0;
}
char存邮箱
#include<bits/stdc++.h>
using namespace std;
#define PII pair<int,int>
const int INF = 0x3f3f3f3f;
const int N = 1e4+10;
struct node{
char name[20];
int num;
const bool operator<(const node &t) {
if (num == t.num) return strcmp(name,t.name)<0;
return num > t.num;
}
}stu[N];
int main(){
int n, g, k;
scanf("%d%d%d", &n, &g, &k);
int sum = 0;
for ( int i = 1 ; i <= n ; i ++ ){
scanf("%s %d", stu[i].name, &stu[i].num);
if ( stu[i].num >= g) sum += 50;
else if ( stu[i].num >= 60 ) sum += 20;
}
printf("%d\n",sum);
sort(stu+1,stu+n+1);
int cnt = 1;
for ( int i = 1 ; i <= n ; i ++ ){
if ( stu[i].num < stu[i-1].num ) cnt=i;
if ( cnt > k ) break;
printf("%d %s %d\n", cnt, stu[i].name, stu[i].num);
}
return 0;
}
