官网https://pintia.cn/problem-sets/994805046380707840/exam/problems/type/7文章目录L2-001 紧急救援L2-002 链表去重L2-003 月饼L2-004 这是二叉搜索树吗L2-001 紧急救援题目大意给定n个城市和m条双向道路每个城市有一定数量的救援队。从起点出发前往终点在保证路径总长度最短的前提下尽可能召集更多救援队。输出最短路径的条数、最多可召集的救援队数量以及一条对应的最优路径。核心思路在Dijkstra单源最短路径算法的基础上扩展额外维护三个数组最短路径条数、到达该节点的最大救援队数量、路径前驱节点。松弛操作分情况更新找到更短路径时重置计数与救援数路径长度相等时累加路径数若救援数更多则更新救援数与前驱。算法步骤初始化距离数组为无穷大起点距离设为0起点的救援队数量为自身救援队数最短路径条数为1。循环n次每次选出未访问的距离最小的节点标记为已访问。用当前节点松弛所有邻接节点若发现更短路径更新最短距离路径条数继承自当前节点更新最大救援队数记录前驱节点。若路径长度相等路径条数累加若新方案救援队数量更多则更新最大救援数与前驱节点。从终点递归回溯前驱节点正序输出完整路径。正解代码#includebits/stdc.husingnamespacestd;constintN510;intn,t,m,be,ed,d[N],ans[N],a[N],p[N],cnt[N];// p 父节点 ansi 到i的最大救援人数 cnti 到i的最短路径条数boolst[N];intg[N][N];voiddijkstra(){//初始化memset(d,0x3f,sizeofd);d[be]0;ans[be]a[be];cnt[be]1;for(inti0;in;i){intt-1;for(intj0;jn;j){if(!st[j](t-1||d[t]d[j]))tj;}//if (t -1) return;st[t]1;for(intj0;jn;j){if(d[j]d[t]g[t][j]){d[j]d[t]g[t][j];ans[j]ans[t]a[j];cnt[j]cnt[t];p[j]t;}elseif(d[j]d[t]g[t][j]){cnt[j]cnt[t];if(ans[j]ans[t]a[j]){ans[j]ans[t]a[j];p[j]t;}}}}}///*voidpt(intx){if(xbe){coutbe ;return;}pt(p[x]);coutx;if(x!ed)cout ;}//*/intmain(){cinnmbeed;memset(g,0x3f,sizeofg);for(inti0;in;i)cina[i];while(m--){inta,b,c;cinabc;g[a][b]g[b][a]c;}dijkstra();coutcnt[ed] ans[ed]\n;pt(ed);return0;}代码关键细节使用邻接矩阵存图适配500以内的节点规模初始化所有边权为无穷大。路径输出采用递归回溯先输出前驱再输出当前节点保证路径正序。题目保证最优解唯一最大救援队对应的前驱路径是确定的。L2-002 链表去重题目大意给定一个链表按遍历顺序删除键值绝对值重复的节点仅保留第一个出现的节点。被删除的节点按原顺序组成另一个链表分别输出去重后的链表和被删除的链表。核心思路用数组模拟链表存储全部节点通过地址建立下标映射实现O(1)查找。从头节点顺序遍历链表用布尔数组标记已出现的绝对值首次出现归入保留链表重复的归入删除链表最后按格式分别输出。算法步骤读取所有节点信息建立「地址→数组下标」的映射方便快速定位节点。从头节点开始顺序遍历当前节点键值的绝对值未标记时标记为已出现加入保留链表。已标记时加入删除链表。按格式输出两个链表每个节点输出地址、键值、下一个节点地址末尾节点的下一地址为-1。正解代码#includebits/stdc.husingnamespacestd;constintN1e59;intn,head,a[N];//节点下标bools[N];structnode{intid,x,nt;//节点地址 键值 next地址}g[N];vectornodev;intmain(){cinheadn;for(inti0;in;i){cing[i].idg[i].xg[i].nt;a[g[i].id]i;}intnowhead;while(now!-1){intja[now];if(!s[abs(g[j].x)]){s[abs(g[j].x)]1;if(nowhead)printf(%05d %d ,head,g[j].x);elseprintf(%05d\n%05d %d ,g[j].id,g[j].id,g[j].x);}elsev.push_back(g[j]);nowg[j].nt;}cout-1\n;for(inti0;iv.size();i){if(i0)printf(%05d %d ,v[i].id,v[i].x);elseprintf(%05d\n%05d %d ,v[i].id,v[i].id,v[i].x);}if(v.size())cout-1\n;return0;}代码关键细节地址为5位整数输出必须用%05d补前导零-1直接原样输出。输出时保证链表逻辑连贯上一节点的下一地址即为下一节点的地址。删除链表可能为空此时不需要输出删除链表部分。L2-003 月饼题目大意给定n种月饼的库存量和总售价以及市场最大需求量月饼可拆分销售求能获得的最大收益。核心思路典型的分数背包问题使用贪心策略。先计算每种月饼的单位售价优先选择单价最高的月饼出售直到满足市场需求量。算法步骤读取每种月饼的库存量与总售价计算单价总售价/库存量。按单价从高到低对所有月饼排序。依次遍历排序后的月饼剩余需求量大于等于当前库存量时全部卖出累加总售价扣减对应需求量。剩余需求量不足时按比例卖出部分月饼累加收益后结束循环。按两位小数格式输出最终收益。正解代码#includebits/stdc.husingnamespacestd;constintN1010;structItem{doublevalue;// 价值doubleweight;// 重量doubleratio;// 价值重量比};intn,m;// n:物品数量, m:背包容量Item items[N];boolcmp(constItema,constItemb){returna.ratiob.ratio;// 按价值比降序排列}intmain(){cinnm;// 输入重量和价值for(inti0;in;i)cinitems[i].weight;for(inti0;in;i)cinitems[i].value;// 计算价值重量比for(inti0;in;i){items[i].ratioitems[i].value/items[i].weight;}// 按价值比降序排序sort(items,itemsn,cmp);doubleans0;intremainingm;for(inti0;inremaining0;i){if(remainingitems[i].weight){// 可以装下整个物品ansitems[i].value;remaining-items[i].weight;}else{// 只能装下一部分ansitems[i].ratio*remaining;remaining0;}}printf(%.2f,ans);return0;}代码关键细节相关变量统一使用double类型避免整数除法造成精度丢失。循环终止条件为剩余需求量为0或所有月饼遍历完毕。输出使用%.2f格式化严格保留两位小数。L2-004 这是二叉搜索树吗题目大意给定一个整数序列判断它是否是一棵二叉搜索树或其镜像树的前序遍历结果。如果是则输出 YES 并给出对应的后序遍历序列否则输出 NO。其中二叉搜索树定义为左子树所有节点值小于根右子树所有节点值大于等于根。核心思路利用二叉搜索树前序遍历「根-左-右」的性质递归验证同时在递归过程中记录后序遍历结果。分别对正常二叉搜索树和镜像二叉搜索树各做一次校验只要其中一种成立即可输出答案。算法步骤定义两个校验函数ck1正常BST和ck2镜像BST传入当前序列的左右区间[l,r]。取区间首元素作为当前子树的根节点x。正常BST从左向右找到第一个不小于x的位置划分出左子树区间再检查剩余区间是否全部大于等于x若右边界能到达r则结构合法。镜像BST逻辑相反左子树全部大于等于x右子树全部小于x。递归校验左右子树递归返回后将根节点存入后序数组天然形成后序遍历顺序。主函数先调用ck1成功则输出后序结果失败再调用ck2均失败则输出 NO。正解代码#includebits/stdc.husingnamespacestd;constintN1001;intn,pre[N],suf1[N],pos10,suf2[N],pos20;boolck1(intl,intr){if(lr)return1;intxpre[l];intil1,j;while(pre[i]xir)i;i--;//左子树右端点ji1;while(pre[j]xjr)j;j--;//右子树右端点if(j!r)return0;boolfgck1(l1,i)ck1(i1,r);suf1[pos1]x;// 后序遍历returnfg;}boolck2(intl,intr){if(lr)return1;intxpre[l];intil1,j;while(pre[i]xir)i;i--;//左子树右端点ji1;while(pre[j]xjr)j;j--;//右子树右端点if(j!r)return0;boolfgck2(l1,i)ck2(i1,r);suf2[pos2]x;// 后序遍历returnfg;}intmain(){cinn;for(inti0;in;i)cinpre[i];if(ck1(0,n-1)){coutYES\n;for(inti0;in;i){if(i)cout ;coutsuf1[i];}}elseif(ck2(0,n-1)){coutYES\n;for(inti0;in;i){if(i)cout ;coutsuf2[i];}}elsecoutNO;return0;}代码关键细节左子树右端点计算循环找到第一个不满足条件的下标后需要减 1 才是左子树的最后一个位置。后序数组使用全局下标累加递归结束时存入根节点保证左右子树都处理完再记录根。边界条件l r时返回true空树视为合法二叉搜索树。