Codeforces Round #278 (Div.1)
终于在这个星期内将这套题干掉了，果然，中国人出的题目就是丧心病狂。
首先，贴上出题人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:
评论 (0)
