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

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

文章目录

• • • L2-009 抢红包
    • L2-010 排座位
    • L2-011 玩转二叉树
    • L2-012 关于堆的判断

---

L2-009 抢红包

题目大意：给定N个人的发红包记录，每条记录包含发红包个数、抢到者编号和对应金额。统计每个人的净收入（抢到总金额 - 发出总金额），按净收入从高到低排序输出；收入并列则按抢到红包个数降序，仍并列则按个人编号升序。输入金额以分为单位，输出以元为单位保留两位小数。

解题思路：

1. 定义结构体存储每个人的编号、净收入、抢到红包的次数。
2. 遍历每条发红包记录：对每个抢到红包的人，累加其收入和抢包次数；同时累计当前发红包者的总发出金额，从其净收入中扣除。
3. 自定义三级排序规则：优先按净收入降序，其次按抢包次数降序，最后按编号升序。
4. 排序后格式化输出，完成分转元的单位换算。

正解代码

#include<bits/stdc++.h>usingnamespacestd;structpo{doubleq;intcnt,id;booloperator<(constpo p)const{if(q!=p.q)returnq>p.q;if(cnt!=p.cnt)returncnt>p.cnt;returnid<p.id;}};intmain(){intn;cin>>n;vector<po>p(n+1);for(inti=1;i<=n;i++){p[i].id=i,p[i].q=0,p[i].cnt=0;}for(inti=1;i<=n;i++){intk,sum=0;cin>>k;for(intj=0;j<k;j++){intmoy,m;cin>>m>>moy;sum+=moy;p[m].cnt++;p[m].q+=moy*0.01;}p[i].q-=sum*0.01;}vector<po>result;for(inti=1;i<=n;i++){result.push_back(p[i]);}sort(result.begin(),result.end());for(inti=0;i<n;i++){printf("%d %.2f\n",result[i].id,result[i].q);}return0;}

代码解析：

• 结构体po包含净收入q、抢包次数cnt、编号id，重载<运算符实现题目要求的排序优先级。
• 外层循环遍历每个发红包的人，内层循环处理每个红包接收者，累加接收者收入，最后统一扣除发红包者的总支出。
• 将所有人存入结果数组后调用sort排序，用printf控制两位小数输出。

---

L2-010 排座位

题目大意：宾客间存在朋友和死对头两种关系，朋友关系具有传递性，敌对关系仅直接生效。对每组查询，根据两人关系输出对应结果：是朋友且不敌对输出No problem；非朋友也不敌对输出OK；敌对但有共同朋友输出OK but...；仅敌对无共同朋友输出No way。

解题思路：

1. 朋友关系：用并查集维护，合并所有朋友对，通过根节点判断两人是否属于同一个朋友圈子。
2. 敌对关系：用二维布尔数组存储直接敌对关系，仅记录直接的死对头。
3. 查询时分四种情况判断：
   • 同根（是朋友/有共同朋友）且不敌对 → No problem
   • 不同根且不敌对 → OK
   • 同根且敌对 → OK but…
   • 不同根且敌对 → No way

正解代码

#include<bits/stdc++.h>usingnamespacestd;intn,m,k,p[110];intfind(intx){if(p[x]!=x)p[x]=find(p[x]);returnp[x];}bools[110][110];intmain(){cin>>n>>m>>k;for(inti=1;i<=n;i++)p[i]=i;for(inti=0;i<m;i++){inta,b,c;cin>>a>>b>>c;if(c==-1)s[a][b]=s[b][a]=1;intaa=find(a),bb=find(b);if(c==1)p[aa]=bb;}for(inti=0;i<k;i++){inta,b;cin>>a>>b;intaa=find(a),bb=find(b);if(aa==bb&&!s[a][b])cout<<"No problem";elseif(aa!=bb&&!s[a][b])cout<<"OK";elseif(aa==bb&&s[a][b])cout<<"OK but...";elseif(aa!=bb&&s[a][b])cout<<"No way";else;cout<<'\n';}return0;}

代码解析：

• 并查集数组p维护朋友连通性，find函数带路径压缩优化查询效率。
• 二维数组s标记敌对关系，双向赋值保证无向性。
• 读取关系时，朋友关系执行合并操作，敌对关系标记数组对应位置。
• 查询时先求两人的根节点，结合敌对标记按四个分支输出对应结果。

---

L2-011 玩转二叉树

题目大意：给定二叉树的中序遍历和前序遍历序列，先对二叉树做镜面反转（所有非叶节点的左右孩子互换），再输出反转后的层序遍历序列。

解题思路：

1. 建树：根据前序遍历确定根节点，在中序遍历中定位根节点，将序列划分为左子树和右子树，递归构建整棵二叉树。
2. 镜面反转的层序遍历：无需真正修改树结构，在层序遍历时优先将右孩子入队，再将左孩子入队，输出顺序即为镜面反转后的层序结果。
3. 使用队列实现广度优先搜索，完成层序遍历。

正解代码

#include<bits/stdc++.h>usingnamespacestd;constintN=1e5+9;intn,m,t,k,x,y;intsuf[49],in[49];structnd{intval;nd*lef=NULL;nd*rig=NULL;};nd*build(intil,intir,intsl,intsr){if(il>ir)returnNULL;introot=suf[sr];nd*p=newnd;p->val=root;if(il==ir)returnp;intpos=il;while(in[pos]!=root)pos++;intlen=pos-1-il+1;p->lef=build(il,pos-1,sl,sl+len-1);p->rig=build(pos+1,ir,sl+len,sr-1);returnp;}queue<nd*>q;intmain(){cin>>n;for(inti=0;i<n;i++)cin>>suf[i];for(inti=0;i<n;i++)cin>>in[i];introot=suf[n-1];nd*head=newnd;head=build(0,n-1,0,n-1);q.push(head);while(q.size()){autont=q.front();q.pop();if(nt->val!=root)cout<<" ";cout<<nt->val;if(NULL!=nt->lef)q.push(nt->lef);if(NULL!=nt->rig)q.push(nt->rig);}return0;}

代码解析：

• build函数接收前序、中序的左右边界，递归构建二叉树：前序首元素为根节点，在中序中找到根位置，计算左子树长度，分别递归构建左右子树。
• 层序遍历从根节点入队开始，每次取出队首节点输出值，先入队右孩子，再入队左孩子，等价于完成镜面反转。
• 输出时控制空格，保证行首行尾无多余空格。

---

L2-012 关于堆的判断

题目大意：将给定数字按顺序插入初始为空的小顶堆，随后判断多条命题，包括根节点判断、兄弟节点判断、父子节点判断，命题为真输出T，否则输出F。

解题思路：

1. 建小顶堆：数组模拟堆，下标从1开始。逐个插入元素，执行向上调整操作：若当前节点值小于父节点，则交换，继续向上调整直到满足小顶堆性质。
2. 节点定位：每次查询时遍历堆数组，找到对应值的下标；也可提前建立值到下标的映射。
3. 命题处理：读取每行命题，通过关键词判断命题类型，提取节点值并转换为下标，再根据堆的父子下标规则判断真假。

正解代码

#include<bits/stdc++.h>usingnamespacestd;constintN=10010;intf[N],hs[N],n,s[N],p[N];//父节点 房子数 面积数 人数structfmy{intid,cntp,cnts,cnths;doubleperhs,pers;booloperator<(fmy fam)const{if(pers!=fam.pers)returnpers>fam.pers;returnid<fam.id;}};vector<fmy>v;vector<int>ff[N];//先读入完再合并intfind(intx){if(f[x]!=x)f[x]=find(f[x]);returnf[x];}voidhebing(inta,intb){intaa=find(a),bb=find(b);if(aa>bb)swap(aa,bb);if(aa==bb)return;f[bb]=aa;//小的为家庭代表// 这里不合并财产，等所有关系建立后再合并hs[aa]+=hs[bb];s[aa]+=s[bb];p[aa]+=p[bb];}intmain(){cin>>n;for(inti=0;i<N;i++)f[i]=i;//初始化intid,dad,mom,cnt;for(inti=0;i<n;i++){cin>>id>>dad>>mom>>cnt;intkid;// 标记存在的节点并初始化人数p[id]=1;if(dad!=-1){ff[id].push_back(dad);p[dad]=1;}if(mom!=-1){ff[id].push_back(mom);p[mom]=1;}for(intj=0;j<cnt;j++){cin>>kid;ff[id].push_back(kid);p[kid]=1;}cin>>hs[id]>>s[id];}// 先建立所有关系for(inti=0;i<10000;i++)for(intj=0;j<ff[i].size();j++)hebing(i,ff[i][j]);for(inti=0;i<10000;i++)if(p[i]>0&&i==find(i)){// 存在且是根节点v.push_back({i,p[i],s[i],hs[i],1.0*hs[i]/p[i],1.0*s[i]/p[i]});}sort(v.begin(),v.end());cout<<v.size()<<'\n';for(inti=0;i<v.size();i++)printf("%04d %d %.3f %.3f\n",v[i].id,v[i].cntp,v[i].perhs,v[i].pers);return0;}

代码解析：

• up函数实现向上调整，递归比较当前节点与父节点，不满足小顶堆则交换位置。
• 使用string::find识别命题类型，sscanf从字符串中提取数值，简化字符串解析。
• 兄弟节点判断：两个节点的父节点下标相同（i/2 == j/2）。
• 父子节点判断：子节点下标除以2等于父节点下标。
• 根节点判断：节点值等于堆数组第1位元素。