企业官网建设流程全解析

官网https://pintia.cn/problem-sets/994805046380707840/exam/problems/type/7

L2-037 包装机

题目分析
本题是数据结构基础模拟题，核心考察队列与栈的典型应用场景：

• 轨道上的物品遵循「先放置先掉落」的规则，符合队列先进先出的特性；
• 筐中的物品遵循「最后放入的最先被抓取」的规则，符合栈后进先出的特性；
• 需要处理两种边界情况：筐满时强制弹出栈顶、轨道/筐为空时操作无效。

解题思路

1. 数据结构选型
   • 用queue<char>数组存储每条轨道的物品，数组下标对应轨道编号（1~n）；
   • 用stack<char>存储筐中的物品。
2. 逐操作模拟
   • 读入操作编号，遇到-1终止循环；
   • 操作0：若栈非空，弹出栈顶元素并直接输出；
   • 操作k (k>0)：
     • 若第k条轨道队列为空，跳过本次操作；
     • 若筐已满（栈大小等于最大容量），先弹出栈顶元素输出，腾出空间；
     • 将轨道队首元素压入栈，同时轨道队首出队。

时间复杂度
每个物品最多入队/出队、入栈/出栈各一次，总操作数与物品数量、操作数线性相关，时间复杂度为O(N)，完全满足题目数据范围。

AC代码

#include<bits/stdc++.h>usingnamespacestd;constintN=110;queue<char>q[N];// 每条轨道对应一个队列intmain(){intn,m,s;cin>>n>>m>>s;// 读入每条轨道的初始物品for(inti=1;i<=n;i++){for(intj=0;j<m;j++){charc;cin>>c;q[i].push(c);}}stack<char>st;// 筐，用栈存储intop;while(cin>>op){if(op==-1)break;// 输入结束标志if(op==0){// 0号操作：抓取筐顶物品到流水线if(!st.empty()){cout<<st.top();st.pop();}}else{// 按下对应轨道按钮if(q[op].empty())continue;// 轨道为空，无操作// 筐已满，强制先弹出一个物品if(st.size()==s){cout<<st.top();st.pop();}// 轨道尽头物品落入筐中st.push(q[op].front());q[op].pop();}}return0;}

L2-038 病毒溯源

题目分析
本题是树的深度遍历经典题，核心考察树的存储、最长路径查找、字典序最小路径输出：

• 病毒变异关系构成一棵有根树，每个节点仅有一个父节点，无环，入度为0的节点是病毒源头；
• 要求找到从根出发的最长变异链，若有多条长度相同的最长链，输出字典序最小的一条。

解题思路

1. 建树与找根
   • 用vector<int>数组存储每个节点的子节点，构建邻接表；
   • 统计每个节点的入度，入度为0的节点即为树的根。
2. 第一次DFS求最长链长度
   • 从根节点出发深度优先遍历，记录路径的最大长度。
3. 子节点排序保证字典序
   • 将每个节点的子节点按编号从小到大排序，DFS时优先遍历小编号子节点，第一条找到的最长链就是字典序最小的。
4. 第二次DFS输出路径
   • 用数组记录当前路径，当路径长度等于最长长度时，直接输出路径并终止程序。

时间复杂度
每个节点仅被遍历两次（两次DFS），总时间复杂度为O(N)，满足数据范围要求。

AC代码

#include<bits/stdc++.h>usingnamespacestd;constintN=1e4+9;vector<int>v[N];// 邻接表，存储每个节点的子节点intdu[N];// 入度数组，用于查找根节点intpath[N];// 记录当前搜索路径intmaxLen;// 最长变异链长度// 第一次DFS：计算最长链长度voiddfs_len(intu,intlen){maxLen=max(maxLen,len);for(intson:v[u]){dfs_len(son,len+1);}}// 第二次DFS：查找字典序最小的最长链voiddfs_path(intu,intlen){path[len]=u;if(len==maxLen){// 找到目标路径，直接输出并退出for(inti=1;i<=maxLen;i++){cout<<path[i];if(i!=maxLen)cout<<' ';}exit(0);// 终止程序，保证第一个找到的就是字典序最小}for(intson:v[u]){dfs_path(son,len+1);}}intmain(){intn;cin>>n;for(inti=0;i<n;i++){intk,x;cin>>k;while(k--){cin>>x;du[x]++;v[i].push_back(x);}}// 查找根节点（入度为0）introot=0;for(inti=0;i<n;i++){if(du[i]==0){root=i;break;}}// 第一步：求最长链长度dfs_len(root,1);cout<<maxLen<<'\n';// 子节点升序排序，保证DFS优先走小编号节点for(inti=0;i<n;i++){sort(v[i].begin(),v[i].end());}// 第二步：输出字典序最小的最长链dfs_path(root,1);return0;}

L2-039 清点代码库

题目分析
本题是STL综合应用题，核心考察vector作为映射键、自定义排序规则的使用：

• 功能相同等价于输出序列完全一致，可用序列作为唯一标识统计出现次数；
• 输出要求按模块数量降序，数量相同时按输出序列字典序升序。

解题思路

1. 映射统计频次
   • 利用map<vector<int>, int>统计每个输出序列出现的次数；
   • vector天然支持字典序比较，可直接作为map的键，完全符合题目对序列大小的定义。
2. 结构化存储与排序
   • 将map中的键值对转为结构体存入vector，方便自定义排序；
   • 重载比较运算符：优先按出现次数降序，次数相同时按序列字典序升序。
3. 按格式输出
   • 先输出不同功能的总数，再逐行输出次数和对应输出序列。

时间复杂度

• 插入map的时间为O(N·M logN)（N为模块数，M为每个模块输出个数）；
• 排序时间为O(K logK)（K为不同功能的数量，K≤N）；
• 整体复杂度完全满足题目数据范围。

AC代码

#include<bits/stdc++.h>usingnamespacestd;// 功能结构体：存储输出序列与对应模块数量structFunc{vector<int>output;intcnt;// 自定义排序规则booloperator<(constFunc&other)const{if(cnt!=other.cnt){returncnt>other.cnt;// 数量多的排在前面}returnoutput<other.output;// 数量相同，序列字典序小的在前}};map<vector<int>,int>mp;vector<Func>ans;intmain(){intn,m;cin>>n>>m;// 统计每个功能出现的次数for(inti=0;i<n;i++){vector<int>tmp;for(intj=0;j<m;j++){intx;cin>>x;tmp.push_back(x);}mp[tmp]++;}// 将map数据转入vector，便于自定义排序for(auto&item:mp){ans.push_back({item.first,item.second});}// 按题目规则排序sort(ans.begin(),ans.end());// 输出结果cout<<ans.size()<<'\n';for(auto&f:ans){cout<<f.cnt;for(intnum:f.output){cout<<' '<<num;}cout<<'\n';}return0;}

L2-040 哲哲打游戏

题目分析
本题是简单模拟题，核心考察数组模拟、下标偏移处理，属于基础送分题：

• 剧情点的跳转关系用邻接表存储；
• 存档功能用数组记录每个档位对应的剧情点；
• 按顺序模拟所有操作，最终输出终点剧情点。

解题思路

1. 存储跳转关系
   • 用vector<int>数组存储每个剧情点的所有选项对应的目标剧情点；
   • 选项编号从1开始，数组下标从0开始，访问时需要做下标减1处理。
2. 存档数组
   • 用数组记录每个档位存储的剧情点编号，档位从1开始，题目约定不超过100档。
3. 逐操作模拟
   • 初始当前剧情点为1；
   • 操作0：根据选项号跳转剧情点；
   • 操作1：输出当前剧情点，并将当前剧情点存入对应档位；
   • 操作2：将当前剧情点更新为对应档位的存档内容。
4. 所有操作结束后，输出最终的当前剧情点。

时间复杂度
每个操作仅执行一次，跳转、存档、读档都是O(1)操作，总时间复杂度为O(M)，效率极高。

AC代码

#include<bits/stdc++.h>usingnamespacestd;constintN=1e5+9;vector<int>plot[N];// 每个剧情点的跳转选项intsave[105];// 存档档位，最多100档intmain(){intn,m;cin>>n>>m;// 读入每个剧情点的跳转关系for(inti=1;i<=n;i++){intk,x;cin>>k;while(k--){cin>>x;plot[i].push_back(x);}}intnow=1;// 当前剧情点，初始为1号while(m--){intop,b;cin>>op>>b;if(op==0){// 选择第b个选项，跳转剧情now=plot[now][b-1];}elseif(op==1){// 存档到第b档，输出当前剧情点cout<<now<<'\n';save[b]=now;}elseif(op==2){// 读取第b档存档now=save[b];}}// 输出最终到达的剧情点cout<<now;return0;}