L1-8 猜数字 (20 分)
题意：
一群人坐在一起，每人猜一个 100 以内的数，谁的数字最接近大家平均数的一半就赢。本题就要求你找出其中的赢家。
思路：
题目要求其实可以提出来，假设第i个人猜的数为ai，且所有人的数字之和为sum，那么本质就是找找对于每个i，找的最小值，这里我怕精度,于是直接转
代码：
#include<bits/stdc++.h> using namespace std; const int maxn=1e5; struct node { string name; int val; }mo[maxn]; bool cmp1(node a,node b ) { return a.val<b.val; } int main() { int n,i,j,t,sum=0; cin>>n; for(i=0;i<n;i++) { cin>>mo[i].name>>mo[i].val; sum+=mo[i].val; } for(i=0;i<n;i++) { mo[i].val=abs(sum-mo[i].val*2*n); } sort(mo,mo+n,cmp1); cout<<(int)(sum/(n*2))<<" "<<mo[0].name<<endl; return 0; }
L2-1 分而治之 (25 分)
题意：
分而治之，各个击破是兵家常用的策略之一。在战争中，我们希望首先攻下敌方的部分城市，使其剩余的城市变成孤立无援，然后再分头各个击破。为此参谋部提供了若干打击方案。本题就请你编写程序，判断每个方案的可行性。
输入：
输入在第一行给出两个正整数 N 和 M（均不超过10 000），分别为敌方城市个数（于是默认城市从 1 到 N 编号）和连接两城市的通路条数。随后 M 行，每行给出一条通路所连接的两个城市的编号，其间以一个空格分隔。在城市信息之后给出参谋部的系列方案，即一个正整数 K （≤ 100）和随后的 K 行方案，每行按以下格式给出：
Np v[1] v[2] ... v[Np]
其中 Np 是该方案中计划攻下的城市数量，后面的系列 v[i] 是计划攻下的城市编号。
输出：
对每一套方案，如果可行就输出YES，否则输出NO。
思路：
一开始读题读错了，一定要注意他题意其实是说，把方案数里的所有城市关闭，那么剩下的城市是否能全部被孤立，孤立就是说没有和其他城市相连，那么其实你按照题意把树建好之后，将攻下的城市打下标机，然后每个点遍历，只要有一个点能去往其他城市，直接输出NO。
代码：
#include<bits/stdc++.h> #include<unordered_map> using namespace std; const int maxn=10005; int N,M; vector<int >edges[maxn]; int main() { int i,j; cin>>N>>M; for(i=0;i<M;i++) { int a,b; cin>>a>>b; edges[a].push_back(b); edges[b].push_back(a); } int k; cin>>k; unordered_map<int ,int >mo; while(k--) { int d,flag=0; cin>>d; vector<int> qry(d); for(int &i:qry ){ cin>>i; mo[i]=1; } for(i=1;i<=N;i++) { if(mo[i]==0) { for(j=0;j<edges[i].size();j++) { if(mo[edges[i][j]]==0) { flag=1; cout<<"NO"<<endl; break; } } } if(flag==1) break; } if(flag==0){ cout<<"YES"<<endl; } mo.clear(); } return 0; }
L2-2 小字辈 (25 分)
题意：
输入在第一行给出家族人口总数 N（不超过 100 000 的正整数） —— 简单起见，我们把家族成员从 1 到 N 编号。随后第二行给出 N 个编号，其中第 i 个编号对应第 i 位成员的父/母。家谱中辈分最高的老祖宗对应的父/母编号为 -1。一行中的数字间以空格分隔。
思路：
把成员和父母之间的关系连边建好，对于每个i来说a[i]就是父节点，i就是子节点，-1就是源头，然后从源头开始bfs，对每个边打上深度标机，然后找深度最大的再输出即可。
代码：
#include<bits/stdc++.h> #include<unordered_map> using namespace std; const int maxn=100005; int a[maxn]; int main() { int n,i,j,t; cin>>n; vector<int >edges[n]; for(i=0;i<=n;i++) { edges[i].clear(); } for(i=1;i<=n;i++) { cin>>a[i]; if(a[i]==-1) a[i]=0; edges[a[i]].push_back(i); } deque<int >qq; qq.push_back(0); unordered_map<int ,int >mo; mo[0]=1; int ans=1; while(!qq.empty()) { int d1=qq.front(); qq.pop_front(); for(i=0;i<edges[d1].size();i++) { if(mo[edges[d1][i]]==0) { mo[edges[d1][i]]=mo[d1]+1; qq.push_back(edges[d1][i]); ans=max(ans,mo[d1]+1); } } } cout<<ans-1<<endl; vector<int >ans1; for(auto &[a,b]:mo) { if(b==ans) { ans1.push_back(a); } } sort(ans1.begin(),ans1.end()); for(i=0;i<ans1.size()-1;i++) cout<<ans1[i]<<" "; cout<<ans1[i]<<endl; }
L2-3 名人堂与代金券 (25 分)
题意：
对于在中国大学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 个空格分隔。需要注意的是：成绩相同的学生享有并列的排名，排名并列时，按账号的字母序升序输出。
思路：
非常简单的一道题，直接一个结构体排序重载一下即可。
#include<bits/stdc++.h> #include<unordered_map> using namespace std; const int maxn=10005; struct node{ string s1; int val; }mo[maxn]; bool cmp1(node a,node b ) { return a.val<b.val; } int main() { int n,g,k,sum=0,i,j; cin>>n>>g>>k; for(i=0;i<n;i++) { cin>>mo[i].s1>>mo[i].val; if(mo[i].val>=60&&mo[i].val<g) sum+=20; else if(mo[i].val>=g) sum+=50; } cout<<sum<<endl; sort(mo,mo+n,cmp1); for(i=1;i<=n;i++) { if(mo[i].val<=mo[k].val) cout<<i<<" "<<mo[i].s1<<" "<<mo[i].val<<endl; else break; } return 0; }
