Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:总结此题可以精简到一个并查集!并且用向量的思考模式想整个过程相当简单!

Posted by vrs570540852 at 2010-12-03 22:18:58 on Problem 1182
In Reply To:Re:总结此题可以精简到一个并查集!并且用向量的思考模式想整个过程相当简单! Posted by:Magic347 at 2010-11-18 12:44:58
> 我的理解是,对于集合里的任意两个元素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有所帮助 :]

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator