官网https://pintia.cn/problem-sets/994805046380707840/exam/problems/type/7文章目录L2-041 插松枝L2-042 老板的作息表L2-043 龙龙送外卖L2-044 大众情人L2-041 插松枝题目大意制作松枝的流程包含三个核心对象推送器按顺序给出n片松针依次取用、小盒子栈结构容量为m后进先出、松枝干最多插k片松针要求新插的松针不能比上一片大即序列非递增。制作规则如下每根松枝从空开始制作优先取小盒子顶部的松针满足大小要求就插入盒子为空或顶部不满足要求时从推送器取松针。推送器取到的松针满足要求就插入松枝不满足且盒子未满时将松针放入盒子继续取下一片。满足以下任一条件则结束当前松枝制作开始下一根盒子满了但新取的松针仍不满足要求盒子顶部不满足要求且推送器已空松枝已插满。最终按制作顺序输出每根松枝自底向上的松针大小。核心考点栈的基础应用、流程模拟、双端队列的灵活使用。解题思路本题属于纯模拟题严格按照题目描述的操作流程实现即可核心是用栈模拟小盒子的后进先出特性用stack模拟小盒子只能操作栈顶元素。用deque模拟当前制作的松枝新松针插在顶部因此用push_front插入保证队首始终是松枝最顶端的元素方便比较大小最终从队尾到队首输出就是自底向上的顺序。每根松枝的制作流程优先尝试取栈顶元素能插就插不能插则停止取栈。若松枝已经插满直接输出并进入下一根制作。否则遍历推送器符合条件就插入松枝不符合则尝试入栈栈满则终止当前松枝制作。松枝结束后输出结果循环直到推送器取完且盒子为空。正解代码#includebits/stdc.husingnamespacestd;constintN1e59;intm,n,k,a[1010];signedmain(){cinnmk;for(inti1;in;i)cina[i];stackintst;intpos1;while(posn||st.size()){dequeintdq;while(st.size()){//先取小盒子里的if((st.top()dq.front()dq.size()k)||dq.empty()){dq.push_front(st.top());st.pop();}elsebreak;}if(dq.size()k){while(dq.size()){coutdq.back();if(dq.size()!1)cout ;dq.pop_back();}cout\n;continue;}while(posndq.size()k)//否则去推进器上取{if(a[pos]dq.front()||dq.empty()){dq.push_front(a[pos]);pos;}else{if(st.size()m){st.push(a[pos]);pos;}elsebreak;}}while(dq.size()){coutdq.back();if(dq.size()!1)cout ;dq.pop_back();}cout\n;}return0;}代码详解变量定义n为推送器松针总数m为盒子容量k为松枝容量数组a存储推送器的松针序列pos记录当前推送器的取用位置。外层循环只要推送器未取完或盒子中还有剩余松针就继续制作新的松枝。栈处理循环优先取用栈顶松针满足大小要求则插入松枝并弹栈不满足则跳出循环。满枝判断如果松枝已经达到容量k直接输出并进入下一轮循环。推送器处理循环遍历推送器当前松针符合要求则插入松枝不符合则尝试放入盒子盒子满则直接跳出循环。结果输出从deque队尾到队头依次输出对应松枝自底向上的顺序。注意事项盒子满时刚从推送器取出的松针需要“压回”对应代码中栈满时直接breakpos不递增符合题目规则。推送器取完后盒子中剩余的松针仍要继续制作新的松枝因此外层循环条件包含st.size()。输出顺序是自底向上先插入的松针在底部因此用deque头插、尾输出的方式实现。L2-042 老板的作息表题目大意给出一天内n个已安排的时间段时间段之间互不重叠最多仅端点重合。要求找出所有未被安排的空闲时间段按时间先后顺序输出格式统一为hh:mm:ss - hh:mm:ss。一天的时间范围为 00:00:00 到 23:59:59。核心考点区间排序、时间格式化处理、简单模拟。解题思路核心思路是排序后找间隙步骤如下将所有时间段按开始时间从小到大排序。检查三处可能的空闲区间当日起始00:00:00到第一个时间段的开始时间之间。每两个相邻时间段之间前一个的结束时间到后一个的开始时间之间。最后一个时间段的结束时间到当日结束23:59:59之间。若两个时间点完全相等说明没有空闲不输出该区间。正解代码#includebits/stdc.h//#define int long longusingnamespacestd;constintN1e59;intt,x,n;structsj{inth,m,s;};vectorpairsj,sjv;booloperator(sj j1,sj j2){if(j1.h!j2.h)returnj1.hj2.h;elseif(j1.m!j2.m)returnj1.mj2.m;elsereturnj1.sj2.s;}signedmain(){cinn;for(inti0;in;i){inth1,h2,m1,m2,s1,s2;scanf(%d:%d:%d - %d:%d:%d,h1,m1,s1,h2,m2,s2);v.push_back({{h1,m1,s1},{h2,m2,s2}});}sort(v.begin(),v.end());auto[h1,m1,s1]v[0].first;boolfd0;if(h10m10s10){fd1;}if(!fd)printf(00:00:00 - %02d:%02d:%02d\n,h1,m1,s1);for(inti1;iv.size();i){auto[h1,m1,s1]v[i-1].second;auto[h2,m2,s2]v[i].first;if(h1!h2||m1!m2||s1!s2)printf(%02d:%02d:%02d - %02d:%02d:%02d\n,h1,m1,s1,h2,m2,s2);}auto[h2,m2,s2]v[v.size()-1].second;if(h2!23||m2!59||s2!59)printf(%02d:%02d:%02d - 23:59:59\n,h2,m2,s2);return0;}代码详解时间结构体定义sj结构体存储时、分、秒重载运算符按时→分→秒的优先级比较大小用于时间段排序。输入与存储读入n个时间段每个时间段存为开始时间, 结束时间的pair存入vector。排序对vector按开始时间升序排列。开头空闲判断如果第一个时间段的开始时间不是00:00:00输出当日起点到该开始时间的区间。相邻间隙判断遍历所有相邻时间段若前一个的结束时间与后一个的开始时间不相等则输出中间的空闲区间。结尾空闲判断如果最后一个时间段的结束时间不是23:59:59输出该结束时间到当日终点的区间。格式化输出使用%02d控制输出保证不足两位时自动补前导零。注意事项时间比较必须严格按时、分、秒的顺序依次判断重载运算符时逻辑不能出错。输出格式必须严格补零例如5分3秒需输出为00:05:03。题目已保证区间不重叠无需处理区间交叉的情况仅需判断端点是否相等。L2-043 龙龙送外卖题目大意小区道路构成一棵树外卖站为根节点。每次新增一个送餐点求从外卖站出发访问所有已有的送餐点至少一次的最短路程送完餐后无需返回外卖站。核心考点树的深度优先搜索、树上路径结论推导、动态加点维护。解题思路本题有一个关键结论可以避免每次新增点都重新计算全树路径从根出发、访问指定节点且无需返回根的最短路 所有经过边的往返总长度 - 最远节点的深度。原理每条需要经过的边往返需要走2次最后不用返回根因此减去最深节点往回走的路程即该节点的深度。基于该结论只需动态维护两个值sum所有已访问边的往返总路程每新增一条未走过的边sum 2。mx所有送餐点中距离根节点的最大深度。每次新增送餐点时从该点向上遍历到根未标记的节点标记为已访问sum加2。更新最大深度mx max(mx, 当前点深度)。本次答案为sum - mx。正解代码#includebits/stdc.husingnamespacestd;constintN1e6;intn,m,root;inth[N],e[N],ne[N],idx,p[N],d[N];bools[N];voidadd(inta,intb){e[idx]b,ne[idx]h[a],h[a]idx;}voiddfs(intx){for(intih[x];i!-1;ine[i]){intje[i];d[j]d[x]1;dfs(j);}}/* 外卖站到所有地方的往返距离减去最远距离 不用回去 */intmain(){cinnm;memset(h,-1,sizeofh);for(inti1;in;i){cinp[i];if(p[i]-1)rooti;elseadd(p[i],i);}dfs(root);intmx0,sum0;while(m--){inta;cina;mxmax(mx,d[a]);while(!s[a]a!root){s[a]1;sum2;//往返ap[a];}coutsum-mx\n;}return0;}代码详解建树用邻接表存储树结构根据输入的父节点数组添加父节点到子节点的有向边。预处理深度从根节点出发DFS预处理出每个节点到根的深度d[]。标记数组s[]记录节点对应的边是否已经计入总路程避免重复计算。处理m次查询读入新增送餐点编号先更新全局最大深度。循环向上遍历父节点遇到未标记的节点则标记同时sum加2直到到达根节点。输出sum - mx作为本次结果。注意事项重复添加同一个送餐点时路径已被标记不会增加新的路程。根节点无需标记也不计入路程。本题所有边的长度均为1节点深度等于该节点到根的边数。L2-044 大众情人题目大意n个人分为男女两类人与人之间存在单向的距离感距离感可传递且取所有传递路径中的最小值即有向图最短路。一个人的异性缘定义为所有异性对他/她的距离感中的最大值由最无感的那个异性决定。异性缘越好该最大值越小。分别找出女性、男性中的“大众情人”异性缘最优的人若结果并列则按编号升序输出。核心考点有向图单源最短路、多源最短路、题意逻辑转换。解题思路题意转换“j眼中i的距离感”等价于有向图中 j → i 的最短路径长度。最短路计算以每个人为起点跑一遍单源最短路得到d[j][i]表示j到i的最短距离。统计异性缘对每个女性i遍历所有男性j取d[j][i]的最大值即为i的异性缘数值。对每个男性i遍历所有女性j取d[j][i]的最大值即为i的异性缘数值。结果筛选分别在女性、男性群体中找到异性缘数值最小的所有人按编号升序输出。正解代码#includebits/stdc.h#definepiipairint,intusingnamespacestd;constintM3e59,N510,inf1e9;intidx,d[N][N],sex[N];vectorpiig[N];intn,k;boolst[N];voiddijkstra(intstr){for(inti1;in;i){d[str][i]inf;st[i]0;}priority_queuepii,vectorpii,greaterpiiq;d[str][str]0;q.push({0,str});while(q.size()){auto[dd,a]q.top();q.pop();if(st[a])continue;st[a]1;for(auto[b,w]:g[a])if(d[str][b]ddw){d[str][b]ddw;q.push({ddw,b});}}}signedmain(){cinn;for(inti1;in;i){charc;cinck;if(cM)sex[i]1;for(intj0;jk;j){intb,w;cinbcw;g[i].push_back({b,w});}}for(inti1;in;i)dijkstra(i);vectorpiians1,ans2;for(inti1;in;i){//女if(sex[i])continue;intmx0;boolfd0;for(intj1;jn;j){//男if(!sex[j])continue;if(d[j][i]inf){mxinf;fd1;break;}mxmax(mx,d[j][i]);}ans1.push_back({mx,i});}for(inti1;in;i){//男if(!sex[i])continue;intmx0;boolfd0;for(intj1;jn;j){//女if(sex[j])continue;if(d[j][i]inf){mxinf;fd1;break;}mxmax(mx,d[j][i]);}ans2.push_back({mx,i});}sort(ans1.begin(),ans1.end());sort(ans2.begin(),ans2.end());intsz10,sz20;for(autoa1:ans1)if(a1.firstans1[0].first)sz1;elsebreak;for(autoa2:ans2)if(a2.firstans2[0].first)sz2;elsebreak;for(inti0;isz1;i){if(i)cout ;coutans1[i].second;}cout\n;for(inti0;isz2;i){if(i)cout ;coutans2[i].second;}return0;}代码详解建图用邻接表存储有向图边权为对应距离感。最短路实现本题n≤500使用堆优化Dijkstra对每个点跑一遍单源最短路时间复杂度可接受也可使用Floyd算法代码更简洁。异性缘统计遍历所有女性计算每个女性对应的男性最大距离存入女性结果列表。遍历所有男性计算每个男性对应的女性最大距离存入男性结果列表。排序与输出将结果按“距离从小到大编号从小到大”排序取出所有距离等于最小值的编号按格式输出。注意事项距离是单向的“j对i的距离感”是j到i的路径不是i到j方向不能搞反。异性缘取最大值由最无感的异性决定因此是取max而非min这是本题最容易出错的点。距离数组初始化要设为足够大的无穷值避免溢出和误判。并列结果必须按编号升序输出排序时第二关键字为编号。