首页 > 代码库 > NOI2002银河英雄传说

NOI2002银河英雄传说

//培训受的打击太大了。。。于是决定必须要每过一题写一篇题解来保证自己是不是真的懂了。。。(水题什么的就不刷了)

题目大意

  对给定的序列进行合并与查询操作,要求能够求出任意两元素之间的元素个数。

解题过程

  尼玛培训的时候不是说好了是水题吗!结果我想了快一天都没想出来。。。首先毫无疑问是用并查集,而且必然要维护附加的字段。但是就是在维护信息的选择上走上了歧途导致一直卡住。最初的想法是用一个数组before来保存某元素前面的元素个数,在合并操作时用另一个数组delta来记录序列里元素个数的变化以便于更新before值(delta记录在合并时其中一个集合的树根上),但是这种方法似乎行不通(至少我想不出来):在路径压缩过程中更新了before值之后,delta值应该马上变为0,否则下次访问该节点时会继续累加delta;但是如果马上更新delta为0,也许该节点的子节点的before值就无法更新(因为叶子节点通过读取从自己到根的路径上的delta之和来更新before值)。所以我就陷入了这样一个怪圈之中纠结了好久。最后。。。我无耻地谷歌了一下题解。。。然后就恍然大悟了。。。其实没必要设置delta数组,因为每次合并两个集合时,假设集合1的根A成了集合2的根B的子节点,那么A的before值就从0变成了集合2的元素个数,也就是说节点A的before值等于我之前所记录的delta。那么累加的时候直接累加before即可。至于集合元素个数的读取,如果不设其他任何数组,就需要遍历树找到叶子节点中最大的before值,复杂度可想而知。那么解决方法是另设一个sum数组,在合并时相加即可。

经验教训

  学会舍弃原有的方法,即使原来的算法已经调试了很久。还有就是如果真的做了很久都做不出来,就先放着留到以后或者看题解吧,长时间纠结于一道题目往往会产生烦躁心理导致影响心态、效率低下。