有没有人知道这题怎么O(n)啊

kczno1 2018-03-22 20:32:40

https://loj.ac/submission/71134 这位大佬貌似就是O(n)的

共 5 条回复

ffccsc

@zjp_shadow谢谢讲解,懂了

zjp_shadow

@ffccsc 转化成期望删掉多少人,然后枚举 [l, r] 假设这段区间完全消去利用期望线性性统计答案。然后发现枚举区间位置是没有意义的,只需要枚举区间长度,这个贡献恰好就是卡特兰数。

ffccsc

@zjp_shadow 能讲详细点吗?

kczno1

懂了,谢谢

zjp_shadow

孔爷 , 似乎可以找到规律 . 也就是说 长度为 n 的序列完全可以被消除的概率是 Catlan(n / 2) / (2 ^ n)

然后用期望的线性性 计算这个序列两端的点被匹配的概率 , 直接推就行啦 ?

证明的话 , 可以用长度为 n/2 序列的进出栈顺序来理解 ? (这也就是等价于长度为 n 匹配的左右括号数量)

菜鸡的代码: https://loj.ac/submission/120876