同求B题第四个数据（WA了），打的暴力也是WA，不知道哪里错了。谢谢了QAQ.
2019.1 月赛题解
ultmaster edited 5 年，11 月前
花絮
这场比赛早在十二月初就开始筹备了。所有题目都是我无聊的时候想出来的。
听说 C 题跟 BZOJ 2797 撞了（很遗憾，题目见得太少了）。
题面大概有几百个毛病（根本没复查过，很抱歉）。
感谢 dream_cloud 讨论 idea，感谢 oxx1108 验题。希望大家玩得开心。
A
大致思路其实非常显然，就是找到最先坍塌的块，然后考虑这一块坍塌之后对周围的块的影响。
可以用一个优先队列维护所有的 DC 对的坍塌时间，用一个链表或者 set 维护所有的块的状态（以及最后更新的时间）。当一个块坍塌了之后，如果是会往右合并的，就用一个循环一个一个合并过去，直到不能合并为止，把最后的那个状态塞进优先队列；往左合并也是同样的道理。
这样，由于合并的总次数是 $O(n)$ 的，从而优先队列里的元素总个数也是 $O(n)$ 的，总复杂度是 $O(n \log n)$。
B
就是要选一个根，使得若干祖先和孩子的关系成立。
考虑任选一个为根，然后那些关系就是若干树上的路径。考虑 $s$ 到 $t$。
- 如果 $t$ 是 $s$ 的祖先，说明根应该在 $t$ 的子树外面。
- 否则，根应该在 $t$ 的子树里面。
因为题目已经保证有解了，我们只要把解的范围缩小就可以了。对于「在子树外面」的那些约束，我们大可以无视，最后选答案的时候选一个深度最小的就可以了；而对于在子树里面的那些约束，就更好办了，维护一个最大的历史深度就好了。实现的时候可以合二为一，直接维护答案。
可以写 LCA，或者离线搞一搞（可能需要一点小技巧）。可以做到 $O(n)$，但是带 log 也能过。输出答案稍微有点麻烦。注意输入量偏大，如果又是 cin，又是带 log，小心 TLE。
这题削了好几下，大家可以考虑一下：
- 不保证是树怎么做？
- 不保证连通怎么做？
- 不保证有解怎么做？
其实也没什么花头，只是会相当繁琐。
C
既然是原题，大家就去搜原题的题解吧。我不写了。
不是原题吗？怎么没人做啊？
D
因为题目保证一开始的句子是合法的，所以可以根据文法考察每个终结符的 $Follow$ 集合：$Follow(.) = { D, . }$，$Follow(D) = {O}$，$Follow(O)={., C}$，$Follow(C) = { O, $ $ $}$。一个终结符只能和它 $Follow$ 集合里的终结符交换，可以看到可能合法的只有 . 和 . 交换，或者 O 和 C 交换。后者交换以后再看一下对前后的 $Follow$ 的影响，发现也是不合法的。所以只有交换两个相同的符号才合法（只有可能是 . 和 .）。
或者你可以猜只有交换两个相同的符号才行，然后秒掉。（至少能过样例）
E
对于你来说，这根本不是一个概率问题，这就是一个出什么最好的问题。所以答案是 $\max i \cdot a_i \Big/ (\sum_{i=1}^6 a_i)$。
Comments
Test 4 有 50 个点……