题解 P5092 【[USACO2004OPEN]Cube Stacking 方块游戏】

· · 题解

就像NOIP2018模仿POI一样

USACO2004居然copyNOIP2002的题

而且还简化了......

这算是模板题吧，相信大家都是来学习并查集的相关知识的，那我就从头开始讲，以基础知识为主

解题思路：带权并查集+路径压缩

用dis数组储存某一节点到他所在队列队首的距离

Part I 带权并查集

我们用fa[i]数组表示i节点的父亲，初始化为i 若某一个节点的fa等于他自己（fa[i]=i），说明这个节点还没有被移动过，他就是第i队列的队首 于是得到find函数

int find(int x)
{
    if (fa[x]==x) return x;
    return find(fa[x]);
}

同时，用dis[i]表示i节点到他所在队列队首的距离，初始化为0。length[i]表示第i队列的长度（显然这一队列的队首为i），初始化为1。当移动X队列到Y后时，则有：

fa[x]=fa[y],dis[x]=length[y],length[y]+=length[x]

注意：我们已无法将其他队列移动到原x队列，故没有必要将length[x]改为0

于是得到move函数

void move(int x,int y)
{
    int fx=find(x);
    int fy=find(y);
    fa[fx]=fy;
    dis[fx]+=length[fy];    
    length[fy]+=length[fx];
}

那么check函数就简单啦

void check(int x)
{
    int ffx=find(x); 
    printf("%d\n",dis[x]);
}

以上程序整合后，期望得分60分。60%AC+40%TLE

那么，我们该如何优化呢？

Part II 路径压缩

我们发现，当某一节点x在另一节点y上方，那么他、它永远在y上方，而且两点间距恒定。（因为我们不能把其他队列插入到它们中间）

利用这个性质，我们进行路径压缩

举个例子

fa[2]=1,fa[3]=2,fa[4]=3; 任意两点间距为1

压缩为：

fa[2]=1,dis[2]=1,fa[3]=1,dis[3]=2,fa[4]=1,dis[4]=3

这个过程我们用回溯实现，在一步步找到队列队首后，一步步原路返回，把每一节点的fa都改为队首，并相应的改变dis即可。于是得到优化后的find函数

int find(int xx)
{
    if (fa[xx]==xx) return xx;
    int father=find(fa[xx]);
    dis[xx]+=dis[fa[xx]];
    fa[xx]=father;
    return father;
}

完整代码，检验后AC

#include<cstdio>
#include<iostream>
#include<cmath> 
#define num 30001
using namespace std;
int n,fa[30005],dis[30005],length[30005];
int read()
{
    int x=0,f=1; char c=getchar();
    while (c<'0' || c>'9') {if (c=='-') f=-1; c=getchar();}
    while (c>='0'&&c<='9') {x=(x<<3)+(x<<1)+(c^48); c=getchar();}
    return x*f;
}
int find(int xx)
{
    if (fa[xx]==xx) return xx;
    int father=find(fa[xx]);
    dis[xx]+=dis[fa[xx]];
    fa[xx]=father;
    return father;
}
void move(int x,int y)
{
    int fx=find(x);
    int fy=find(y);
    fa[fx]=fy;
    dis[fx]+=length[fy];    
    length[fy]+=length[fx];
}
void check(int x)
{
    int ffx=find(x); 
    printf("%d\n",dis[x]);
}
int main()
{
    n=read();
    for (int i=1;i<=num;i++) fa[i]=i;
    for (int i=1;i<=num;i++) length[i]=1;
    for (int w=1;w<=n;w++)
    {
        char c; cin>>c;
        int x=read();
        if (c=='M')
        {
            int y=read(); 
            move(x,y);
        }
        if (c=='C') check(x);
    }
    return 0;
}

最后说明几点：

1、没有必要关注fa[i]到底是i节点的上几位，因为dis数组随之变化，加上上述性质，他已经覆盖了中间区域。

2、蒟蒻写题解，有bug疏漏请大家不要喷，有问题可以在评论区提问，我会常常关注。最后希望题解对大家有用，祝大家AC此题，AK IOI。

3、如有需Pascal代码请在评论区回复。