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