Educational Codeforces Round 105 (Rated for Div. 2) A ~ E题解

C题结论猜错了，debug了近半小时。。D的细节没考虑清楚。

A. ABC String

给 A，B，C 分配的括号状态有8种，括号匹配即可。复杂度 $O(T8n)$ 。

B. Berland Crossword

n = 1时特判。

否则，枚举四个角是否该选，那么各个边剩余的点彼此独立，可 $O(1)$ 判断。

复杂度为 $O(16T)$ 。

C. 1D Sokoban

稍作思考一下，负半轴就是翻转过去的正半轴，稍作处理可转为两个相同的子问题。

考虑正半轴的箱子 $a_1,a_2,\dots,a_n$ ，特殊点 $b_1,b_2,\dots,b_m$ ，要不将前缀的箱子都恰好推到 $b_i$ 及之前的位置，要不将前缀的箱子都恰好推到 $b_1$ 及之后的位置（只猜了这个结论，然后错了翻车了半小时= =）。

那么预处理包括每个特殊点的前缀的箱子和 $c_i$ ，然后把箱子恰好推到 $b_i - c_i + 1$ 的位置，答案即为 $[b_i-c_i+1,b_i]$ 里特殊点的个数，加上 $b_i$ 之后恰好箱子覆盖到特殊点的个数（求个后缀和）。另一种假设也是类似的求法。两者统计答案后取max。

复杂度 $O(n\log n \sim n)$ 。

D. Dogeforces

由于父节点的工资严格大于子节点，那么可以考虑从小到大合并子节点来找到祖父节点，这个祖父节点一定为直属父节点。即从下往上一层层合并来构造树。

但有一类数据会出错，比如4个叶节点的直属父节点为5，假设价值为5。如果先合并1,2得到父节点5，再合并3,4得到父节点6，此时5,6合并得到父节点7，那么父节点7的价值是5，不严格大于子节点。

解决上述问题，只需将合并的节点作为排序的第二关键字，即当价值相同时，按< 1 , 2 >，< 2 , 3 >，< 3 , 4 >来合并。当< u , v >的理想lca对应的工资w已经等于实际u,v其中一个的上属工资fu.w，那么将另一个v的上属直接设为fu即可。否则当w都大于实际u,v上属的工资，那么就新建点，然后合并u,v就行。

复杂度 $O(n^2\log n)$ 。

E. A-Z Graph

手画几个环，发现只有出现无向边时，才可能构造出点列。

具体的，当 k 是偶数，可以构造< u , v , u , v , . . . , u , v >的形式，那么需要双向边的字母相同；

当 k 是奇数，可以构造< u , v , u ,. . . , v , u > 的形式，只需要有双向边即可。

预处理会建的边，增边删边时，考虑反向边的情况即可 $O(1)$ 判断。

复杂度 $O(m\log m)$ 。