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标记输入的情侣顺序女男/男女保证最终输出顺序与输入一致。最后分别遍历所有异性找出最高亲密度对应的所有编号并输出。

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

相关推荐

AI 行业的架构多动症与管理学组织团队协作的最优解

【 Seedance 2.5创意玩法技术解析】长视频生成如何从演示走向可控生产

采用本地Portal服务器与LDAP服务器组合对用户认证的典型配置

更多资讯

Linux内存安全：用mlock防止密钥泄露到Swap

时序场景生成与削减：从蒙特卡洛采样到相关性建模的完整实践

Spring refresh()源码导读：从IoC容器初始化到Bean生命周期

2026论文降重工具红黑榜：实测八类方法，避坑与组合打法

Win7最后兼容版VS Code v1.70.3：免安装配置实战

Codeforces 946G Almost Increasing Array：删除位置与树状数组优化解析

今日更新

再见，SSE！你好，Streamable HTTP！轻松开发 Streamable HTTP MCP Server 并接入 TaoToken

工业软件标准化路线图：国产替代的落地施工图

VCMI安卓版实操指南：原生运行英雄无敌3的3步技术落地

本周精选

CMOS设计三大物理效应：体效应、沟道长度调制与亚阈值导电

微信小程序在线阅读毕设全解析：Java后端+MySQL+避坑实战

Android音频问题五层分析法：从App到Codec的系统化诊断

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？