洛谷题解 P1196 【[NOI2002]银河英雄传说】

男娘i 2021-12-14 14:59 224阅读 0赞

并查集大难题。

看了题解之后才有思路，调了很久很久才AC，当然要写一篇题解来纪念一下。

先来分析一下这些指令的特点，很容易发现对于每个M指令，只可能一次移动整个队列，并且是把两个队列首尾相接合并成一个队列，不会出现把一个队列分开的情况，因此，我们必须要找到一个可以一次操作合并两个队列的方法。

再来看下C指令：判断飞船i和飞船j是否在同一列，若在，则输出它们中间隔了多少艘飞船。我们先只看判断是否在同一列，由于每列一开始都只有一艘飞船，之后开始合并，结合刚刚分析过的M指令，很容易就想到要用并查集来实现。

用`fa[i]`表示飞船i的祖先节点，即其所在列的队头。

看见多次求两个点的距离的问题，便想到用前缀和来实现：开一个`g`数组，`g[i]`表示飞船i到其所在队列队头的距离，然后飞船`i`和飞船`j`之间的飞船数量即为它们到队头的距离之差减一，就是`abs(g[i]-g[j])-1`。

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

现在就差最后一步了：如何计算每个飞船到队头的距离。再来分析一下：对于任意一个飞船，我们都知道它的祖先（不一定是队头，但一定间接或直接指向队头），还知道距离它祖先的距离。对于每一个飞船，它到队头的距离，就等于它到它祖先的距离加上它祖先到队头的距离，而它的祖先到队头的距离，也可以变成类似的。可以递归实现，由于每一次更新都要用到已经更新完成的祖先到队头的距离，所以要先递归找到队头，然后在回溯的时候更新`（g[i]+=g[fa[i]]）`，可以把这个过程和`find`的函数放在一起。

完整代码:

#include<bits/stdc++.h> using namespace std; const int MAXN=30000+10; int T; int fa[MAXN],num[MAXN],g[MAXN]; inline int read() { int tot=0; char c=getchar(); while(c<'0'||c>'9') c=getchar(); while(c>='0'&&c<='9') { tot=tot*10+c-'0'; c=getchar(); } return tot; } inline int find(int k) { if(fa[k]==k)return k; int grandfa=find(fa[k]); g[k]+=g[fa[k]]; return fa[k]=grandfa; } int main() { T=read(); for(int i=1;i<=MAXN-10;i++)fa[i]=i,num[i]=1; char c; int x,y; while(T--) { cin>>c; x=read();y=read(); int fx=find(x),fy=find(y); //cout<<c<<" "<<x<<" "<<y<<endl; if(c=='M') { g[fx]+=num[fy]; fa[fx]=fy; num[fy]+=num[fx]; num[fx]=0; } else { if(fx!=fy)cout<<-1<<endl; else cout<<abs(g[x]-g[y])-1<<endl; } //for(int i=1;i<=5;i++)cout<<fa[i]<<" ";cout<<endl; } return 0; }

参考博文:[https://www.luogu.org/blog/user24518/solution-p1196][https_www.luogu.org_blog_user24518_solution-p1196]

转载于:https://www.cnblogs.com/hulean/p/10834889.html

[https_www.luogu.org_blog_user24518_solution-p1196]: https://www.luogu.org/blog/user24518/solution-p1196