银河英雄传说

题目

银河英雄传说

题解

先来分析一下这些指令的特点，很容易发现M指令，C指令要用并查集来实现。
并查集的基本操作我就不bb了。

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

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

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

对于任意一个飞船，我们都知道它的祖先（不一定是队头，但一定间接或直接指向队头），还知道距离它祖先的距离。对于每一个飞船，它到队头的距离，就等于它到它祖先的距离加上它祖先到队头的距离，而它的祖先到队头的距离，也可以变成类似的。可以递归实现，由于每一次更新都要用到已经更新完成的祖先到队头的距离，所以要先递归找到队头，然后在回溯的时候更新（ $d[i] += d[fa[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

相关推荐