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

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

文章目录

• • • L2-021 点赞狂魔
    • L2-022 重排链表
    • L2-023 图着色问题
    • L2-024 部落

L2-021 点赞狂魔

题目大意：统计每个用户点赞的不同标签数量，选出数量最多的前3名作为“点赞狂魔”。若不同标签数量并列，则选择标签总个数更少（标签出现次数平均值更小）的用户。人数不足3时用-补齐。

解题思路：

正解代码

#include <bits/stdc++.h>
//#define int long long
using namespace std;
const int N=110;
int n;
string s;
struct no{
string id;
int num,ave;
bool operator <(const no n1)const{
if(num!=n1.num)return num>n1.num;
return ave<n1.ave;
}
}a[N];
signed main(){
cin>>n;
for(int i=0;i<n;i++){
cin>>a[i].id;
int k;
cin>>k;
set<int>s;
for(int j=0;j<k;j++){
int y;
cin>>y;
s.insert(y);
}
a[i].num=s.size();
a[i].ave=k;
}
sort(a,a+n);
int mm=min(3,n);
for(int i=0;i<mm;i++){

cout<<a[i].id;
if(i!=2)cout<<' ';
}
if(n<3)for(int i=0;i<3–n;i++){

cout<<"-";
if(i!=2–n)cout<<' ';
}

return 0;
}

代码解析：

• 定义结构体存储用户名、不同标签数num、标签总数ave（变量名实际表示总个数，用于间接比较平均值）。
• 重载<运算符实现自定义排序，保证排序后符合题目优先级。
• 输入时通过set去重，s.size()即为不同标签数量。
• 输出部分先输出前min(3,n)个用户名，再根据总人数补全-，同时控制行末无多余空格。

小技巧：

• 平均值 = 总标签数 / 不同标签数，当不同标签数相等时，总个数越小平均值越小，因此直接比较总个数即可，无需计算浮点数，避免精度问题。

L2-022 重排链表

题目大意：给定一个单链表 L₁→L₂→…→Lₙ，将其重新排列为 Lₙ→L₁→Lₙ₋₁→L₂→… 的形式，按指定格式输出重排后的链表。

解题思路：

正解代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+9;
struct node{
int id,x,next;
}l[N],ans[N];
map<int,int>mp;
int main(){
int head,n;
cin>>head>>n;
for(int i=0;i<n;i++){
cin>>l[i].id>>l[i].x>>l[i].next;
mp[l[i].id]=i;
}
int now=mp[head],count=0;
for(int i=0;i<n;i++){
ans[i]=l[now];
count++;
if(l[now].next==–1)break;
now=mp[l[now].next];
}
int le=0,ri=count–1;
int cnt=0;
printf("%05d %d ",ans[ri].id,ans[ri].x);
ri—;
while(le<=ri){
if(cnt&1){
printf("%05d\\n%05d %d ",ans[ri].id,ans[ri].id,ans[ri].x);
ri—;
cnt++;
}
else{
printf("%05d\\n%05d %d ",ans[le].id,ans[le].id,ans[le].x);
le++;
cnt++;
}
}
cout<<–1;

return 0;
}

代码解析：

• 用数组存储所有输入节点，通过map建立「地址→数组下标」的映射，方便快速通过地址定位节点。
• 从头结点开始遍历，将链表按顺序存入结果数组，同时统计有效节点总数。
• 双指针交替取节点，先取最右侧节点，再依次取左、右节点，完成重排。
• 使用printf("%05d")实现地址的5位补零格式，满足输出要求。

L2-023 图着色问题

题目大意：给定无向图和颜色数k，判断多组颜色分配方案是否为合法的图着色解：要求所有相邻顶点颜色不同，且恰好使用k种颜色。

解题思路：

正解代码

#include<bits/stdc++.h>
using namespace std;
const int N=521;
int n,m,k,a[N],t;
bool fd=0;
vector<pair<int,int>>g;
int main(){
cin>>n>>m>>t;
for(int i=0;i<m;i++){
int u,v;
cin>>u>>v;
g.push_back({u,v});
}
cin>>k;
while(k—){
map<int,int>mp;
for(int i=1;i<=n;i++){
cin>>a[i];
mp[a[i]]++;
}
fd=0;
for(auto [u,v]:g){
if(a[u]==a[v]){fd=1;break;}
}
if((int)mp.size()!=t)fd=1;
if(fd)cout<<"No";
else cout<<"Yes";
cout<<'\\n';
}

return 0;
}

代码解析：

• 用vector<pair<int,int>>存储所有边，单次检查的时间复杂度为O(m)，适配题目数据范围。
• 用map或set统计颜色种类数，校验是否恰好等于给定的颜色数。
• 用标记变量记录是否出现非法情况，一旦发现冲突可提前跳出循环，优化效率。

L2-024 部落

题目大意：给定多个小圈子，定义“朋友的朋友属于同一个部落”。要求统计社区总人数、互不相交的部落数量，并查询多对人员是否属于同一个部落。

解题思路：

• 标准并查集应用题，利用并查集维护人员的连通关系。

正解代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e4+9;
int p[N],t,x,q,k,n;
set<int>s1;
set<int>s2;
int find(int x){
if(p[x]!=x)p[x]=find(p[x]);
return p[x];
}
signed main(){
cin>>n;
for(int i=1;i<=N;i++)p[i]=i;
for(int i=0;i<n;i++){
int k,fi,y;
cin>>k>>fi;
s1.insert(fi);
int f1=find(fi);
for(int i=1;i<k;i++){
cin>>y;
int f2=find(y);
p[f2]=f1;
s1.insert(y);
}
}
cin>>q;
for(auto x:s1)s2.insert(find(x));
cout<<s1.size()<<' '<<s2.size()<<'\\n';
while(q—){
int a,b;
cin>>a>>b;
int f1=find(a);
int f2=find(b);
if(f1==f2)cout<<"Y\\n";
else cout<<"N\\n";

}

return 0;
}

代码解析：

• find函数实现路径压缩，大幅优化查询效率。
• 合并策略：将每个小圈子的后续成员都合并到第一个成员所在的集合中。
• 用第一个set存储所有出现过的人，其大小即为总人数；遍历该集合将所有根节点存入第二个set，其大小即为部落数量。
• 查询时调用两次find比较根节点，相同则输出Y，否则输出N。