PTA团体程序设计天梯赛L2真题讲解L2-037-040
官网https://pintia.cn/problem-sets/994805046380707840/exam/problems/type/7文章目录L2-037 包装机L2-038 病毒溯源L2-039 清点代码库L2-040 哲哲打游戏L2-037 包装机题目分析本题是数据结构基础模拟题核心考察队列与栈的典型应用场景轨道上的物品遵循「先放置先掉落」的规则符合队列先进先出的特性筐中的物品遵循「最后放入的最先被抓取」的规则符合栈后进先出的特性需要处理两种边界情况筐满时强制弹出栈顶、轨道/筐为空时操作无效。解题思路数据结构选型用queuechar数组存储每条轨道的物品数组下标对应轨道编号1~n用stackchar存储筐中的物品。逐操作模拟读入操作编号遇到-1终止循环操作0若栈非空弹出栈顶元素并直接输出操作k (k0)若第k条轨道队列为空跳过本次操作若筐已满栈大小等于最大容量先弹出栈顶元素输出腾出空间将轨道队首元素压入栈同时轨道队首出队。时间复杂度每个物品最多入队/出队、入栈/出栈各一次总操作数与物品数量、操作数线性相关时间复杂度为O(N)完全满足题目数据范围。AC代码#includebits/stdc.husingnamespacestd;constintN110;queuecharq[N];// 每条轨道对应一个队列intmain(){intn,m,s;cinnms;// 读入每条轨道的初始物品for(inti1;in;i){for(intj0;jm;j){charc;cinc;q[i].push(c);}}stackcharst;// 筐用栈存储intop;while(cinop){if(op-1)break;// 输入结束标志if(op0){// 0号操作抓取筐顶物品到流水线if(!st.empty()){coutst.top();st.pop();}}else{// 按下对应轨道按钮if(q[op].empty())continue;// 轨道为空无操作// 筐已满强制先弹出一个物品if(st.size()s){coutst.top();st.pop();}// 轨道尽头物品落入筐中st.push(q[op].front());q[op].pop();}}return0;}L2-038 病毒溯源题目分析本题是树的深度遍历经典题核心考察树的存储、最长路径查找、字典序最小路径输出病毒变异关系构成一棵有根树每个节点仅有一个父节点无环入度为0的节点是病毒源头要求找到从根出发的最长变异链若有多条长度相同的最长链输出字典序最小的一条。解题思路建树与找根用vectorint数组存储每个节点的子节点构建邻接表统计每个节点的入度入度为0的节点即为树的根。第一次DFS求最长链长度从根节点出发深度优先遍历记录路径的最大长度。子节点排序保证字典序将每个节点的子节点按编号从小到大排序DFS时优先遍历小编号子节点第一条找到的最长链就是字典序最小的。第二次DFS输出路径用数组记录当前路径当路径长度等于最长长度时直接输出路径并终止程序。时间复杂度每个节点仅被遍历两次两次DFS总时间复杂度为O(N)满足数据范围要求。AC代码#includebits/stdc.husingnamespacestd;constintN1e49;vectorintv[N];// 邻接表存储每个节点的子节点intdu[N];// 入度数组用于查找根节点intpath[N];// 记录当前搜索路径intmaxLen;// 最长变异链长度// 第一次DFS计算最长链长度voiddfs_len(intu,intlen){maxLenmax(maxLen,len);for(intson:v[u]){dfs_len(son,len1);}}// 第二次DFS查找字典序最小的最长链voiddfs_path(intu,intlen){path[len]u;if(lenmaxLen){// 找到目标路径直接输出并退出for(inti1;imaxLen;i){coutpath[i];if(i!maxLen)cout ;}exit(0);// 终止程序保证第一个找到的就是字典序最小}for(intson:v[u]){dfs_path(son,len1);}}intmain(){intn;cinn;for(inti0;in;i){intk,x;cink;while(k--){cinx;du[x];v[i].push_back(x);}}// 查找根节点入度为0introot0;for(inti0;in;i){if(du[i]0){rooti;break;}}// 第一步求最长链长度dfs_len(root,1);coutmaxLen\n;// 子节点升序排序保证DFS优先走小编号节点for(inti0;in;i){sort(v[i].begin(),v[i].end());}// 第二步输出字典序最小的最长链dfs_path(root,1);return0;}L2-039 清点代码库题目分析本题是STL综合应用题核心考察vector作为映射键、自定义排序规则的使用功能相同等价于输出序列完全一致可用序列作为唯一标识统计出现次数输出要求按模块数量降序数量相同时按输出序列字典序升序。解题思路映射统计频次利用mapvectorint, int统计每个输出序列出现的次数vector天然支持字典序比较可直接作为map的键完全符合题目对序列大小的定义。结构化存储与排序将map中的键值对转为结构体存入vector方便自定义排序重载比较运算符优先按出现次数降序次数相同时按序列字典序升序。按格式输出先输出不同功能的总数再逐行输出次数和对应输出序列。时间复杂度插入map的时间为O(N·M logN)N为模块数M为每个模块输出个数排序时间为O(K logK)K为不同功能的数量K≤N整体复杂度完全满足题目数据范围。AC代码#includebits/stdc.husingnamespacestd;// 功能结构体存储输出序列与对应模块数量structFunc{vectorintoutput;intcnt;// 自定义排序规则booloperator(constFuncother)const{if(cnt!other.cnt){returncntother.cnt;// 数量多的排在前面}returnoutputother.output;// 数量相同序列字典序小的在前}};mapvectorint,intmp;vectorFuncans;intmain(){intn,m;cinnm;// 统计每个功能出现的次数for(inti0;in;i){vectorinttmp;for(intj0;jm;j){intx;cinx;tmp.push_back(x);}mp[tmp];}// 将map数据转入vector便于自定义排序for(autoitem:mp){ans.push_back({item.first,item.second});}// 按题目规则排序sort(ans.begin(),ans.end());// 输出结果coutans.size()\n;for(autof:ans){coutf.cnt;for(intnum:f.output){cout num;}cout\n;}return0;}L2-040 哲哲打游戏题目分析本题是简单模拟题核心考察数组模拟、下标偏移处理属于基础送分题剧情点的跳转关系用邻接表存储存档功能用数组记录每个档位对应的剧情点按顺序模拟所有操作最终输出终点剧情点。解题思路存储跳转关系用vectorint数组存储每个剧情点的所有选项对应的目标剧情点选项编号从1开始数组下标从0开始访问时需要做下标减1处理。存档数组用数组记录每个档位存储的剧情点编号档位从1开始题目约定不超过100档。逐操作模拟初始当前剧情点为1操作0根据选项号跳转剧情点操作1输出当前剧情点并将当前剧情点存入对应档位操作2将当前剧情点更新为对应档位的存档内容。所有操作结束后输出最终的当前剧情点。时间复杂度每个操作仅执行一次跳转、存档、读档都是O(1)操作总时间复杂度为O(M)效率极高。AC代码#includebits/stdc.husingnamespacestd;constintN1e59;vectorintplot[N];// 每个剧情点的跳转选项intsave[105];// 存档档位最多100档intmain(){intn,m;cinnm;// 读入每个剧情点的跳转关系for(inti1;in;i){intk,x;cink;while(k--){cinx;plot[i].push_back(x);}}intnow1;// 当前剧情点初始为1号while(m--){intop,b;cinopb;if(op0){// 选择第b个选项跳转剧情nowplot[now][b-1];}elseif(op1){// 存档到第b档输出当前剧情点coutnow\n;save[b]now;}elseif(op2){// 读取第b档存档nowsave[b];}}// 输出最终到达的剧情点coutnow;return0;}

相关新闻

AI驱动Figma设计:基于Claude Code与Plugin API的智能工作流实践

AI驱动Figma设计:基于Claude Code与Plugin API的智能工作流实践

1. 项目概述:当设计工具“活”了过来如果你和我一样,常年泡在Figma里,从线框图一路画到高保真,那你一定对那种“重复劳动”的疲惫感深有体会。调整一个组件的间距,得手动框选几十个实例;想尝试一个新的布局…

2026/11/9 22:07:22 阅读更多 →
SpringBoot在线投票系统开发与毕业设计实践

SpringBoot在线投票系统开发与毕业设计实践

1. 项目概述:SpringBoot在线投票系统的核心价值网络投票系统在当今数字化社会中扮演着越来越重要的角色。我最近用SpringBoot完整实现了一个B/S架构的在线投票平台,这个系统特别适合作为计算机专业毕业设计选题,因为它涵盖了Web开发的完整技术…

2026/11/17 4:08:31 阅读更多 →
从零构建技术博客:以Istio服务网格部署为例的写作方法论与实践

从零构建技术博客:以Istio服务网格部署为例的写作方法论与实践

在实际技术写作中,我们经常会遇到一个看似简单却容易出错的任务:如何将零散、不完整甚至缺失的原始材料,系统性地重构为一篇结构严谨、内容充实、可指导实践的技术博客。本文将以一个极端案例——“Jason Liu 晒新玩具引热议”这个仅有标题、…

2026/11/17 2:57:16 阅读更多 →

最新新闻

Electron桌面应用开发实战:从环境搭建到打包发布全流程

Electron桌面应用开发实战:从环境搭建到打包发布全流程

做前端这些年,我大部分时间都在跟浏览器标签页打交道,直到第一次把桌面应用跑起来,才发现原来自己一直被限制在地址栏和刷新按钮围起来的框框里。Electron这个词,最开始是在某段时间频繁出现在同事的讨论里,一个用HTML…

2026/11/18 13:59:04 阅读更多 →
滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

简介:亚太天能T109滑盖智能锁产品说明书是一份PDF格式的官方技术文档,主要面向智能锁安装人员、终端用户及售后维护者,帮助快速掌握产品安装、配置与常见故障处理。全包仅1个PDF文件,大小4.37MB,内容结构清晰&#xff…

2026/11/18 15:33:23 阅读更多 →
PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

上个月我在调试一台高速AGV的驱动系统,整车要求空载跑到8m/s,电机转速已经拉到额定点,驱动器的输出电压也顶到了母线电压极限附近。再往上踩速度指令,转速纹丝不动,三相电流反而开始震荡。那会儿我的第一反应就是&…

2026/11/18 17:05:28 阅读更多 →
C++核心知识点:从内存管理到STL的实战指南

C++核心知识点:从内存管理到STL的实战指南

C 这门语言我前前后后折腾了十几年,用它写过嵌入式驱动、做过游戏服务端,也搭过基础组件库。每次看到新人一头扎进"C 核心知识点"这个搜索词,我其实挺感慨的——这门语言的难点从来不是语法多,而是知识点之间的耦合太深…

2026/11/18 14:33:19 阅读更多 →
T109滑盖智能锁怎么装?安装调试与故障排查全攻略

T109滑盖智能锁怎么装?安装调试与故障排查全攻略

简介:亚太天能T109滑盖智能锁产品说明书以PDF格式发布,适合智能锁用户、安装人员与售后维修人员阅读。内容围绕T109系列指纹密码刷卡锁展开,先介绍前面板、后面板、锁体、机械钥匙、电池盒盖等部件名称与功能,再给出完整安装步骤&…

2026/11/18 17:05:28 阅读更多 →
LLM知识降熵:从信息垄断到理解权下放

LLM知识降熵:从信息垄断到理解权下放

你有没有过这种经历:翻开源码注释、论文摘要或者一份专业报告,每个字都认识,连在一起却像天书。想找人聊聊,身边要么没人懂,要么懂的懒得跟你解释。后来我试着把同一段内容丢给一个大语言模型,几秒钟之后&a…

2026/11/18 14:13:08 阅读更多 →

日新闻

周新闻

月新闻