M_sea

洛谷2342 叠积木
题目描述约翰和贝西在叠积木。共有30000块积木,编号为1到30000。一开始,这些积木放在地上,自然地分成N堆。...
扫描右侧二维码阅读全文
29
2017/08

洛谷2342 叠积木

题目描述

约翰和贝西在叠积木。共有30000块积木,编号为1到30000。一开始,这些积木放在地上,自然地分成N堆。贝西接受约翰的指示,把一些积木叠在另一些积木的上面。一旦两块积木相叠, 彼此就再也不会分开了,所以最后叠在一起的积木会越来越高。约翰让贝西依次执行P条操作,操作分为两种:

第一种是移动操作,格式为“移动X到Y的上面”。X和Y代表两块积木的编号,意思是将X所的那堆积木,整体叠放到Y所在的那堆积木之上;

第二种是统计操作,格式为“统计Z下方的积木数量”。Z代表一块积木的编号,意思是贝西需要报告在编号为Z的积木之下还有多少块积木

请编写一个程序,帮助贝西回答每条统计问题。

传送门

算法(非完美)

用某位大佬的话——这就是一道并查集的裸题、、、
(虽然我也这么认为)
来考虑一下每种操作:
第一种操作就是合并,第二种就是统计。

如果统计循环的话肯定会超时,那我们应该怎么做呢?

维护一个数组,记录父节点
维护一个数组,记录子节点
第二问的答案即为子节点数

这样就方便的解决了第二问。

至于第一问,查找时记得路径压缩。
需要两个函数:找祖先和找晚辈。

代码(非完美)

#include <iostream>
using namespace std;
int g[30005],s[30005];
int FindF(int x) //找祖先
{
    while (g[x]!=x) 
    {
        s[g[x]]=x; 
        x=g[x];
    }
    return x;
}
int FindS(int x) //找晚辈
{
    while (s[x]!=x) {x=s[x];}
    return x;    
}
int sum(int x) //查询下面方块数
{
    if (g[x]==x) return 0;
    int ans=0;
    while (g[x]!=x)
    {
        ans++; 
        x=g[x];
    }
    return ans;
}
int main()
{
    int p;
    ios::sync_with_stdio(false);
    cin>>p;
    for (int i=1;i<=30005;i++) g[i]=i=s[i]=i; //初始化
    for (int i=1;i<=p;i++)
    {
        char c; cin>>c;
        if (c=='M')
        {
            int x,y; 
            cin>>x>>y; 
            g[FindF(x)]=FindS(y); //合并集合
            s[FindS(y)]=x;
        }
        else
        {
            int x; 
            cin>>x;    
            cout<<sum(x)<<endl; //查询输出结果
        }
    }
    return 0;    
}

算法(完美)

很可惜,上面的算法会超时。为什么?因为还是有计算,没有保存下方积木块数。
换句话说,我们要做到O(1)时间查询。
自然想到用一个数组维护下方积木数,只是较为麻烦。
用一块积木(最上面的)代表整摞积木,路径压缩
维护这一堆积木下面的积木数和这一堆数
在进行查找时要find一下,不然会WA
还有什么?记得画图理解,考虑每个函数(不要漏掉),才能理解透彻。

代码(完美)

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
using namespace std;
int root[30010]; //父节点(下面的一摞积木) 
int down[30010]; //下面的积木数  
int size[30010]; //这一摞积木数  
int find(int x)//查找父节点并路径压缩  
{
    if (root[x]!=x) 
    {
        int fa=find(root[x]);
        down[x]+=down[root[x]];
        root[x]=fa;
    }
    return root[x];
}
void merge(int x,int y) //合并积木  
{
    int r1=find(x),r2=find(y);
    if (r1!=r2) 
    {
        root[r1]=r2;
        down[r1]+=size[r2];
        size[r2]+=size[r1];
    }
    find(x); find(y); //合并后更新 
}
bool judge(int x,int y) //判断是不是在同一堆积木中  
{
    int r1=find(x),r2=find(y);
    return (r1==r2);
}
int check(int x,int y) //取答案  
{
    if (!judge(x,y)) return -1; //judge中已更新  
    else return max(down[x],down[y])-min(down[x],down[y]); //与根节点比较,取绝对值(因为会有多加) 
}
int main()
{
    ios::sync_with_stdio(false);
    for (int i=1;i<=30000;i++) //初始化 
    {
        root[i]=i;
        size[i]=1;
        down[i]=0;
    }
    int t;
    cin>>t; //输入  
    while (t--)
    {
        char c; int a,b;
        cin>>c;
        if (c=='M') //M即合并  
        {
            cin>>a>>b;
            merge(a,b);
        }
        else //C即查询  
        {
            cin>>a;
            cout<<check(a,find(a))<<endl; //要减根节点(有多算) 
        }
//        for (int i=1;i<=6;i++) printf("%d %d %d\n",root[i],down[i],size[i]); //不理解就删掉看看吧  
    }
    return 0;
}

后记

这道题的正解真的不是很好理解,但是画图+输出中间变量可以更容易理解。

最后修改:2018 年 11 月 09 日 03 : 56 PM

发表评论