官网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;}