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

并查集大难题。

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

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

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

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

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

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

上一篇:题解 P5092 【[USACO04OPEN]Cube Stacking】


下一篇:[洛谷P1525] 关押罪犯