银河英雄传说 C++题解

编程基础 • 2024-12-20 08:27 • 阅读 23

银河英雄传说

内存限制： 256 MiB 时间限制： 1500 ms 标准输入输出题目类型：传统评测方式：文本比较

题目描述

有一个划分为N列的星际战场，各列依次编号为 1,2,…,N。

有N艘战舰，也依次编号为 1,2,…,N,其中第 i 号战舰处于第 i 列。

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

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

2、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。

样例

样例输入

复制4 M 2 3 C 1 2 M 2 4 C 4 2

样例输出

复制-1 1

数据范围与提示

N ≤ 30000,T ≤

#include <bits/stdc++.h> #define int long long using namespace std; const int N = 3e4 + 5; char c; int t, x, y; int ans[N], size[N], parent[N]; void init(int n) { for(int i = 1; i <= n; i++) { size[i] = 1; parent[i] = i; } } int find(int x) { if(x == parent[x]) { return x; } int fa = parent[x]; parent[x] = find(parent[x]); ans[x] += ans[fa]; return parent[x]; } void uni(int x, int y) { x = find(x), y = find(y); if(x == y) { return; } parent[x] = y; ans[x] += size[y]; size[y] += size[x]; } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); init(N); cin >> t; while(t--) { cin >> c >> x >> y; if(c == 'M') { uni(x, y); } else { if(find(x) != find(y)) { cout << -1 << "\n"; } else { cout << abs(ans[x] - ans[y]) - 1 << "\n"; } } } return 0; }

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

银河英雄传说 C++题解