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

官网https://pintia.cn/problem-sets/994805046380707840/exam/problems/type/7文章目录L2-005 集合相似度L2-006 树的遍历L2-007 家庭房产L2-008 最长对称子串L2-005 集合相似度题目大意给定 N 个整数集合每次查询两个集合计算它们的相似度。相似度公式为两个集合交集的不同元素个数 ÷ 并集的不同元素个数 × 100%结果保留两位小数。核心思路使用set自动去重存储每个集合查询时统计交集元素数量再通过「并集大小 两集合大小之和 - 交集大小」计算分母最终得到百分比结果。算法步骤读取 N 个集合每个集合的元素存入set自动去重按编号保存。读取 K 次查询每次取出两个集合。遍历其中一个集合的所有元素若该元素在另一个集合中存在则交集计数加 1。代入公式计算相似度按格式输出两位小数和百分号。正解代码#includebits/stdc.husingnamespacestd;constintN1e59;intn,m,t,k,x,y;mapint,setintmp;intmain(){cinn;for(inti1;in;i){cinm;setintse;for(intj0;jm;j){cinx;se.insert(x);}mp[i]se;}cink;for(inti0;ik;i){intx,y;cinxy;intnc0,nt0;ntmp[x].size()mp[y].size();for(autont:mp[x])if(mp[y].count(nt))nc;nt-nc;doubleansnc*100.0/nt;printf(%.2f\%\n,ans);}return0;}代码关键细节用vectorsetint或mapint, setint存储集合编号从 1 开始对应输入。遍历较小的集合可以减少循环次数本题数据范围不大直接遍历任一集合均可通过。输出使用printf(%.2f%%\n, ans)注意百分号需要转义。L2-006 树的遍历题目大意给定一棵二叉树的后序遍历和中序遍历序列输出该树的层序遍历序列节点值均为互不相同的正整数。核心思路递归构建二叉树。后序遍历的最后一个元素是根节点在中序序列中定位根节点位置即可划分出左右子树的中序区间再对应算出左右子树的后序区间递归完成建树。最后用BFS实现层序遍历。算法步骤分别存储后序遍历数组suf和中序遍历数组in。递归函数build(il, ir, sl, sr)il、ir是中序区间sl、sr是后序区间。取后序末尾元素suf[sr]作为根节点值在中序数组中找到根的下标pos。左子树长度len pos - il左子树中序区间为[il, pos-1]后序区间为[sl, sllen-1]。右子树中序区间为[pos1, ir]后序区间为[sllen, sr-1]。递归构建左右子树并返回根节点指针。使用队列进行 BFS 层序遍历依次出队输出节点值。正解代码#includebits/stdc.husingnamespacestd;constintN1e59;intn,m,t,k,x,y;intsuf[49],in[49];structnd{intval;nd*lefNULL;nd*rigNULL;};nd*build(intil,intir,intsl,intsr){if(ilir)returnNULL;introotsuf[sr];nd*pnewnd;p-valroot;if(ilir)returnp;intposil;while(in[pos]!root)pos;intlenpos-1-il1;p-lefbuild(il,pos-1,sl,sllen-1);p-rigbuild(pos1,ir,sllen,sr-1);returnp;}queuend*q;intmain(){cinn;for(inti0;in;i)cinsuf[i];for(inti0;in;i)cinin[i];introotsuf[n-1];nd*headnewnd;headbuild(0,n-1,0,n-1);q.push(head);while(q.size()){autontq.front();q.pop();if(nt-val!root)cout ;coutnt-val;if(NULL!nt-lef)q.push(nt-lef);if(NULL!nt-rig)q.push(nt-rig);}return0;}代码关键细节节点结构体包含节点值和左右孩子指针初始指针置为NULL。递归边界il ir时返回空指针il ir时直接返回叶子节点。层序输出时空格处理第一个元素前不输出空格后续元素前输出空格避免行尾多余空格。L2-007 家庭房产题目大意给定每个人的父母、子女信息以及名下房产套数和总面积按家庭统计人口数、人均房产套数和人均面积。结果按人均面积降序输出并列则按家庭最小编号升序。核心思路使用并查集维护家庭亲属关系合并集合时同步维护每个家庭的总人口、总房产套数和总面积。统一以小编号作为家庭代表最后收集所有家庭根节点并排序输出。算法步骤初始化并查集所有编号的父节点初始为自身人口数初始为 1。读取每条人员信息先暂存所有亲属关系同时标记所有出现过的有效编号。遍历所有有效编号将本人与父母、子女分别合并合并时始终让编号更小的作为根节点。合并过程中将房产套数、面积、人口数累加到根节点上。遍历 0~9999 所有编号找出满足「存在且是根节点」的家庭存入结果数组。按人均面积降序、最小编号升序的规则排序。按格式输出编号不足 4 位时前面补零。正解代码#includebits/stdc.husingnamespacestd;constintN10010;intf[N],hs[N],n,s[N],p[N];//父节点 房子数 面积数 人数structfmy{intid,cntp,cnts,cnths;doubleperhs,pers;booloperator(fmy fam)const{if(pers!fam.pers)returnpersfam.pers;returnidfam.id;}};vectorfmyv;vectorintff[N];//先读入完再合并intfind(intx){if(f[x]!x)f[x]find(f[x]);returnf[x];}voidhebing(inta,intb){intaafind(a),bbfind(b);if(aabb)swap(aa,bb);if(aabb)return;f[bb]aa;//小的为家庭代表// 这里不合并财产等所有关系建立后再合并hs[aa]hs[bb];s[aa]s[bb];p[aa]p[bb];}intmain(){cinn;for(inti0;iN;i)f[i]i;//初始化intid,dad,mom,cnt;for(inti0;in;i){ciniddadmomcnt;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(intj0;jcnt;j){cinkid;ff[id].push_back(kid);p[kid]1;}cinhs[id]s[id];}// 先建立所有关系for(inti0;i10000;i)for(intj0;jff[i].size();j)hebing(i,ff[i][j]);for(inti0;i10000;i)if(p[i]0ifind(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());coutv.size()\n;for(inti0;iv.size();i)printf(%04d %d %.3f %.3f\n,v[i].id,v[i].cntp,v[i].perhs,v[i].pers);return0;}代码关键细节用二维数组暂存亲属关系读完所有数据后再统一合并避免边读边合并不完整。并查集加入路径压缩优化提升查找效率。输出使用%04d格式化编号自动补前导零到 4 位。L2-008 最长对称子串题目大意给定一个字符串求其中最长的对称回文子串的长度。核心思路采用中心扩展法枚举每一个可能的回文中心向左右两端扩展直到字符不相等记录过程中的最大回文长度。回文分为奇数长度中心为单个字符和偶数长度中心为两个字符之间两种需分别处理。算法步骤遍历字符串每个位置i奇数长度回文以i为中心左右指针向两侧扩展统计回文长度。偶数长度回文以i与i1之间为中心左右指针向两侧扩展统计回文长度。每次扩展结束后更新全局最大回文长度。遍历完成后输出最大长度。正解代码#includebits/stdc.husingnamespacestd;intmain(){string s;getline(cin,s);intns.size();intans0;for(inti0;in;i){intli-1,ri1;while(l0rns[l]s[r]){l--;r;}l;r--;ansmax(ans,r-l1);li,ri1;while(l0rns[l]s[r]){l--;r;}l;r--;ansmax(ans,r-l1);}coutans;return0;}代码关键细节扩展循环结束后指针会多移动一步需要回退一位再计算长度。输入可能包含空格、特殊符号必须使用getline读取整行字符串。字符串长度不超过1000O(n²)的中心扩展法可稳定通过。