1 条题解

  • 0
    @ 2026-11-15 13:45:09

    题目分析

    30 分

    显然每个后缀最多操作一次,于是暴力枚举即可,时间复杂度 O(2n)\mathcal{O}(2^n)。

    60 分

    可能存在一些复杂度较大的神奇做法。

    正解

    签到题啊,假设令 S0=0S_0=0,那么答案就是 max⁡(∑i=1n[Si≠Si−1]−1,0)\max(\sum_{i=1}^n [S_i\ne S_{i-1}]-1,0)。为什么呢?

    注意到相邻相同的字母是可以缩在一起的,那么问题变成了 01010101... 这种交替串将其变成不降串最小操作次数,这是非常简单的,从后往前依次翻转即可。

    例如 01010,先变成 01011,再变成 01000,最后变成 01111。

    • 1

    信息

    ID
    69
    时间
    1000ms
    内存
    256MiB
    难度
    4
    标签
    递交数
    1
    已通过
    1
    上传者