NOI2002银河英雄传说

编程基础 • 2025-01-03 08:01 • 阅读 87

题目大意：

有一个划分为N列的星际战场，各列依次编号为1，2，……，N。有N艘战舰，也依次编号为1，2，……，N，其中第i号战舰处于第i列。

有M条指令，每条指令格式为以下两种之一：

1.M i j，表示让第i号战舰所在列的全部战舰保持原有顺序，接在第j号战舰的尾部。

2.C i j，表示询问第i号战舰与第j号战舰当前是否处于同一列中，如果在同一列中，它们之间间隔了多少艘战舰。

其中N<=30000,M<=.

题目链接：codevs：http://codevs.cn/problem/1540，luogu：https://www.luogu.org/problemnew/show/P1196.

思路：

这题使用的主要数据结构为并查集，将所有战舰放进并查集中来进行查询和合并。

由于数据范围较大，我们需要将并查集的合并进行路径压缩，因为路径压缩会改变它们的原有顺序，因此我们用一个数组d来记录各点到祖先的距离，d数组相减的绝对值即为两数之间的距离。

getfather操作：

在对一艘战舰进行路径压缩的同时，也让d[x]等于它的父亲节点的权值+1.

merge操作：

让x的root等于y的儿子，则d[x]就等于y的集合大小，同时将y的集合大小加上x的集合大小。

代码实现：

int getfather(int x) { if(x==fa[x]) return x; //如果该节点为根节点，则返回 int root=getfather(fa[x]); d[x]+=d[fa[x]]; //子节点到root的距离=父节点到root的距离+1 return fa[x]=root; //路径压缩 } void merge(int x,int y) { x=getfather(x),y=getfather(y); fa[x]=y;d[x]=size[y]; //让x的父节点等于y，x到原点的距离等于y的长度 size[y]+=size[x]; //y的长度+=x的长度 }

完整代码如下：

#include<cstdio> #include<cmath> using namespace std; int n,p,q,d[]; char c; int read() { int num = 0, flag = 1; char c = getchar(); for(; c < '0' || c > '9'; c = getchar()) if(c == '-') flag = 0; for(; c >= '0' && c <= '9'; c = getchar()) num = (num<<3)+(num<<1)+c-48; return flag? num: -num; } int fa[],size[]; inline int getfather(int x) { if(x==fa[x]) return x; int root=getfather(fa[x]); d[x]+=d[fa[x]]; return fa[x]=root; } inline void merge(int x,int y) { x=getfather(x),y=getfather(y); fa[x]=y;d[x]=size[y]; size[y]+=size[x]; } int main() { n=read(); for(int i=1;i<=;i++) fa[i]=i,size[i]=1; for(int i=1;i<=n;i++) { c=getchar();p=read();q=read(); if(c=='M') merge(p,q); if(c=='C') { if(getfather(p)!=getfather(q)) puts("-1\n"); else { int ans=abs(d[p]-d[q])+1; printf("%d\n",ans-2); } } } return 0; }

今天的文章 NOI2002银河英雄传说分享到此就结束了，感谢您的阅读。