【解题报告】[NOI2002]银河英雄传说
题意简述
处理M个指令，都为两种如下形式的指令之一
1.M i j 表示让第i好战舰所在列的全部战舰保持原有顺序，接在第j好战舰所在列的尾部。
2.C i j，表示询问第i号战舰与第j号战舰当前是否处于同一列中，如果在同一列中，它们之间间隔了多少艘战舰。如果不在同一列中，输出-1；
解题思路
并查集
第二个指令我们要知道i，j两号战舰差多少，维护一个数列d即可，d[x]代表x前面的战舰数量,要查询的时候，我们只要知道i，j两号前面各有多少战舰，然后i前面的减去j前面的绝对值减一就可以了。
而第一个指令就是简单地处理一下size，记录集合大小，也很简单
AC代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
| #include <iostream>
#include <cstdio>
using namespace std;
int f[30005];
int d[30005];
int size[30005];
int t;
int jdz(int x)
{
return x>0? x:(-x);
}
void init()
{
for(int i=1;i<=30000;i++)
{
f[i]=i;
size[i]=1;
}
}
int get(int x)
{
if(x==f[x])
return x;
int root=get(f[x]);
d[x]+=d[f[x]];
return f[x]=root;
}
void merge(int x,int y)
{
x=get(x),y=get(y);
f[x]=y;d[x]=size[y];
size[y]+=size[x];
}
int main()
{
cin>>t;
init();
for(int i=1;i<=t;i++)
{
char s[2];
int x,y;
scanf("%s",s);
cin>>x>>y;
if(s[0]=='M')
merge(x,y);
if(s[0]=='C')
{
if(get(x)==get(y))
cout<<jdz(d[x]-d[y])-1<<endl;
else
cout<<"-1"<<endl;
}
}
return 0;
}
|
数据情况https://www.luogu.org/record/22153408
