企业官网建设流程全解析

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

L2-013 红色警报

题目大意：给定城市间的通路网络，城市会被逐个攻占。每失去一个城市，判断其是否会导致剩余城市的连通区域数量增加（即该城市是割点，移除后网络分裂）。若是则输出红色警报，否则输出普通丢失提示；所有城市都失陷后输出Game Over.。

解题思路：

1. 核心采用并查集维护连通性，由于城市是逐步被删除的，而并查集不支持删除操作，因此采用每次删除后重建并查集的方式计算当前连通块数量。
2. 初始时计算完整图的连通块总数。每攻占一个城市，就将所有与该城市相连的边标记为失效，用剩余有效边重建并查集，统计当前所有节点的连通块总数。
3. 判定规则：若删除后连通块总数 > 删除前连通块总数 + 1，说明该城市的移除导致原有连通区域分裂，触发红色警报。该判定等价于：剩余未失陷城市的连通块数量相比删除前有所增加。
4. 最后若攻占数等于城市总数，额外输出Game Over.。

正解代码

#include<bits/stdc++.h>usingnamespacestd;constintN=5200;intn,m,f[N],k;structnd{inta,b;boolfg=0;}e[N];intfind(intx){if(f[x]!=x)f[x]=find(f[x]);returnf[x];}voidhb(inta,intb){intaa=find(a),bb=find(b);f[aa]=bb;}intmain(){cin>>n>>m;for(inti=0;i<n;i++)f[i]=i;for(inti=1;i<=m;i++){cin>>e[i].a>>e[i].b;hb(e[i].a,e[i].b);}cin>>k;intlost,cnt=0,now=0;for(inti=0;i<n;i++)if(f[i]==i)cnt++;//连通块数量for(inti=0;i<k;i++){cin>>lost;now=0;for(intj=0;j<n;j++)f[j]=j;for(intj=1;j<=m;j++){if(e[j].fg||e[j].a==lost||e[j].b==lost){e[j].fg=1;continue;}hb(e[j].a,e[j].b);}for(intj=0;j<n;j++)if(f[j]==j)now++;if(now>cnt+1)printf("Red Alert: City %d is lost!\n",lost);elseprintf("City %d is lost.\n",lost);cnt=now;}if(k==n)cout<<"Game Over.";return0;}

代码解析：

• 结构体存储每条边的两个端点及失效标记，攻占城市时将包含该城市的边标记为失效。
• find函数实现路径压缩的并查集查找，hb函数实现合并操作。
• 每次攻占城市后重置并查集数组，仅用有效边合并节点，统计根节点数量得到连通块总数。
• 通过now > cnt + 1判断是否触发红色警报，更新当前连通块数为下一次判定做准备。

L2-014 列车调度

题目大意：列车按给定顺序驶入平行调度轨道，要求最终从出口按序号递减顺序驶出，求完成调度最少需要多少条平行轨道。

解题思路：

1. 问题可转化为经典的最长递增子序列问题：将序列划分为最少的递减子序列，其最少个数等于原序列的最长递增子序列长度。
2. 采用贪心+二分的O(nlogn)算法求解最长递增子序列：维护一个数组，数组中每个元素表示对应长度递增子序列的最小末尾值。
3. 遍历每个列车序号：若当前序号大于数组末尾元素，直接追加到数组后；否则找到数组中第一个大于当前序号的元素，将其替换为当前序号。最终数组长度即为答案。

正解代码

#include<bits/stdc++.h>usingnamespacestd;constintN=1e5+9;intf[N],n,p=0;intmain(){cin>>n;intx;cin>>x;f[++p]=x;for(inti=1;i<n;i++){cin>>x;if(x>=f[p])f[++p]=x;else{intpos=upper_bound(f+1,f+1+p,x)-f;f[pos]=x;//将a[i]换为原f中第一个>=a[i]的数}}cout<<p;return0;}

代码解析：

• 数组f维护递增子序列的末尾值，p记录当前数组长度。
• 使用upper_bound在有序数组中快速查找替换位置，保证数组始终递增。
• 替换操作的意义是让子序列末尾尽可能小，为后续更大的数留出空间，从而得到最长的递增子序列。

L2-015 互评成绩

题目大意：每位学生有k个评审成绩，去掉一个最高分和一个最低分后取平均值作为最终成绩。要求输出得分最高的M个成绩，按非递减顺序排列，保留3位小数。

解题思路：

1. 逐个读取每位学生的k个成绩，同步累加总分、记录最高分和最低分。
2. 总分减去最高分和最低分，除以(k-2)得到最终平均分，存入结果数组。
3. 将所有平均分升序排序，取最后M个即为得分最高的M个成绩，按顺序格式化输出。

正解代码

#include<bits/stdc++.h>usingnamespacestd;intmain(){intn,m,k;cin>>n>>k>>m;vector<double>v;intx;doublesum;for(inti=0;i<n;i++){sum=0;intmx=-1,mi=999;// 读取k个分数for(intj=0;j<k;j++){cin>>x;sum+=x;mx=max(mx,x);mi=min(mi,x);}// 去掉最高分和最低分，计算平均sum=sum-mx-mi;doubleavg=sum*1.000/(k-2);// cout<<"sum:"<<sum<<' '<<avg<<endl;v.push_back(avg);}// 排序并输出前m个最高分sort(v.begin(),v.end());for(inti=n-m;i<n;i++){printf("%.3f",v[i]);if(i!=n-1)cout<<' ';}return0;}

代码解析：

• 遍历每个学生成绩时，用变量mx和mi分别跟踪当前最高分和最低分，无需排序即可快速得到极值，效率更高。
• 排序后数组下标n-m到n-1对应最高的M个成绩，按顺序输出即满足非递减要求。
• 使用printf("%.3f")控制输出格式，保证三位小数精度。

L2-016 愿天下有情人都是失散多年的兄妹

题目大意：判断一对异性是否可以通婚：若两人五代以内（本人、父母、祖父母、曾祖父母、高祖父母）存在共同祖先，则不可通婚；同性直接输出Never Mind。

解题思路：

1. 预处理存储每个人的性别、父亲ID、母亲ID。
2. 对每对查询：
   • 首先判断性别，同性直接输出Never Mind。
   • 异性则先遍历第一个人的五代以内所有祖先，用标记数组记录。
   • 再遍历第二个人的五代以内所有祖先，若遇到已标记的节点，说明存在共同祖先，判定不可通婚。
3. 采用BFS逐层向上遍历祖先，控制遍历层数为4代（父母至高祖父母），确保仅检查五代以内。

正解代码

#include<bits/stdc++.h>usingnamespacestd;constintN=1e6;intf[N],m[N],s[N],n;boolst[N];intmain(){memset(f,-1,sizeoff);memset(m,-1,sizeofm);memset(s,-1,sizeofs);cin>>n;for(inti=0;i<n;i++){intid,fid,mid;charS;cin>>id>>S>>f[id]>>m[id];if(S=='M')s[id]=1;elses[id]=0;s[f[id]]=1;s[m[id]]=0;}intk;cin>>k;while(k--){inta,b;cin>>a>>b;if(s[a]==s[b])cout<<"Never Mind\n";else{boolfg=0;memset(st,0,sizeofst);queue<int>q,qnext;q.push(a);for(inti=0;i<4;i++){while(q.size()){autoid=q.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);}queue<int>q1,q1next;q1.push(b);for(inti=0;i<4;i++){while(q1.size()){autoid=q1.front();q1.pop();if(f[id]!=-1){if(st[f[id]]==1){fg=1;break;}q1next.push(f[id]);}if(m[id]!=-1){if(st[m[id]]==1){fg=1;break;}q1next.push(m[id]);}}swap(q1,q1next);if(fg)break;}if(fg)cout<<"No\n";elsecout<<"Yes\n";}}return0;}

代码解析：

• 三个数组分别存储父亲ID、母亲ID、性别，数组大小覆盖所有可能的5位ID。
• 第一轮BFS将第一个人的四代祖先全部标记，第二轮BFS遍历第二个人的四代祖先，同时检查是否存在重合。
• 每层处理完后交换队列，进入上一代的遍历，共循环4次覆盖四代祖先。
• 用标记变量记录是否找到共同祖先，找到后可提前终止遍历。