官网https://pintia.cn/problem-sets/994805046380707840/exam/problems/type/7文章目录L2-013 红色警报L2-014 列车调度L2-015 互评成绩L2-016 愿天下有情人都是失散多年的兄妹L2-013 红色警报题目大意给定城市间的通路网络城市会被逐个攻占。每失去一个城市判断其是否会导致剩余城市的连通区域数量增加即该城市是割点移除后网络分裂。若是则输出红色警报否则输出普通丢失提示所有城市都失陷后输出Game Over.。解题思路核心采用并查集维护连通性由于城市是逐步被删除的而并查集不支持删除操作因此采用每次删除后重建并查集的方式计算当前连通块数量。初始时计算完整图的连通块总数。每攻占一个城市就将所有与该城市相连的边标记为失效用剩余有效边重建并查集统计当前所有节点的连通块总数。判定规则若删除后连通块总数 删除前连通块总数 1说明该城市的移除导致原有连通区域分裂触发红色警报。该判定等价于剩余未失陷城市的连通块数量相比删除前有所增加。最后若攻占数等于城市总数额外输出Game Over.。正解代码#includebits/stdc.husingnamespacestd;constintN5200;intn,m,f[N],k;structnd{inta,b;boolfg0;}e[N];intfind(intx){if(f[x]!x)f[x]find(f[x]);returnf[x];}voidhb(inta,intb){intaafind(a),bbfind(b);f[aa]bb;}intmain(){cinnm;for(inti0;in;i)f[i]i;for(inti1;im;i){cine[i].ae[i].b;hb(e[i].a,e[i].b);}cink;intlost,cnt0,now0;for(inti0;in;i)if(f[i]i)cnt;//连通块数量for(inti0;ik;i){cinlost;now0;for(intj0;jn;j)f[j]j;for(intj1;jm;j){if(e[j].fg||e[j].alost||e[j].blost){e[j].fg1;continue;}hb(e[j].a,e[j].b);}for(intj0;jn;j)if(f[j]j)now;if(nowcnt1)printf(Red Alert: City %d is lost!\n,lost);elseprintf(City %d is lost.\n,lost);cntnow;}if(kn)coutGame Over.;return0;}代码解析结构体存储每条边的两个端点及失效标记攻占城市时将包含该城市的边标记为失效。find函数实现路径压缩的并查集查找hb函数实现合并操作。每次攻占城市后重置并查集数组仅用有效边合并节点统计根节点数量得到连通块总数。通过now cnt 1判断是否触发红色警报更新当前连通块数为下一次判定做准备。L2-014 列车调度题目大意列车按给定顺序驶入平行调度轨道要求最终从出口按序号递减顺序驶出求完成调度最少需要多少条平行轨道。解题思路问题可转化为经典的最长递增子序列问题将序列划分为最少的递减子序列其最少个数等于原序列的最长递增子序列长度。采用贪心二分的O(nlogn)算法求解最长递增子序列维护一个数组数组中每个元素表示对应长度递增子序列的最小末尾值。遍历每个列车序号若当前序号大于数组末尾元素直接追加到数组后否则找到数组中第一个大于当前序号的元素将其替换为当前序号。最终数组长度即为答案。正解代码#includebits/stdc.husingnamespacestd;constintN1e59;intf[N],n,p0;intmain(){cinn;intx;cinx;f[p]x;for(inti1;in;i){cinx;if(xf[p])f[p]x;else{intposupper_bound(f1,f1p,x)-f;f[pos]x;//将a[i]换为原f中第一个a[i]的数}}coutp;return0;}代码解析数组f维护递增子序列的末尾值p记录当前数组长度。使用upper_bound在有序数组中快速查找替换位置保证数组始终递增。替换操作的意义是让子序列末尾尽可能小为后续更大的数留出空间从而得到最长的递增子序列。L2-015 互评成绩题目大意每位学生有k个评审成绩去掉一个最高分和一个最低分后取平均值作为最终成绩。要求输出得分最高的M个成绩按非递减顺序排列保留3位小数。解题思路逐个读取每位学生的k个成绩同步累加总分、记录最高分和最低分。总分减去最高分和最低分除以(k-2)得到最终平均分存入结果数组。将所有平均分升序排序取最后M个即为得分最高的M个成绩按顺序格式化输出。正解代码#includebits/stdc.husingnamespacestd;intmain(){intn,m,k;cinnkm;vectordoublev;intx;doublesum;for(inti0;in;i){sum0;intmx-1,mi999;// 读取k个分数for(intj0;jk;j){cinx;sumx;mxmax(mx,x);mimin(mi,x);}// 去掉最高分和最低分计算平均sumsum-mx-mi;doubleavgsum*1.000/(k-2);// coutsum:sum avgendl;v.push_back(avg);}// 排序并输出前m个最高分sort(v.begin(),v.end());for(intin-m;in;i){printf(%.3f,v[i]);if(i!n-1)cout ;}return0;}代码解析遍历每个学生成绩时用变量mx和mi分别跟踪当前最高分和最低分无需排序即可快速得到极值效率更高。排序后数组下标n-m到n-1对应最高的M个成绩按顺序输出即满足非递减要求。使用printf(%.3f)控制输出格式保证三位小数精度。L2-016 愿天下有情人都是失散多年的兄妹题目大意判断一对异性是否可以通婚若两人五代以内本人、父母、祖父母、曾祖父母、高祖父母存在共同祖先则不可通婚同性直接输出Never Mind。解题思路预处理存储每个人的性别、父亲ID、母亲ID。对每对查询首先判断性别同性直接输出Never Mind。异性则先遍历第一个人的五代以内所有祖先用标记数组记录。再遍历第二个人的五代以内所有祖先若遇到已标记的节点说明存在共同祖先判定不可通婚。采用BFS逐层向上遍历祖先控制遍历层数为4代父母至高祖父母确保仅检查五代以内。正解代码#includebits/stdc.husingnamespacestd;constintN1e6;intf[N],m[N],s[N],n;boolst[N];intmain(){memset(f,-1,sizeoff);memset(m,-1,sizeofm);memset(s,-1,sizeofs);cinn;for(inti0;in;i){intid,fid,mid;charS;cinidSf[id]m[id];if(SM)s[id]1;elses[id]0;s[f[id]]1;s[m[id]]0;}intk;cink;while(k--){inta,b;cinab;if(s[a]s[b])coutNever Mind\n;else{boolfg0;memset(st,0,sizeofst);queueintq,qnext;q.push(a);for(inti0;i4;i){while(q.size()){autoidq.front();q.pop();if(f[id]!-1){qnext.push(f[id]);st[f[id]]1;}if(m[id]!-1){qnext.push(m[id]);st[m[id]]1;}}swap(q,qnext);}queueintq1,q1next;q1.push(b);for(inti0;i4;i){while(q1.size()){autoidq1.front();q1.pop();if(f[id]!-1){if(st[f[id]]1){fg1;break;}q1next.push(f[id]);}if(m[id]!-1){if(st[m[id]]1){fg1;break;}q1next.push(m[id]);}}swap(q1,q1next);if(fg)break;}if(fg)coutNo\n;elsecoutYes\n;}}return0;}代码解析三个数组分别存储父亲ID、母亲ID、性别数组大小覆盖所有可能的5位ID。第一轮BFS将第一个人的四代祖先全部标记第二轮BFS遍历第二个人的四代祖先同时检查是否存在重合。每层处理完后交换队列进入上一代的遍历共循环4次覆盖四代祖先。用标记变量记录是否找到共同祖先找到后可提前终止遍历。
