PTA团体程序设计天梯赛L2真题讲解L2-025-028

官网https://pintia.cn/problem-sets/994805046380707840/exam/problems/type/7文章目录L2-025 分而治之L2-026 小字辈L2-027 名人堂与代金券L2-028 秀恩爱分得快L2-025 分而治之题目大意给定N个城市、M条通路构成的无向图。给出K个方案每个方案指定要攻占的城市集合。判断攻占这些城市后剩余的所有城市之间是否不存在任何通路即剩余城市全部孤立是则输出YES否则输出NO。解题思路核心是判断删点后剩余图的边数是否为0。直接每次删点重建图效率过低因此采用度数统计法预先存储每个点的初始度数以及每个点的邻接表。对于每个方案先复制一份所有点的初始度数。遍历每一个被攻占的城市x将x的度数置为0相当于删除该点同时遍历x的所有邻居将邻居的度数减1相当于删除x连向邻居的边。最后统计所有城市的度数之和若总和为0说明剩余城市之间没有边方案可行输出YES否则输出NO。复杂度分析每个方案遍历所有点和边总时间复杂度为O ( K × ( N M ) ) O(K\times(NM))O(K×(NM))在题目数据范围下完全可以通过。代码解析g[N]邻接表存储无向图的连接关系。sz[]临时数组记录每个点当前的剩余度数。每次询问初始化sz数组为各点原始度数处理被攻占的点后统计度数总和判断是否为0。正解代码#includebits/stdc.husingnamespacestd;constintN1e49;intn,m,k,t,sz[N];vectorintg[N];intmain(){cinnm;for(inti0;im;i){intu,v;cinuv;g[u].push_back(v);g[v].push_back(u);}cink;while(k--){cint;for(inti1;in;i){sz[i]g[i].size();//coutsz[i] ;}intcnt0;for(inti0;it;i){intx;cinx;for(autont:g[x])sz[nt]max(0,sz[nt]-1);//度数减1时不能小于0sz[x]0;//被攻占的城市本身要置为度数0不计入剩余边。}for(inti1;in;i)cntsz[i];if(!cnt)coutYES\n;elsecoutNO\n;}return0;}L2-026 小字辈题目大意给定一个家族的家谱结构每个成员有唯一的父/母编号老祖宗的父/母编号为-1。老祖宗辈分为1每向下一代辈分1。请找出辈分最小深度最大的所有成员输出最小辈分和对应的成员编号。解题思路这是一道典型的树的深度遍历问题首先根据输入的父节点信息建树将每个节点加入其父节点的邻接表中同时记录根节点父节点为-1的节点。从根节点出发进行DFS或BFS计算每个节点的深度辈分同时记录最大深度。遍历所有节点收集所有深度等于最大深度的节点按编号升序输出。代码解析g[N]存储家族树的邻接表每个节点存储它的子节点。a[]记录每个节点的深度辈分。dfs函数递归遍历子节点子节点深度 当前节点深度 1同时更新最大深度mx。最后遍历所有节点收集答案按编号顺序输出。正解代码#includebits/stdc.h//#define int long longusingnamespacestd;constintN1e59;inta[N],t,x,n,root,mx;vectorintg[N];voiddfs(intnow,intdeep){a[now]deep;mxmax(mx,deep);if(!g[now].size())return;for(autont:g[now])dfs(nt,deep1);}signedmain(){cinn;for(inti1;in;i){intx;cinx;if(x!-1)g[x].push_back(i);elserooti;}dfs(root,1);vectorintans;for(inti1;in;i)if(a[i]mx)ans.push_back(i);coutmx\n;for(inti0;ians.size();i){coutans[i];if(i!ans.size()-1)cout ;}return0;}L2-027 名人堂与代金券题目大意给定N名学生的账号和总评成绩按规则计算代金券总额并输出进入名人堂的学生名单。规则成绩≥G奖励50元代金券60≤成绩G奖励20元代金券60无奖励。名人堂为总排名前K名的学生成绩相同则并列排名并列时按账号字典序升序排列。解题思路自定义排序按成绩降序排列成绩相同则按账号字符串字典序升序排列。统计代金券遍历排序后的数组按成绩区间累加代金券总额。处理并列排名名次规则为“成绩不同时名次等于当前已遍历人数”。例如第1、2名成绩不同第3、4名成绩相同则两人都是第3名下一名为第5名。遍历输出直到名次超过K为止。正解代码#includebits/stdc.husingnamespacestd;constintN1e59;structnd{string id;intsco;booloperator(constnd nd1){if(sco!nd1.sco)returnscond1.sco;returnidnd1.id;}}v[N];intn,x,k,G;intmain(){cinnGk;for(inti1;in;i){cinv[i].idv[i].sco;}intcnt0,rting0,res0;sort(v1,v1n);for(inti1;in;i){if(v[i].sco60)break;if(v[i].scoG)cnt50;elsecnt20;}coutcnt\n;cout1 v[1].id v[1].sco\n;rting1;res1;//总人数for(inti2;in;i){res;if(v[i].sco!v[i-1].sco)rtingres;if(rtingk)break;coutrting v[i].id v[i].sco\n;}return0;}代码解析结构体nd存储学生账号id和成绩sco重载运算符实现自定义排序规则。cnt统计代金券总金额。rting记录当前名次res记录当前已遍历的总人数。当成绩与前一名不同时更新名次为当前人数。L2-028 秀恩爱分得快题目大意给定M张照片每张照片有K个人。任意一对异性若同框亲密度增加1/K。给定一对异性情侣A、B分别找出与A、B亲密度最高的异性。若A和B互为对方的最高亲密度则只输出两人否则分别输出各自的最高亲密度异性多人并列时按编号绝对值升序输出。解题思路性别与编号处理编号带负号为女性正号为男性存储时用绝对值作为数组下标单独记录性别。亲密度计算对于每张照片将男性、女性分为两组遍历所有男女组合给他们的亲密度加上1/K。查询最高亲密度分别找到与A、B亲密度最高的异性的亲密度数值。判断特殊情况若A与B的亲密度同时等于双方的最高亲密度说明二人互为最亲密异性直接输出二人编号。否则分别输出A、B对应的所有最高亲密度异性。正解代码#includebits/stdc.husingnamespacestd;constintN1010;intn,m;doubleg[N][N];//g 男女intmain(){cinnm;for(inti0;im;i){intx;string y;vectorintby,gl;cinx;for(intj0;jx;j){ciny;intyystoi(y);if(y[0]-){//女gl.push_back(abs(yy));}elseby.push_back(yy);//男}for(intj0;jby.size();j){for(intk0;kgl.size();k){g[by[j]][gl[k]]1.0/(x*1.0);}}}string na1,na2;boolfg0;//女男 1男女cinna1na2;intn1abs(stoi(na1));intn2abs(stoi(na2));if(na2[0]-){fg1;swap(n1,n2);swap(na1,na2);}doublemxby0,mxgl0;//最亲密男朋友 女朋友for(inti0;in;i)mxbymax(mxby,g[i][n1]);for(inti0;in;i)mxglmax(mxgl,g[n2][i]);if(g[n2][n1]mxglg[n2][n1]mxby){if(!fg)coutna1 na2\n;elsecoutna2 na1\n;return0;}if(!fg){//先女for(inti0;in;i)if(g[i][n1]mxby)cout-n1 i\n;for(inti0;in;i)if(g[n2][i]mxgl)coutn2 -i\n;}else{//先男for(inti0;in;i)if(g[n2][i]mxgl)coutn2 -i\n;for(inti0;in;i)if(g[i][n1]mxby)cout-n1 i\n;}return0;}代码解析g[N][N]二维数组存储异性间的亲密度第一维为男性编号第二维为女性编号。每张照片拆分男性列表by和女性列表gl双重循环累加亲密度。fg标记输入的情侣顺序女男/男女保证最终输出顺序与输入一致。最后分别遍历所有异性找出最高亲密度对应的所有编号并输出。