【团体程序设计天梯赛 往年关键真题 详细分析&完整AC代码】搞懂了赛场上拿下就稳
【团体程序设计天梯赛 往年关键真题 25分题合集 详细分析&完整AC代码】（L2-001 - L2-024）搞懂了赛场上拿下就稳了
【团体程序设计天梯赛 往年关键真题 25分题合集 详细分析&完整AC代码】（L2-025 - L2-048）搞懂了赛场上拿下这些分就稳了
L2-009 抢红包 排序
没有人没抢过红包吧…… 这里给出N个人之间互相发红包、抢红包的记录，请你统计一下他们抢红包的收获。
输入格式：
输入第一行给出一个正整数N（≤104），即参与发红包和抢红包的总人数，则这些人从1到N编号。随后N行，第i行给出编号为i的人发红包的记录，格式如下：
K**N1P1⋯NKP**K
其中K（0≤K≤20）是发出去的红包个数，N**i是抢到红包的人的编号，P**i（>0）是其抢到的红包金额（以分为单位）。注意：对于同一个人发出的红包，每人最多只能抢1次，不能重复抢。
输出格式：
按照收入金额从高到低的递减顺序输出每个人的编号和收入金额（以元为单位，输出小数点后2位）。每个人的信息占一行，两数字间有1个空格。如果收入金额有并列，则按抢到红包的个数递减输出；如果还有并列，则按个人编号递增输出。
输入样例：
10
3 2 22 10 58 8 125
5 1 345 3 211 5 233 7 13 8 101
1 7 8800
2 1 1000 2 1000
2 4 250 10 320
6 5 11 9 22 8 33 7 44 10 55 4 2
1 3 8800
2 1 23 2 123
1 8 250
4 2 121 4 516 7 112 9 10
输出样例：
1 11.63
2 3.63
8 3.63
3 2.11
7 1.69
6 -1.67
9 -2.18
10 -3.26
5 -3.26
4 -12.32
分析：
就是细节题，题目让你干什么就干什么。结构体中自定义排序规则
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
typedef long long ll;
struct node{
int id,money,num;
const bool operator < (const node &t) const {
if(t.money == money)
return id > t.id;
return money > t.money;
}
}peo[N];
int main(){
int n; cin>>n;
for(int i = 1 ; i <= n ; i ++) peo[i].id = i;
for(int i = 1 ; i <= n ; i ++){
int k,sum=0; cin>>k;
for(int j = 0 ; j < k ; j++){
int x,m; cin>>x>>m;
peo[x].money += m;
sum += m;
peo[x].num ++;
}
peo[i].money -= sum;
}
sort(peo+1, peo+1+n);
for(int i = 1 ; i <= n ; i ++)
printf("%d %.2lf\n", peo[i].id, peo[i].money*1.0/100);
return 0;
}
L2-010 排座位 dfs
布置宴席最微妙的事情，就是给前来参宴的各位宾客安排座位。无论如何，总不能把两个死对头排到同一张宴会桌旁！这个艰巨任务现在就交给你，对任何一对客人，请编写程序告诉主人他们是否能被安排同席。
输入格式：
输入第一行给出3个正整数：N（≤100），即前来参宴的宾客总人数，则这些人从1到N编号；M为已知两两宾客之间的关系数；K为查询的条数。随后M行，每行给出一对宾客之间的关系，格式为：宾客1 宾客2 关系，其中关系为1表示是朋友，-1表示是死对头。注意两个人不可能既是朋友又是敌人。最后K行，每行给出一对需要查询的宾客编号。
这里假设朋友的朋友也是朋友。但敌人的敌人并不一定就是朋友，朋友的敌人也不一定是敌人。只有单纯直接的敌对关系才是绝对不能同席的。
输出格式：
对每个查询输出一行结果：如果两位宾客之间是朋友，且没有敌对关系，则输出No problem；如果他们之间并不是朋友，但也不敌对，则输出OK；如果他们之间有敌对，然而也有共同的朋友，则输出OK but...；如果他们之间只有敌对关系，则输出No way。
输入样例：
7 8 4
5 6 1
2 7 -1
1 3 1
3 4 1
6 7 -1
1 2 1
1 4 1
2 3 -1
3 4
5 7
2 3
7 2
输出样例：
No problem
OK
OK but...
No way
分析：
N≤100，说明可以直接建图后进行dfs遍历，只遍历边权为1的点，如果可以从a走到b，说明有共同朋友，再判断mp[a][b]是否为-1即可。其他情况类似。
代码：
#include <bits/stdc++.h>
using namespace std;
int n, m, k, a, b, c;
int mp[111][111],vis[111];
bool dfs(int now,int end) {
if(now==end) return true;
for(int i=1;i<=n;i++){
if(mp[now][i]==1&&vis[i]==0){
vis[now]=1;
if(dfs(i,end)) return true;
vis[now]=0;
}
}
return false;
}
int main() {
cin>>n>>m>>k;
for (int i=0;i<m;i++) {
cin>>a>>b>>c;
mp[a][b]=mp[b][a]=c;
}
while (k--) {
cin>>a>>b;
for(int i=1;i<=n;i++) vis[i]=0;
vis[a]=1;
bool flag=dfs(a,b);
if(flag && mp[a][b]!=-1) cout<<"No problem"<<endl;
if(flag && mp[a][b]==-1) cout<<"OK but..."<<endl;
if(!flag && mp[a][b]!=-1) cout<<"OK"<<endl;
if(!flag && mp[a][b]==-1) cout<<"No way"<<endl;
}
return 0;
}
