2019.1 月赛题解

ultmaster edited 5 年,2 月前

花絮

这场比赛早在十二月初就开始筹备了。所有题目都是我无聊的时候想出来的。

听说 C 题跟 BZOJ 2797 撞了(很遗憾,题目见得太少了)。

题面大概有几百个毛病(根本没复查过,很抱歉)。

感谢 dream_cloud 讨论 idea,感谢 oxx1108 验题。希望大家玩得开心。

A

大致思路其实非常显然,就是找到最先坍塌的块,然后考虑这一块坍塌之后对周围的块的影响。

可以用一个优先队列维护所有的 DC 对的坍塌时间,用一个链表或者 set 维护所有的块的状态(以及最后更新的时间)。当一个块坍塌了之后,如果是会往右合并的,就用一个循环一个一个合并过去,直到不能合并为止,把最后的那个状态塞进优先队列;往左合并也是同样的道理。

这样,由于合并的总次数是 $O(n)$ 的,从而优先队列里的元素总个数也是 $O(n)$ 的,总复杂度是 $O(n \log n)$。

B

就是要选一个根,使得若干祖先和孩子的关系成立。

考虑任选一个为根,然后那些关系就是若干树上的路径。考虑 $s$ 到 $t$。

因为题目已经保证有解了,我们只要把解的范围缩小就可以了。对于「在子树外面」的那些约束,我们大可以无视,最后选答案的时候选一个深度最小的就可以了;而对于在子树里面的那些约束,就更好办了,维护一个最大的历史深度就好了。实现的时候可以合二为一,直接维护答案。

可以写 LCA,或者离线搞一搞(可能需要一点小技巧)。可以做到 $O(n)$,但是带 log 也能过。输出答案稍微有点麻烦。注意输入量偏大,如果又是 cin,又是带 log,小心 TLE。

这题削了好几下,大家可以考虑一下:

其实也没什么花头,只是会相当繁琐。

C

既然是原题,大家就去搜原题的题解吧。我不写了。

不是原题吗?怎么没人做啊?

D

因为题目保证一开始的句子是合法的,所以可以根据文法考察每个终结符的 $Follow$ 集合:$Follow(.) = { D, . }$,$Follow(D) = {O}$,$Follow(O)={., C}$,$Follow(C) = { O, $ $ $}$。一个终结符只能和它 $Follow$ 集合里的终结符交换,可以看到可能合法的只有 .. 交换,或者 OC 交换。后者交换以后再看一下对前后的 $Follow$ 的影响,发现也是不合法的。所以只有交换两个相同的符号才合法(只有可能是 ..)。

或者你可以猜只有交换两个相同的符号才行,然后秒掉。(至少能过样例)

E

对于你来说,这根本不是一个概率问题,这就是一个出什么最好的问题。所以答案是 $\max i \cdot a_i \Big/ (\sum_{i=1}^6 a_i)$。

Comments

xu_mengnan

请问可以看下数据吗?或者有标程吗?C wa21,不知道哪里不对。谢谢了

hyx1999

同求B题第四个数据(WA了),打的暴力也是WA,不知道哪里错了。谢谢了QAQ.

ultmaster

Test 4 有 50 个点……

shutouchfish

请问一下B题的第四个数据(WA了)可以看一下吗,不知道哪里不对。谢谢了