欢迎来到起遇信息学
起遇信息学正处于上线筹建阶段，以下功能已全部开放免费体验： ✅ 完整题库浏览与代码提交评测（C / C++ / Python / Java 等） ✅ 入门到进阶的系列课程试读、作业与考试 ✅ AI 提示、AI 作业分析等智能助教功能 ✅ 赛事模拟与个人能力报告 ✅ 邮箱注册开放 ⏳ 付费课程订阅与微信/支付宝支付通道 ⏳ 手机号登录，微信扫码登录、微信公众号绑定 使用中如遇任何问题，欢迎通过页面底部 **"联系我们"** 与我们沟通。
T1: 题目：原序列中，c[i]=i.现在要求在序列上支持两种操作：
1 x c：将与x相邻且颜色相同的单元格绘制为颜色c。
2 C：打印颜色c的单元格数。
分析：已经合并的，不会再次分开。所以这和并查集的性质一样，用并查集解决，维护每段的左右L[i],R[i],以及col[i]和sz[i].
/**/
#include<bits/stdc++.h>
using namespace std;
int fa[500005];
int sz[500005];
int col[500005];
int L[500005];
int R[500005];
int ans[500005];
int q;
int n;
int find(int x){
if(fa[x]==x)return x;
else return fa[x]=find(fa[x]);
}
int main(){
cin>>n>>q;
for(int i=1;i<=n;i++){
col[i]=i;
sz[i]=1;
fa[i]=i;
L[i]=i;
R[i]=i;
ans[i]=1;
}
while(q--){
int op;
cin>>op;
if(op==1){
int x,c;
cin>>x>>c;
int fx=find(x);
ans[col[fx]]-=(R[fx]-L[fx]+1);
ans[c]+=(R[fx]-L[fx]+1);
col[fx]=c;
int l=L[fx]-1;
int r=R[fx]+1;
if(l>=1){
int fl=find(l);
if(col[fl]==col[fx]){
fa[fl]=fa[fx];
sz[fx]+=sz[fl];
L[fx]=L[fl];
}
}
if(r<=n){
int fr=find(r);
if(col[fr]==col[fx]){
fa[fr]=fa[fx];
sz[fx]+=sz[fr];
R[fx]=R[fr];
}
}
} else{
int c;
cin>>c;
cout<<ans[c]<<"\n";
}
}
return 0;
}
T2:
题目分析：并查集模版和求集合大小
#include<bits/stdc++.h>
using namespace std;
int n,m;
int fa[500005];
int sz[500005];
int find(int x){
if(fa[x]==x)return x;
else return fa[x]=find(fa[x]);
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
fa[i]=i;
sz[i]=1;
}
for(int i=1;i<=m;i++){
int k;
cin>>k;
int x;
if(k==0)continue;
k-=1;
cin>>x;
while(k--){
if(k<0)break;
int y;
cin>>y;
int fx=find(x);
int fy=find(y);
fa[fy]=fx;
if(fx!=fy)
sz[fx]+=sz[fy];
}
}
for(int i=1;i<=n;i++){
cout<<sz[find(i)]<<" ";
}
return 0;
}
T3: 题目：给一个序列，将数组中的数按照这个序列给出的顺序一个个拿走，问每次拿走后最大的连续段和是多少。
分析：如果按照题目给出的顺序，难以处理。可以考虑倒着处理，一个个加入数组中，更好维护连续段的和。
/*
一个个删除=反向一个个加入
倒着维护各个集合内元素总和以及集合
*/
#include<bits/stdc++.h>
using namespace std;
int n;
int a[100005];
long long sum[100005];
int fa[100005];
int era[100005];
long long ans[100005];
long long maxx=0;
bool vis[100005];
int find(int x){
if(fa[x]==x)return x;
else return fa[x]=find(fa[x]);
}
int main(){
cin>>n;
for(int i=1;i<=n;i++)fa[i]=i;
for(int i=1;i<=n;i++){cin>>a[i];sum[i]=a[i];}
for(int i=1;i<=n;i++)cin>>era[i];
for(int j=n;j>=1;j--){
int i=era[j];
vis[i]=1;
int fi=find(i);
ans[j]=maxx;
maxx=max(maxx,sum[fi]);
if(vis[i-1]==1&&vis[i+1]!=1){
int f1=find(i-1);
fa[fi]=f1;
if(fi!=f1){
sum[f1]+=sum[fi];
maxx=max(maxx,sum[f1]);
}
}
if(vis[i+1]==1&&vis[i-1]!=1){
int f1=find(i+1);
fa[fi]=f1;
if(fi!=f1){
sum[f1]+=sum[fi];
maxx=max(maxx,sum[f1]);
}
}
if(vis[i+1]==1&&vis[i-1]==1){
int f1=find(i-1);
int f2=find(i+1);
fa[f1]=fi;
fa[f2]=fi;
sum[fi]=sum[fi]+sum[f1]+sum[f2];
maxx=max(maxx,sum[fi]);
}
}
for(int i=1;i<=n;i++)cout<<ans[i]<<"\n";
return 0;
}
T4: 题目：给定一张图。每个联通块内的节点编号必须连续。若不连续，可以与其他联通块连边，问最少要联多少条边才能满足上面的条件？ 思路：用并查集做。维护每个集合的最大最小值。最后按照最小值排序。如果下一个集合的最小值<上一个集合的最大值，ans++; 如果不小于了，那么要新开一个联通块。
#include<bits/stdc++.h>
using namespace std;
int n,m;
int fa[200005];
struct node{
int l,r;
}h[200005];
vector<node>v;
vector<int>lian[200005];
int bianhao[200005];
int cnt=0;
int find(int x){
if(fa[x]==x)return x;
else return fa[x]=find(fa[x]);
}
bool cmp(node a,node b){
return a.l<b.l;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
fa[i]=i;
h[i].l=i;
h[i].r=i;
}
for(int i=1;i<=m;i++){
int u,v;
scanf("%d%d",&u,&v);
int fu=find(u);
int fv=find(v);
if(fu>fv)swap(fu,fv);
fa[fu]=fv;
h[fv].l=min(h[fu].l,h[fv].l);
h[fv].r=max(h[fu].r,h[fv].r);
}
for(int i=1;i<=n;i++){
if(fa[i]==i){
v.push_back({h[i].l,h[i].r});
}
}
sort(v.begin(),v.end(),cmp);
int now_r=v[0].r;
int ans=0;
if(v.empty()){
cout<<ans<<"\n";
return 0;
}
for(int i=1;i<(int)v.size();i++){
int nxt_l=v[i].l;
int nxt_r=v[i].r;
if(nxt_l<=now_r){
ans++;
now_r=max(now_r,nxt_r);
} else{
now_r=nxt_r;
}
}
cout<<ans;
return 0;
}
T5: 题目： 给定一张含 n 个顶点、m 条带权边的连通无向图，其中有 k 个特殊顶点。 一条路径的代价定义为路径上最大的边权。两个顶点的距离，定义为连接它们的所有路径中的最小代价。 对每个特殊顶点，求它到其他特殊顶点的最大距离。 分析：k个点两两互通，就是求这k个点形成的树。由于求最大距离，所以将边按边权从小到大排序，如果形成了树，那么就求得了答案。由于要求最大距离，所以最大的边就是答案。
#include<bits/stdc++.h>
using namespace std;
int n,m,k;
int is[100005];
struct Edge{
int u,v,w;
}e[100005];
bool cmp(Edge a,Edge b){
return a.w<b.w;
}
int fa[100005];
int sz[100005];
int find(int x){
if(fa[x]==x)return x;
else return fa[x]=find(fa[x]);
}
int main(){
cin>>n>>m>>k;
for(int i=1;i<=n;i++){
fa[i]=i;
}
for(int i=1;i<=k;i++){
int x;
cin>>x;
is[x]=1;
sz[x]=1;
}
for(int i=1;i<=m;i++){
cin>>e[i].u>>e[i].v>>e[i].w;
}
sort(e+1,e+1+m,cmp);
int ans=0;
for(int i=1;i<=m;i++){
int u=e[i].u;
int v=e[i].v;
int ru=find(u);
int rv=find(v);
if(find(u)!=find(v)){
fa[ru]=rv;
sz[rv]+=sz[ru];
}
if(sz[rv]==k){
ans=e[i].w;
break;
}
}
while(k--){
cout<<ans<<" ";
}
return 0;
}
T6: 分析：对边按权值从小到大排序，对限制条件从小到大排序，在限制条件下尽可能加边，再判断边上的两点是否不在同一集合中，若不在，则更新ans=ans+sz[u]*sz[v].
#include<bits/stdc++.h>
using namespace std;
int n,m;
int fa[200005],sz[200005];
struct node{
int u,v,w;
}e[200005];
struct node1{
int id;
int val;
long long an=0;
}q[200005];
bool cmp(node x,node y){
return x.w<y.w;
}
bool cmp2(node1 x,node1 y){
return x.val<y.val;
}
bool cmp1(node1 x,node1 y){
return x.id<y.id;
}
int find(int x){
if(x==fa[x])return x;
else return fa[x]=find(fa[x]);
}
unsigned long long ans=0;
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
fa[i]=i;
sz[i]=1;
}
for(int i=1;i<=n-1;i++)cin>>e[i].u>>e[i].v>>e[i].w;
for(int i=1;i<=m;i++){
cin>>q[i].val;
q[i].id=i;
}
sort(e+1,e+n,cmp);
sort(q+1,q+1+m,cmp2);
int i=1,j=1;
for(;j<=m;j++){
while(e[i].w<=q[j].val&&i<=n-1){
int u=e[i].u;
int v=e[i].v;
u=find(u);
v=find(v);
if(u!=v){
if(u>v)swap(u,v);
fa[u]=v;
ans+=(long long)sz[u]*sz[v];
sz[v]+=sz[u];
}
i++;
}
q[j].an=ans;
}
sort(q+1,q+1+m,cmp1);
for(int i=1;i<=m;i++)cout<<q[i].an<<" ";
return 0;
}
/*
*/
0 条评论
目前还没有评论...
Be the first to comment!
返回讨论列表
107
通过题目
10
发帖数