现在的位置: 首页 > 综合 > 正文

排数游戏

2017年12月23日 ⁄ 综合 ⁄ 共 487字 ⁄ 字号 评论关闭

有n个数排在一行,数字i的位置为第i列(初始时每个数自称一列),游戏有两种操作:

1.合并指令 M i  j, 让数字i所在的整条列作为整体接到数字j 所在列的列尾。显然队列是由处于同一列的一个或多个数字组成的。合并的结果会使该列增长。

2.询问指令 C i  j. 询问数字i和数字j是否在同一列中,如果是,那么他们之间相隔多少个数字?不在一列则回答-1.

 

直觉当然是用并查集,但是单纯的并查集可能是n个节点的树退化成一条链,这样将极大减小查询的效率,因此应当使用路径压缩的并查集算法

 

初始化三个数组: fa[ n ] , len [n ] 表示所在的队列的长度, loc [ n ] 表示在队列中的相对位置。

 

路径压缩可以在查询也可以在合并的操作中进行,这里我们选择在查询中进行,这使得查找和合并的复杂度均为 O(logn);

而在合并中进行的话,查找和合并的复杂度分别为O(1)和O(logn)。

 

查询的时候,从待查询的点x开始向上寻找,需要完成两个操作:将x的父亲设置为树根父亲的孩子;更新loc[x];

合并的时候,先查找i,j 的根节点fi ,fj , 两个操作: loc [i] = len [j] , len [i] += len[j]

【上篇】
【下篇】

抱歉!评论已关闭.