|
|
|
|
|
##[$AcWing$ $238$. 银河英雄传说](https://www.acwing.com/problem/content/240/)
|
|
|
|
|
|
|
|
|
|
|
|
### 一、题目描述
|
|
|
|
|
|
有一个划分为 $N$ 列的星际战场，各列依次编号为 $1,2,…,N$。
|
|
|
|
|
|
|
|
|
|
|
|
有 $N$ 艘战舰，也依次编号为 $1,2,…,N$，其中第 $i$ 号战舰处于第 $i$列。
|
|
|
|
|
|
|
|
|
|
|
|
有 $T$ 条指令，每条指令格式为以下两种之一：
|
|
|
|
|
|
|
|
|
|
|
|
`M i j`，表示让第 $i$号战舰所在列的全部战舰保持原有顺序，接在第 $j$号战舰所在列的尾部。
|
|
|
|
|
|
`C i j`，表示询问第 $i$ 号战舰与第 $j$ 号战舰当前是否处于同一列中，**如果在同一列中，它们之间间隔了多少艘战舰**。
|
|
|
|
|
|
|
|
|
|
|
|
现在需要你编写一个程序，处理一系列的指令。
|
|
|
|
|
|
**输入格式**
|
|
|
|
|
|
|
|
|
|
|
|
第一行包含整数 $T$，表示共有 $T$条指令。
|
|
|
|
|
|
|
|
|
|
|
|
接下来 $T$行，每行一个指令，指令有两种形式：`M i j` 或 `C i j`。
|
|
|
|
|
|
|
|
|
|
|
|
其中 $M$ 和 $C$ 为大写字母表示指令类型，$i$ 和 $j$ 为整数，表示指令涉及的战舰编号。
|
|
|
|
|
|
|
|
|
|
|
|
**输出格式**
|
|
|
|
|
|
|
|
|
|
|
|
你的程序应当依次对输入的每一条指令进行分析和处理：
|
|
|
|
|
|
|
|
|
|
|
|
如果是 `M i j` 形式，则表示舰队排列发生了变化，你的程序要注意到这一点，但是不要输出任何信息；
|
|
|
|
|
|
|
|
|
|
|
|
如果是 `C i j` 形式，你的程序要输出一行，仅包含一个整数，表示在同一列上，第 $i$
|
|
|
|
|
|
号战舰与第 $j$ 号战舰之间布置的战舰数目，如果第 $i$ 号战舰与第 $j$ 号战舰当前不在同一列上，则输出 $−1$。
|
|
|
|
|
|
|
|
|
|
|
|
**数据范围**
|
|
|
|
|
|
|
|
|
|
|
|
$N≤30000,T≤500000$
|
|
|
|
|
|
|
|
|
|
|
|
**输入样例**：
|
|
|
|
|
|
```cpp {.line-numbers}
|
|
|
|
|
|
4
|
|
|
|
|
|
M 2 3
|
|
|
|
|
|
C 1 2
|
|
|
|
|
|
M 2 4
|
|
|
|
|
|
C 4 2
|
|
|
|
|
|
```
|
|
|
|
|
|
|
|
|
|
|
|
**输出样例**：
|
|
|
|
|
|
```cpp {.line-numbers}
|
|
|
|
|
|
-1
|
|
|
|
|
|
1
|
|
|
|
|
|
```
|
|
|
|
|
|
|
|
|
|
|
|
### 二、解题思路
|
|
|
|
|
|
|
|
|
|
|
|
* 并查集除可以维护集合异同关系外，还可维护集合中元素数量
|
|
|
|
|
|
* 除了维护集合中元素的数量，还同时需要维护距离根的距离长度
|
|
|
|
|
|
|
|
|
|
|
|
[姊妹题 $POJ-1988-Cube Stacking$](https://www.cnblogs.com/littlehb/p/16128501.html)
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
### 三、实现代码
|
|
|
|
|
|
```cpp {.line-numbers}
|
|
|
|
|
|
#include <bits/stdc++.h>
|
|
|
|
|
|
|
|
|
|
|
|
using namespace std;
|
|
|
|
|
|
const int N = 30010;
|
|
|
|
|
|
|
|
|
|
|
|
int m;
|
|
|
|
|
|
int p[N], sz[N], d[N];
|
|
|
|
|
|
|
|
|
|
|
|
int find(int x) {
|
|
|
|
|
|
if (p[x] != x) {
|
|
|
|
|
|
int px = find(p[x]);
|
|
|
|
|
|
d[x] += d[p[x]]; // 距离
|
|
|
|
|
|
p[x] = px;
|
|
|
|
|
|
}
|
|
|
|
|
|
return p[x];
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
int main() {
|
|
|
|
|
|
scanf("%d", &m);
|
|
|
|
|
|
|
|
|
|
|
|
for (int i = 1; i < N; i++) p[i] = i, sz[i] = 1;
|
|
|
|
|
|
|
|
|
|
|
|
while (m--) {
|
|
|
|
|
|
char op[2]; // 读入一个操作符的办法：读入一个字符串，只用op[0]
|
|
|
|
|
|
scanf("%s", op);
|
|
|
|
|
|
int a, b;
|
|
|
|
|
|
scanf("%d %d", &a, &b);
|
|
|
|
|
|
if (op[0] == 'M') {
|
|
|
|
|
|
int pa = find(a), pb = find(b);
|
|
|
|
|
|
if (pa != pb) { // 如果a,b不在同一个集合中，需要合并集合
|
|
|
|
|
|
d[pa] = sz[pb]; // 需要在它家族人数未修改前，记录下pa前面的船的数量，否则，修改完就没机会了
|
|
|
|
|
|
sz[pb] += sz[pa]; // 维护pb家族人员数量
|
|
|
|
|
|
p[pa] = pb; // 将pa加入pb家族
|
|
|
|
|
|
}
|
|
|
|
|
|
} else {
|
|
|
|
|
|
int pa = find(a), pb = find(b);
|
|
|
|
|
|
if (pa != pb) // 不在一起
|
|
|
|
|
|
puts("-1");
|
|
|
|
|
|
else
|
|
|
|
|
|
// 注意：题目C操作问的是间隔多少条船，若a != b，
|
|
|
|
|
|
// 则间隔abs(d[a] - d[b]) - 1条船，若a == b，则间隔0条船
|
|
|
|
|
|
cout << max(0, abs(d[a] - d[b]) - 1) << endl;
|
|
|
|
|
|
}
|
|
|
|
|
|
}
|
|
|
|
|
|
return 0;
|
|
|
|
|
|
}
|
|
|
|
|
|
```
|
