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

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

文章目录

• • • L2-001 紧急救援
    • L2-002 链表去重
    • L2-003 月饼
    • L2-004 这是二叉搜索树吗？

---

L2-001 紧急救援

题目大意：给定n个城市和m条双向道路，每个城市有一定数量的救援队。从起点出发前往终点，在保证路径总长度最短的前提下，尽可能召集更多救援队。输出最短路径的条数、最多可召集的救援队数量，以及一条对应的最优路径。

核心思路：在Dijkstra单源最短路径算法的基础上扩展，额外维护三个数组：最短路径条数、到达该节点的最大救援队数量、路径前驱节点。松弛操作分情况更新：找到更短路径时重置计数与救援数；路径长度相等时累加路径数，若救援数更多则更新救援数与前驱。

算法步骤：

1. 初始化距离数组为无穷大，起点距离设为0；起点的救援队数量为自身救援队数，最短路径条数为1。
2. 循环n次，每次选出未访问的距离最小的节点，标记为已访问。
3. 用当前节点松弛所有邻接节点：
   • 若发现更短路径：更新最短距离，路径条数继承自当前节点，更新最大救援队数，记录前驱节点。
   • 若路径长度相等：路径条数累加；若新方案救援队数量更多，则更新最大救援数与前驱节点。
4. 从终点递归回溯前驱节点，正序输出完整路径。

正解代码

#include<bits/stdc++.h>usingnamespacestd;constintN=510;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(inti=0;i<n;i++){intt=-1;for(intj=0;j<n;j++){if(!st[j]&&(t==-1||d[t]>d[j]))t=j;}//if (t == -1) return;st[t]=1;for(intj=0;j<n;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(x==be){cout<<be<<' ';return;}pt(p[x]);cout<<x;if(x!=ed)cout<<' ';}//*/intmain(){cin>>n>>m>>be>>ed;memset(g,0x3f,sizeofg);for(inti=0;i<n;i++)cin>>a[i];while(m--){inta,b,c;cin>>a>>b>>c;g[a][b]=g[b][a]=c;}dijkstra();cout<<cnt[ed]<<' '<<ans[ed]<<'\n';pt(ed);return0;}

代码关键细节：

• 使用邻接矩阵存图，适配500以内的节点规模，初始化所有边权为无穷大。
• 路径输出采用递归回溯，先输出前驱再输出当前节点，保证路径正序。
• 题目保证最优解唯一，最大救援队对应的前驱路径是确定的。

L2-002 链表去重

题目大意：给定一个链表，按遍历顺序删除键值绝对值重复的节点，仅保留第一个出现的节点。被删除的节点按原顺序组成另一个链表，分别输出去重后的链表和被删除的链表。

核心思路：用数组模拟链表存储全部节点，通过地址建立下标映射实现O(1)查找。从头节点顺序遍历链表，用布尔数组标记已出现的绝对值，首次出现归入保留链表，重复的归入删除链表，最后按格式分别输出。

算法步骤：

1. 读取所有节点信息，建立「地址→数组下标」的映射，方便快速定位节点。
2. 从头节点开始顺序遍历：
   • 当前节点键值的绝对值未标记时，标记为已出现，加入保留链表。
   • 已标记时，加入删除链表。
3. 按格式输出两个链表，每个节点输出地址、键值、下一个节点地址，末尾节点的下一地址为-1。

正解代码

#include<bits/stdc++.h>usingnamespacestd;constintN=1e5+9;intn,head,a[N];//节点下标bools[N];structnode{intid,x,nt;//节点地址 键值 next地址}g[N];vector<node>v;intmain(){cin>>head>>n;for(inti=0;i<n;i++){cin>>g[i].id>>g[i].x>>g[i].nt;a[g[i].id]=i;}intnow=head;while(now!=-1){intj=a[now];if(!s[abs(g[j].x)]){s[abs(g[j].x)]=1;if(now==head)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]);now=g[j].nt;}cout<<"-1\n";for(inti=0;i<v.size();i++){if(i==0)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种月饼的库存量和总售价，以及市场最大需求量，月饼可拆分销售，求能获得的最大收益。

核心思路：典型的分数背包问题，使用贪心策略。先计算每种月饼的单位售价，优先选择单价最高的月饼出售，直到满足市场需求量。

算法步骤：

1. 读取每种月饼的库存量与总售价，计算单价（总售价/库存量）。
2. 按单价从高到低对所有月饼排序。
3. 依次遍历排序后的月饼：
   • 剩余需求量大于等于当前库存量时，全部卖出，累加总售价，扣减对应需求量。
   • 剩余需求量不足时，按比例卖出部分月饼，累加收益后结束循环。
4. 按两位小数格式输出最终收益。

正解代码

#include<bits/stdc++.h>usingnamespacestd;constintN=1010;structItem{doublevalue;// 价值doubleweight;// 重量doubleratio;// 价值重量比};intn,m;// n:物品数量, m:背包容量Item items[N];boolcmp(constItem&a,constItem&b){returna.ratio>b.ratio;// 按价值比降序排列}intmain(){cin>>n>>m;// 输入重量和价值for(inti=0;i<n;i++)cin>>items[i].weight;for(inti=0;i<n;i++)cin>>items[i].value;// 计算价值重量比for(inti=0;i<n;i++){items[i].ratio=items[i].value/items[i].weight;}// 按价值比降序排序sort(items,items+n,cmp);doubleans=0;intremaining=m;for(inti=0;i<n&&remaining>0;i++){if(remaining>=items[i].weight){// 可以装下整个物品ans+=items[i].value;remaining-=items[i].weight;}else{// 只能装下一部分ans+=items[i].ratio*remaining;remaining=0;}}printf("%.2f",ans);return0;}

代码关键细节：

• 相关变量统一使用double类型，避免整数除法造成精度丢失。
• 循环终止条件为剩余需求量为0，或所有月饼遍历完毕。
• 输出使用%.2f格式化，严格保留两位小数。

L2-004 这是二叉搜索树吗？

题目大意：给定一个整数序列，判断它是否是一棵二叉搜索树或其镜像树的前序遍历结果。如果是则输出 YES 并给出对应的后序遍历序列，否则输出 NO。其中二叉搜索树定义为左子树所有节点值小于根，右子树所有节点值大于等于根。

核心思路：利用二叉搜索树前序遍历「根-左-右」的性质递归验证，同时在递归过程中记录后序遍历结果。分别对正常二叉搜索树和镜像二叉搜索树各做一次校验，只要其中一种成立即可输出答案。

算法步骤：

1. 定义两个校验函数ck1（正常BST）和ck2（镜像BST），传入当前序列的左右区间[l,r]。
2. 取区间首元素作为当前子树的根节点x。
3. 正常BST：从左向右找到第一个不小于x的位置，划分出左子树区间；再检查剩余区间是否全部大于等于x，若右边界能到达r则结构合法。
4. 镜像BST：逻辑相反，左子树全部大于等于x，右子树全部小于x。
5. 递归校验左右子树，递归返回后将根节点存入后序数组，天然形成后序遍历顺序。
6. 主函数先调用ck1，成功则输出后序结果；失败再调用ck2，均失败则输出 NO。

正解代码

#include<bits/stdc++.h>usingnamespacestd;constintN=1001;intn,pre[N],suf1[N],pos1=0,suf2[N],pos2=0;boolck1(intl,intr){if(l>r)return1;intx=pre[l];inti=l+1,j;while(pre[i]<x&&i<=r)i++;i--;//左子树右端点j=i+1;while(pre[j]>=x&&j<=r)j++;j--;//右子树右端点if(j!=r)return0;boolfg=ck1(l+1,i)&&ck1(i+1,r);suf1[pos1++]=x;// 后序遍历returnfg;}boolck2(intl,intr){if(l>r)return1;intx=pre[l];inti=l+1,j;while(pre[i]>=x&&i<=r)i++;i--;//左子树右端点j=i+1;while(pre[j]<x&&j<=r)j++;j--;//右子树右端点if(j!=r)return0;boolfg=ck2(l+1,i)&&ck2(i+1,r);suf2[pos2++]=x;// 后序遍历returnfg;}intmain(){cin>>n;for(inti=0;i<n;i++)cin>>pre[i];if(ck1(0,n-1)){cout<<"YES\n";for(inti=0;i<n;i++){if(i)cout<<' ';cout<<suf1[i];}}elseif(ck2(0,n-1)){cout<<"YES\n";for(inti=0;i<n;i++){if(i)cout<<' ';cout<<suf2[i];}}elsecout<<"NO";return0;}

代码关键细节：

• 左子树右端点计算：循环找到第一个不满足条件的下标后，需要减 1 才是左子树的最后一个位置。
• 后序数组使用全局下标累加，递归结束时存入根节点，保证左右子树都处理完再记录根。
• 边界条件l > r时返回true，空树视为合法二叉搜索树。