> 什么叫做向量的思维模式？
> Orz Orz
我的理解是，对于集合里的任意两个元素a,b而言，它们之间必定存在着某种联系，

因为并查集中的元素均是有联系的，否则也不会被合并到当前集合中。那么我们

就把这2个元素之间的关系量转化为一个偏移量，以食物链的关系而言，不妨假设

a->b 偏移量0时 a和b同类

a->b 偏移量1时 a吃b

a->b 偏移量2时 a被b吃，也就是b吃a

有了这些基础，我们就可以在并查集中完成任意两个元素之间的关系转换了。

不妨继续假设，a的当前集合根节点aa，b的当前集合根节点bb，a->b的偏移值为d-1（题中给出的询问已知条件）

(1)如果aa和bb不相同，那么我们把bb合并到aa上，并且更新delta[bb]值（delta[i]表示i的当前集合根节点到i的偏移量）

    此时 aa->bb = aa->a + a->b + b->bb，可能这一步就是所谓向量思维模式吧

    上式进一步转化为：aa->bb = (delta[a]+d-1+3-delta[b])%3 = delta[bb]，（模3是保证偏移量取值始终在[0,2]间）

(2)如果aa和bb相同，那么我们就验证a->b之间的偏移量是否与题中给出的d-1一致

    此时 a->b = a->aa + aa->b = a->aa + bb->b，

    上式进一步转化为：a->b = (3-delta[a]+delta[b])%3，

    若一致则为真，否则为假。

希望可以对LS有所帮助 :]

• Re:总结此题可以精简到一个并查集！并且用向量的思考模式想整个过程相当简单！ (741) vrs570540852 2010-12-03 22:18:58
  • Re:总结此题可以精简到一个并查集！并且用向量的思考模式想整个过程相当简单！ (9) skyhacker 2010-12-07 13:36:54
• Re:总结此题可以精简到一个并查集！并且用向量的思考模式想整个过程相当简单！ (7) vrs570540852 2010-12-03 22:20:13
• 必须膜拜!!! (25) yy17yy 2010-12-28 09:05:34
• Re:总结此题可以精简到一个并查集！并且用向量的思考模式想整个过程相当简单！ (741) 20134947 2014-07-31 23:47:58