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

官网https://pintia.cn/problem-sets/994805046380707840/exam/problems/type/7文章目录L2-033 简单计算器L2-034 口罩发放L2-035 完全二叉树的层序遍历L2-036 网红点打卡攻略L2-033 简单计算器题目大意使用数字栈和运算符栈两个栈实现简易计算器将输入的数字和运算符按顺序分别压入对应栈中随后循环执行「弹出两个数字 弹出一个运算符 → 计算 → 结果压回数字栈」的流程直到数字栈仅剩一个元素即为最终计算结果。除法仅保留整数部分若出现除数为零的非法操作输出指定错误信息并直接结束程序。解题思路定义两个栈分别存储整数数字和字符型运算符。按输入顺序将所有数字压入数字栈将所有运算符压入运算符栈。循环执行计算当数字栈大小大于 1 时依次弹出栈顶两个数字n1、n2弹出栈顶运算符op。按n2 op n1的规则计算栈是后进先出结构先弹出的是右操作数后弹出的是左操作数减法和除法需特别注意顺序。除法特判若右操作数n1为 0按格式输出错误信息并直接终止程序。将计算结果压回数字栈循环结束后输出数字栈的栈顶元素。核心注意点运算顺序是本题最易错点必须严格遵循「后弹出的数 运算符 先弹出的数」。题目要求只取整数部分C 内置整数除法向零取整的特性正好符合要求。运算符总数为n-1与数字数量天然匹配循环终止条件为数字栈长度为 1。参考代码#includebits/stdc.h#defineintlonglongusingnamespacestd;signedmain(){intn,t;cinn;stackints1;// 数字栈stackchars2;// 运算符栈for(inti0;in;i){cint;s1.push(t);}for(inti1;in;i){charc;cinc;s2.push(c);}while(s1.size()1){intn1s1.top();s1.pop();intn2s1.top();s1.pop();charops2.top();s2.pop();if(op)s1.push(n1n2);if(op-)s1.push(n2-n1);if(op*)s1.push(n1*n2);if(op/){if(n10){coutERROR: n2/0;return0;}s1.push(n2/n1);}}couts1.top();return0;}L2-034 口罩发放题目大意处理连续 D 天的口罩申请数据每天有 T 条申请、S 个发放名额。发放规则① 身份证必须是 18 位纯数字② 同一人两次成功领取至少间隔 P 天③ 按提交时间先后发放时间相同时按输入顺序排序同一天每人最多领取一次。最终还需按首次出现顺序输出所有身份证合法且身体状况为 1 的人员名单。解题思路结构体设计定义申请记录结构体存储姓名、身份证号、身体状况、提交时间转换为分钟数便于比较、当天输入顺序。身份证校验函数判断字符串长度是否为 18且每一位都是数字。全局数据维护用哈希表记录每个人最后一次成功领取的天数用于校验领取间隔。用列表去重集合维护身体状况为 1 的人员保证按首次出现顺序输出且不重复。每日处理流程读入当天所有申请记录先遍历一遍将身份证合法且身体不适的人员加入全局统计列表。筛选出身份证合法、满足领取间隔的候选记录。按「提交时间升序 → 输入顺序升序」对候选记录排序。按顺序发放口罩名额用完即停止用当日去重集合避免同一人当天多次领取同时更新全局最后领取天数。全部天数处理完毕后遍历输出身体不适人员列表。核心注意点身体状况统计与是否成功领取无关只要身份证合法且身体状况为 1 就需要记录。间隔判断规则第day天领取后第day1到第dayP天都不可再次领取判断条件为day - 上次领取天数 P则不符合要求。同一天内同一人提交多条申请也只能领取一次必须做当日去重。时间转换为分钟数后整数比较比字符串比较更高效且不易出错。参考代码#includebits/stdc.husingnamespacestd;// 检查身份证号是否为18位数字boolck(conststrings){if(s.size()!18)returnfalse;for(charc:s)if(c0||c9)returnfalse;returntrue;}structnd{string nam,sfz;intop,tim,id;booloperator(constndn1)const{if(tim!n1.tim)returntimn1.tim;returnidn1.id;}};intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intD,P;cinDP;mapstring,intlast;// 每人最后一次成功领取的天数vectorpairstring,stringres;// 最终身体不适的人按首次出现顺序unordered_setstringseen;// 去重辅助for(intday1;dayD;day){intT,S;cinTS;vectorndtmp;// 当天符合条件的申请// 先读入当天所有申请同时收集身体不适的人for(inti0;iT;i){string name,sfz;intop,hh,ss;charcolon;cinnamesfzophhcolonss;if(!ck(sfz))continue;// 身份证不合法忽略// 记录身体不适的人合法身份证且 op1if(op1!seen.count(sfz)){seen.insert(sfz);res.emplace_back(name,sfz);}// 间隔检查如果上次成功领取过且间隔不足 P 天则不能申请autoitlast.find(sfz);if(it!last.end()day-it-secondP)continue;tmp.push_back({name,sfz,op,hh*60ss,i});}// 按时间和输入顺序排序sort(tmp.begin(),tmp.end());// 发放口罩unordered_setstringtoday;// 当天已领取的人避免同一天重复intcnt0;for(constautot:tmp){if(cntS)break;if(today.count(t.sfz))continue;// 同一天已领过today.insert(t.sfz);last[t.sfz]day;// 更新最后成功领取日期cnt;coutt.nam t.sfz\n;}}// 输出所有身体不适的人按首次出现顺序for(constautop:res){coutp.first p.second\n;}return0;}L2-035 完全二叉树的层序遍历题目大意给定一棵包含 n 个节点的完全二叉树的后序遍历序列要求输出该树的层序遍历序列。解题思路本题核心利用完全二叉树的编号性质若根节点编号为 1则任意节点 i 的左孩子编号为2*i右孩子编号为2*i1而层序遍历的结果恰好就是按节点编号 1~n 依次输出的值。用数组ans按节点编号存储节点值最终直接按顺序输出即为层序遍历。按照后序遍历「左子树 → 右子树 → 根节点」的顺序递归填充数组递归终止条件当前节点编号 n说明不存在该节点。先递归处理左孩子再递归处理右孩子最后给当前节点赋值。用指针p记录后序遍历数组的当前位置每访问一个根节点就将后序序列的第 p 个值赋给对应编号的节点指针后移。最后按 1~n 的顺序输出数组即为层序遍历结果。核心注意点无需真正构建二叉树利用完全二叉树的编号特性是本题最优解代码简洁且不易出错。赋值顺序必须严格遵循后序遍历的「左-右-根」才能和输入的后序序列一一对应。递归边界是节点编号超过总节点数 n此时说明该位置没有节点直接返回。参考代码#includebits/stdc.husingnamespacestd;intans[40],pos[40],p1,n;voiddfs(intnow){if(nown)return;// 超出节点数递归终止dfs(now*2);// 遍历左子树dfs(now*21);// 遍历右子树ans[now]pos[p];// 给根节点赋值}intmain(){cinn;for(inti1;in;i)cinpos[i];dfs(1);for(inti1;in;i){if(i1)cout ;coutans[i];}return0;}L2-036 网红点打卡攻略题目大意给定 n 个网红点和 m 条双向通路包含家编号0到景点的通路以及 k 条打卡攻略。需要判断每条攻略是否有效必须恰好打卡所有 n 个网红点每个点仅去一次路径上每一段家→第一个点、相邻景点、最后一个点→家都必须存在通路。统计有效攻略的总数并输出总花费最少的攻略序号和总花费花费相同时选择序号更小的攻略。解题思路建图存储使用邻接矩阵存储两点之间的旅行花费初始化为无穷大输入双向边时同步更新两个方向的花费。逐条校验攻略初始化起点为家编号 0总花费为 0用访问数组标记景点是否已打卡。遍历攻略中的每个景点若已访问过则重复打卡攻略无效若当前点到该景点无路攻略无效否则累加花费更新当前位置标记已访问。遍历完所有景点后额外检查① 景点数量必须恰好等于 n② 最后一个景点到家的路必须存在。维护最优解统计有效攻略数量同时维护最小花费和对应的攻略序号仅当花费严格更小时才更新保证花费相同时序号小的优先。核心注意点有效攻略有两个必要前提景点数恰好为 n不能多也不能少、全程每一段路都连通缺一不可。邻接矩阵初始化需使用足够大的无穷值如0x3f3f3f3f避免累加后溢出。题目保证至少存在一个有效攻略无需处理无有效攻略的边界情况。序号从 1 开始计数更新最优解时注意下标对应。参考代码#includebits/stdc.husingnamespacestd;constintN210;intd[N][N];boolvis[N];intmain(){intn,m;cinnm;memset(d,0x3f,sizeofd);for(inti0;im;i){inta,b,c;cinabc;d[a][b]d[b][a]c;}intk;cink;intmi1e99,ans0,num0;for(inti0;ik;i){intcnt;cincnt;memset(vis,0,sizeofvis);intu0,v,res0;boolfd0;// 标记是否无效for(intj0;jcnt;j){cinv;if(vis[v]){fd1;continue;}// 重复打卡vis[v]1;if(d[u][v]0x3f3f3f3f){fd1;continue;}// 无路resd[u][v];uv;}// 检查回家的路 景点数量是否足够if(d[u][0]0x3f3f3f3f||cntn)fd1;elseresd[u][0];if(!fd){num;if(resmi){mires;ansi1;}}}coutnum\n;coutans mi;return0;}