pku1988(Cube Stacking)

it2022-05-06  0

今天效率还不错,再接再厉^-^

总得来说,这道题目不难,但悲剧的是,我一开始理解错题意了

题意:1)n个队列,n个立方体。

        2)初始化时候每个队列有一个立方体。

        3)两个操作:m x y:将x所在的集合放到y所在的集合里面,说白了,就是将y所在集合放到x所在集合后面

                           c x:问x立方体下面有多少个立方体

呵呵,发现,其实,每次“真正”执行find()的时候,实际上都是对Union的进一步维护,只有进行一次与节点x有关的Union时,才会对x维护,而且,维护过后,x节点之上的节点也会同时被维护,并且直接挂到根节点上,这意味着之后对另一些点的维护并不会影响到已维护了的节点

还有就是那个计算,节点x之下的元素个数=x所在集合的元素个数-x之上的元素-1,很好理解吧

更具体的解释,见代码:

#include<stdio.h> #define MAXN 30010 int f[MAXN],r[MAXN],above[MAXN]; //f[]记录父节点,r[a]记录元素a所在集合的元素个数,above[a]记录a之上 的元素个数 void init()//初始化 { int i; for(i=1;i<=MAXN;i++) { f[i]=i; r[i]=1; above[i]=0; } } int find(int x) { if(x==f[x]) return f[x]; int t=find(f[x]); above[x]+=above[f[x]]; f[x]=t; return f[x]; }//查找根节点,路径压缩,同时维护above[]的值,同样,还是留意一下递归过程,你会发现一个很重要的东西 //类似于回溯,到根节点之后,回溯的时候,每一个元素都直接挂到根节点上了 //这样也就避免了重复操作,呵呵,其实这也是路径压缩的关键所在 void Union(int x,int y) { int a=find(x); int b=find(y); if(a==b) return ; above[b]=r[a]; r[a]+=r[b]; f[b]=a; }//将y所在集合挂到x所在集合,虽说是挂在元素x所在集合的后面,实际上是直接挂在根节点上 //这也引出了一个词,"逻辑上的距离",above记录节点到根节点逻辑上的距离 int main() { int i,a,b,n; char ch[2]; scanf("%d",&n); init(); for(i=1;i<=n;i++) { scanf("%s",ch); if(ch[0]=='M') { scanf("%d %d",&a,&b); Union(a,b); } else { scanf("%d",&a); printf("%d\n",r[find(a)]-above[a]-1); } } return 0; }

转载于:https://www.cnblogs.com/nanke/archive/2011/05/08/2040562.html

相关资源:算法艺术与信息学竞赛题目完全解析

最新回复(0)