3 条题解

  • 2
    @ 2024-2-23 20:18:58
    • 1
      @ 2024-2-16 10:21:42

      考虑先把所有 * 替成 (,然后这样还不满足前缀非负的肯定不对。

      再把 * 替换成 ),这样还不满足后缀非负的也不对。

      考虑为什么满足这两个就对了。首先肯定将一段前缀 * 替成 (,后缀替成 ),由于满足两个条件,最终必然有前后缀和非负。再考虑能否满足总和为 0。由于可以有空串,在【* 替成 (】的情况下依次将后缀 * 改成 ),最后奇偶性问题用一个空串解决。

      所以问题变成了求 (x,y)(x,y) 个数使得 ryxylxr_y\le x\le y\le l_x。随便扫描线。倒序枚举 yy 即可。

      • 1
        @ 2024-2-11 13:25:39

        SS 中有 ll(\texttt (rr)\texttt )ss*\texttt *,这个问题的判定等价于:

        • 对于 SS 的每个前缀有 l+srl + s \geq r
        • 对于 SS 的每个后缀有 r+slr + s \geq l

        如果有能够简洁严谨证明这个结论的,可以 qq 私信我 /kel。

        但是无论如何,这个过对拍了,所以我们对于每个 ll 可以扫描线出最大的合法 rr,对于每个 rr 同理,转化为经典的二维数点问题。

        O(nlogn)\mathcal O(n\log n)

        • 1

        信息

        ID
        798
        时间
        1000ms
        内存
        256MiB
        难度
        5
        标签
        (无)
        递交数
        14
        已通过
        4
        上传者