Codeforces Round #278 (Div.1)

VictorWonder posted @ 2014年12月05日 20:42 in Codeforces with tags 树链剖分 Tarjan算法 树上查询 解题报告 , 1031 阅读
终于在这个星期内将这套题干掉了,果然,中国人出的题目就是丧心病狂。
首先,贴上出题人saffah大神的命题报告链接:
呃,忽然发现,这好像是我第二次在题解中贴saffah大神的题解链接了……好吧,虽然别人已经有题解了,但觉得还是自己总结一下比较好。
 
Problem 2A
直接枚举就行了,我当时以为最多枚举10次就可以了,但是saffah的报告中已经证明了,当目前是-8层时,需要枚举16次,反正都一样。
 
Problem 2B
这道题目很难,或者说是很麻烦,我开始的想法是分类讨论各种情况,然后如果最小数是x的话,最大数就是3x,接着再各种特判……后来看了题解之后才知道完全写麻烦了,很明显,最后的四个数为x,y,4x-y,3x,所以,枚举x和y就行了。
 
Problem 1A
也是暴力题,不过开始的时候没有考虑完全,在第七个点WA了很多次。首先攻击必须能够破防,然后在这样的基础上开始枚举HP、攻击和防御,反正数据范围极小。
 
Problem 1B
很明显的DP题,但是对于我这样的DP渣来说还是太难了,果断翻题解(哎,我就是不停翻题解的命),saffah表示可以用单调队列优化到O(n),但是思考了十多分钟,硬是没有想出来怎么用单调队列搞,然后决定还是打线段树,反正也能过2333
 
Problem 1C
神题,如果不看题解,我估计是永远都做不出来了,首先可以知道,大于4的合数都是不合法的(证明见taorunz和saffah的题解),其次,最后构造起来的数列的前缀积肯定是1,2,3..,n-1,0,(证明同样见题解),然后,对于1和4特判,其他的就用扩展欧几里德算法求就行了。
 
Problem 1D
我采用了题解中给出的三种办法中的第二种,也就是对询问分块,然后随便定了个size,接着就是暴力。
 
Problem 1E
这才是真正的重头戏,毕竟前面几道题目saffah大神的命题报告中已经写得很详细了,这道题目虽然也有讲,但对于我这样的蒟蒻来说还是太含糊了,所以感觉要好好地讲一讲,顺便自己也好好总结一下。
题目大意是这样的:有一张n个结点和m条边的带权无向图(为什么不是树……各种怨念……),进行两种操作,1、将一个点的点权改掉 2、查询两个点之间的所有简单路径上权值最小的点的点权
如果是树的话,我们可以有一万种办法搞出答案,我最喜欢的做法就是树链剖分了。所以,我们的想法就是将这张图变成一棵树,然后就是求双连通分量缩点。于是临时学习了一下双连通分量的Tarjan算法。
Tarjan算法的实现就不讲了,也不是什么麻烦的东西,我习惯用dfn[]表示时间戳,low[x]表示x或x的子树能够追溯到的最早的栈中节点的次序号。
那么,如果low[to[k]]>dfn[x],则表示x的子树是一个独立的子图,是一个双连通分量,如果low[to[k]]==dfn[x],则表示x也属于这个双连通分量。求出双连通分量之后就进行缩点建树,然后树链剖分……
我花了大概两个半小时的时间将以上的内容实现(ORZ当场码了15k代码1.5h AC此题的anta),然后,就发现了一个很严重的问题,割点的归属不明确。
我本来在tarjan的过程中,规定,如果low[to[k]]>=dfn[x],那么将点x也划分到这个BCC(Biconnected components)中,但是,这个时候,点x还是在栈当中的,那么,当x属于另外一个BCC的时候,我又把x给划定到新的BCC中去了,结果导致查询的时候各种混乱出错。
而且,建树也很不科学,对于第二个样例,建出来的图是这样的1-2-3,其中,1和2的割点与3是相连接的(在同一个BCC里面),但是,查询的话,只会查询1-2,而把3排除了。
我赶紧开始补救,重新开始建树,花了大概半个多小时的时间将Tarjan部分重新打好,改出来之后,每个块都有一个顶端割点和上一块相连,但是这个割点是属于块x的,也就是说,对于相连的两个块x和y,假设y在新建的树中是x的父结点,那么y和x之间肯定有一个割点相连,而这个割点被我划定到了块x中。但是这么一来又出现了一个新的问题,查询的时候无法判定一个割点是否需要查询,会出现一个割点不需要查询,却被查询了,需要查询的时候,却没有被查询。
我通读了saffah大神的题解,发现了这么一句话"强行让割点成为根,强行让割点的孩子都是块,让块的孩子都是割点",花了大概一个小时的时间,终于理解透了其中的关键并修改了代码。我把新图中的点分为两类,块结点和割点结点,块结点表示这个点在原图中属于同一个块,割点结点就是一个单独的特点。
首先,不管1在图中是不是割点,我都假定它是割点,把它拎出来,建了一个割点结点。一个块当中可能含有多个割点,我假设其中一个割点是顶端割点,当作是这个块结点的父亲结点,其他的割点结点都是这个块的子节点,顶端割点则归到顶端割点的父亲块结点中去,那么就实现了saffah大神报告中所说的了,查询的时候,如果最后LCA是块结点,那么再查询一下其顶端割点。
照说应该是什么问题都没有了,但是还是出了问题,这一次的问题在于链剖上。因为树链剖分查询的是一个个结点,但是,现在,有一些结点是块结点,也就是说,囊括了很多的结点,查询就会出现问题,我用st[]数组表示一个结点所属的块开始的位置,用ed[]数组表示一个结点所属的块结束的位置,一个块中的所有节点都有连续的dfs序(我还是习惯用dfn[]储存),那么,割点结点怎么办?我规定,如果x是割点结点,则st[x]是其子节点(当然是重链上的那个子节点)的st[],而ed[x]则是ed[fa[x]],那么查询的时候,某一段是割点结点的话,就会主动转化成相邻的块结点,但是,有一点注意的是,如果深度小的结点是割点结点的话,那么要额外查询一下这个结点,否则就会将其忽略。
这下该万事大吉了吧?还有一些细节没有解决,那就是内存问题。实际上,每一个块结点都等于一个新建的虚点,也就是说,原先有100000个点的话,那么新图上的点的个数可能会更多……扔到Codeforces上测,结果是MLE?虽然算来算去都没有爆内存,我还是将数组开小了一些,然后就RE了……坑了大概一个小时才知道,MLE是因为数组开得还是不够大……于是将所有数组都开到了五十万,终于AC了。
从昨天晚上的自修课开始,到今天,零零散散加起来,大概花费了六个小时的时间,终于AC了,真是太感人了TAT,终于在崩溃前搞出来了!(虽然,可能还会有些漏洞,但至少我现在是找不出来了,所以就不管了……)
 
Code:

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter