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

L2-025 分而治之

题目大意：给定N个城市、M条通路构成的无向图。给出K个方案，每个方案指定要攻占的城市集合。判断攻占这些城市后，剩余的所有城市之间是否不存在任何通路（即剩余城市全部孤立），是则输出YES，否则输出NO。

解题思路
核心是判断删点后剩余图的边数是否为0。直接每次删点重建图效率过低，因此采用度数统计法：

1. 预先存储每个点的初始度数，以及每个点的邻接表。
2. 对于每个方案，先复制一份所有点的初始度数。
3. 遍历每一个被攻占的城市x：将x的度数置为0（相当于删除该点）；同时遍历x的所有邻居，将邻居的度数减1（相当于删除x连向邻居的边）。
4. 最后统计所有城市的度数之和：若总和为0，说明剩余城市之间没有边，方案可行，输出YES；否则输出NO。

复杂度分析：每个方案遍历所有点和边，总时间复杂度为O ( K × ( N + M ) ) O(K\times(N+M))O(K×(N+M))，在题目数据范围下完全可以通过。

代码解析

• g[N]：邻接表，存储无向图的连接关系。
• sz[]：临时数组，记录每个点当前的剩余度数。
• 每次询问初始化sz数组为各点原始度数，处理被攻占的点后统计度数总和，判断是否为0。

正解代码

#include<bits/stdc++.h>usingnamespacestd;constintN=1e4+9;intn,m,k,t,sz[N];vector<int>g[N];intmain(){cin>>n>>m;for(inti=0;i<m;i++){intu,v;cin>>u>>v;g[u].push_back(v);g[v].push_back(u);}cin>>k;while(k--){cin>>t;for(inti=1;i<=n;i++){sz[i]=g[i].size();//cout<<sz[i]<<' ';}intcnt=0;for(inti=0;i<t;i++){intx;cin>>x;for(autont:g[x])sz[nt]=max(0,sz[nt]-1);//度数减1时不能小于0sz[x]=0;//被攻占的城市本身要置为度数0，不计入剩余边。}for(inti=1;i<=n;i++)cnt+=sz[i];if(!cnt)cout<<"YES\n";elsecout<<"NO\n";}return0;}

L2-026 小字辈

题目大意：给定一个家族的家谱结构，每个成员有唯一的父/母编号，老祖宗的父/母编号为-1。老祖宗辈分为1，每向下一代辈分+1。请找出辈分最小（深度最大）的所有成员，输出最小辈分和对应的成员编号。

解题思路
这是一道典型的树的深度遍历问题：

1. 首先根据输入的父节点信息建树，将每个节点加入其父节点的邻接表中，同时记录根节点（父节点为-1的节点）。
2. 从根节点出发进行DFS（或BFS），计算每个节点的深度（辈分），同时记录最大深度。
3. 遍历所有节点，收集所有深度等于最大深度的节点，按编号升序输出。

代码解析

• g[N]：存储家族树的邻接表，每个节点存储它的子节点。
• a[]：记录每个节点的深度（辈分）。
• dfs函数：递归遍历子节点，子节点深度 = 当前节点深度 + 1，同时更新最大深度mx。
• 最后遍历所有节点收集答案，按编号顺序输出。

正解代码

#include<bits/stdc++.h>//#define int long longusingnamespacestd;constintN=1e5+9;inta[N],t,x,n,root,mx;vector<int>g[N];voiddfs(intnow,intdeep){a[now]=deep;mx=max(mx,deep);if(!g[now].size())return;for(autont:g[now])dfs(nt,deep+1);}signedmain(){cin>>n;for(inti=1;i<=n;i++){intx;cin>>x;if(x!=-1)g[x].push_back(i);elseroot=i;}dfs(root,1);vector<int>ans;for(inti=1;i<=n;i++)if(a[i]==mx)ans.push_back(i);cout<<mx<<'\n';for(inti=0;i<ans.size();i++){cout<<ans[i];if(i!=ans.size()-1)cout<<' ';}return0;}

L2-027 名人堂与代金券

题目大意：给定N名学生的账号和总评成绩，按规则计算代金券总额，并输出进入名人堂的学生名单。规则：

• 成绩≥G：奖励50元代金券；60≤成绩<G：奖励20元代金券；<60无奖励。
• 名人堂为总排名前K名的学生，成绩相同则并列排名，并列时按账号字典序升序排列。

解题思路

1. 自定义排序：按成绩降序排列，成绩相同则按账号字符串字典序升序排列。
2. 统计代金券：遍历排序后的数组，按成绩区间累加代金券总额。
3. 处理并列排名：名次规则为“成绩不同时，名次等于当前已遍历人数”。例如第1、2名成绩不同，第3、4名成绩相同，则两人都是第3名，下一名为第5名。遍历输出直到名次超过K为止。

正解代码

#include<bits/stdc++.h>usingnamespacestd;constintN=1e5+9;structnd{string id;intsco;booloperator<(constnd nd1){if(sco!=nd1.sco)returnsco>nd1.sco;returnid<nd1.id;}}v[N];intn,x,k,G;intmain(){cin>>n>>G>>k;for(inti=1;i<=n;i++){cin>>v[i].id>>v[i].sco;}intcnt=0,rting=0,res=0;sort(v+1,v+1+n);for(inti=1;i<=n;i++){if(v[i].sco<60)break;if(v[i].sco>=G)cnt+=50;elsecnt+=20;}cout<<cnt<<'\n';cout<<1<<' '<<v[1].id<<' '<<v[1].sco<<'\n';rting=1;res=1;//总人数for(inti=2;i<=n;i++){res++;if(v[i].sco!=v[i-1].sco)rting=res;if(rting>k)break;cout<<rting<<' '<<v[i].id<<' '<<v[i].sco<<'\n';}return0;}

代码解析

• 结构体nd：存储学生账号id和成绩sco，重载<运算符实现自定义排序规则。
• cnt：统计代金券总金额。
• rting：记录当前名次，res记录当前已遍历的总人数。当成绩与前一名不同时，更新名次为当前人数。

L2-028 秀恩爱分得快

题目大意：给定M张照片，每张照片有K个人。任意一对异性若同框，亲密度增加1/K。给定一对异性情侣A、B，分别找出与A、B亲密度最高的异性。若A和B互为对方的最高亲密度，则只输出两人；否则分别输出各自的最高亲密度异性，多人并列时按编号绝对值升序输出。

解题思路

1. 性别与编号处理：编号带负号为女性，正号为男性，存储时用绝对值作为数组下标，单独记录性别。
2. 亲密度计算：对于每张照片，将男性、女性分为两组，遍历所有男女组合，给他们的亲密度加上1/K。
3. 查询最高亲密度：分别找到与A、B亲密度最高的异性的亲密度数值。
4. 判断特殊情况：若A与B的亲密度同时等于双方的最高亲密度，说明二人互为最亲密异性，直接输出二人编号。否则分别输出A、B对应的所有最高亲密度异性。

正解代码

#include<bits/stdc++.h>usingnamespacestd;constintN=1010;intn,m;doubleg[N][N];//g 男女intmain(){cin>>n>>m;for(inti=0;i<m;i++){intx;string y;vector<int>by,gl;cin>>x;for(intj=0;j<x;j++){cin>>y;intyy=stoi(y);if(y[0]=='-'){//女gl.push_back(abs(yy));}elseby.push_back(yy);//男}for(intj=0;j<by.size();j++){for(intk=0;k<gl.size();k++){g[by[j]][gl[k]]+=1.0/(x*1.0);}}}string na1,na2;boolfg=0;//女男 1男女cin>>na1>>na2;intn1=abs(stoi(na1));intn2=abs(stoi(na2));if(na2[0]=='-'){fg=1;swap(n1,n2);swap(na1,na2);}doublemxby=0,mxgl=0;//最亲密男朋友 女朋友for(inti=0;i<n;i++)mxby=max(mxby,g[i][n1]);for(inti=0;i<n;i++)mxgl=max(mxgl,g[n2][i]);if(g[n2][n1]==mxgl&&g[n2][n1]==mxby){if(!fg)cout<<na1<<' '<<na2<<'\n';elsecout<<na2<<' '<<na1<<'\n';return0;}if(!fg){//先女for(inti=0;i<n;i++)if(g[i][n1]==mxby)cout<<"-"<<n1<<' '<<i<<'\n';for(inti=0;i<n;i++)if(g[n2][i]==mxgl)cout<<n2<<" -"<<i<<'\n';}else{//先男for(inti=0;i<n;i++)if(g[n2][i]==mxgl)cout<<n2<<" -"<<i<<'\n';for(inti=0;i<n;i++)if(g[i][n1]==mxby)cout<<"-"<<n1<<' '<<i<<'\n';}return0;}

代码解析

• g[N][N]：二维数组存储异性间的亲密度，第一维为男性编号，第二维为女性编号。
• 每张照片拆分男性列表by和女性列表gl，双重循环累加亲密度。
• fg标记输入的情侣顺序（女男/男女），保证最终输出顺序与输入一致。
• 最后分别遍历所有异性，找出最高亲密度对应的所有编号并输出。