银河英雄传说

题目

在这里插入图片描述

题解

两艘飞船之间的飞船数量，其实就是艘飞船之间的距离，那么，这就转换为了一个求距离的问题。两艘飞船都是在队列里的，最简单的求距离的方法就是前后一个一个查找，但这个方法太低效，会超时。看见多次求两个点的距离的问题，便想到用前缀和来实现：开一个 $d []$ 数组， $d [i]$ 表示飞船i到其所在队列队头的距离(相当于把飞船们看成一条链，然后 $d [i]$ 实际上记录的的节点 $i$ 的深度)，然后飞船 $i$ 和飞船 $j$ 之间的飞船数量即为它们到队头的距离之差减一，就是 $a b s (d [i] - d [j]) - 1$ 。

现在我们已经知道，使用并查集合并两个队列时只改变队头的祖先，而这个队列里其它飞船的祖先还是它原来的队头，并没有更新，所以这个队列里的其它飞船在队列合并之后，仍然可以找到它原来的队头，也就可以使用它原来队头的数据，因此，在每次合并的时候，只要更新合并前队头到目前队头的距离就可以了，之后其它的就可以利用它来算出自己到队头的距离。

对于原来的队头，它到队头的距离为 $0$ ，当将它所在的队列移到另一个队列后面时，它到队头的距离就是排在它前面的飞船数，也就是合并前另一个队列的飞船数量。因此，就知道该怎样实现了，我们再建一个数组 $s i z e [i]$ ， $s i z e [i]$ 表示以 $i$ 为队头的队列的飞船数量，初始时都是 $1$ ，在每次合并的时候， $x$ 为合并前飞船 $i$ 的队头， $y$ 为合并前飞船j的队头，每次合并时，先更新 $d [x]$ ，即给它加上 $n u m [y]$ ，然后开始合并，即 $f a [x] = y$ ，最后更新 $s i z e$ ， $s i z e [y] + = s i z e [x]$ ; $n u m [x] = 0$ 。

对于任意一个飞船，我们都知道它的祖先（不一定是队头，但一定间接或直接指向队头），还知道距离它祖先的距离。对于每一个飞船，它到队头的距离，就等于它到它祖先的距离加上它祖先到队头的距离，而它的祖先到队头的距离，也可以变成类似的。可以递归实现，由于每一次更新都要用到已经更新完成的祖先到队头的距离，所以要先递归找到队头，然后在回溯的时候更新（ $d [i] + = d [f a [i]]$ ），可以把这个过程和查找队头的函数放在一起。

code

#include <algorithm> #include <cctype> #include <cmath> #include <complex> #include <cstdio> #include <cstring> #include <deque> #include <functional> #include <list> #include <map> #include <iomanip> #include <iostream> #include <queue> #include <set> #include <stack> #include <string> #include <vector> #include <bitset> #define clean(x, y) memset(x, y, sizeof(x)) const int maxn = 3e4 + 110; const int inf = 0x3f3f3f3f; typedef long long LL; using namespace std; template <typename T> inline void read(T &s) { 
    s = 0; T w = 1, ch = getchar(); while (!isdigit(ch)) { 
    if (ch == '-') w = -1; ch = getchar(); } while (isdigit(ch)) { 
    s = (s << 1) + (s << 3) + (ch ^ 48); ch = getchar(); } s *= w; } int T; int d[maxn]; int fa[maxn]; int size[maxn]; const int n = 30000; inline int get(int k) { 
    if (fa[k] == k) return k; int root = get(fa[k]); d[k] += d[fa[k]]; fa[k] = root; return fa[k] = root; } inline void merge(int x, int y) { 
    int a = get(x), b = get(y); fa[a] = b, d[a] = size[b]; size[b] += size[a]; } int main() { 
    read(T); for (int i = 1; i <= 30000; ++i) fa[i] = i, size[i] = 1; while (T--) { 
    char ch; while (1) { 
    ch = getchar(); if (ch != ' ' || ch != '\n') break; } int x, y; read(x), read(y); if (ch == 'M') merge(x, y); else { 
    int a = get(x), b = get(y); if (a != b) printf("-1\n"); else printf("%d\n", abs(d[x] - d[y]) - 1); } } return 0; }

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

银河英雄传说

题目

题解

code

相关推荐