1 条题解

  • 0
    @ 2026-11-15 13:51:54

    题目分析

    20 分

    暴力搜索即可。

    40 分

    需要挖掘一些性质,注意到可以把 aa 分成若干极长子段,每段的元素都相同。

    容易知道,每段的元素是什么并不重要,只要知道划分方式就能推出唯一的 bb。

    比较特殊的情况是除了开头的段与结尾的段,如果有长度为 22 的段,其等价于两个长度为 11 的段,对应的 bb 都是 1 1,于是直接钦定除了开头和结尾不能出现长度为 22 的段。

    考虑直接 dp,dpi,jdp_{i,j} 表示到了 ii 划分出了 jj 段,这样是 O(n3)\mathcal{O}(n^3)。

    60 分

    注意到划分出 >k>k 段的方案是等价的,因为只要求 1∼k1\sim k 在 aa 中都至少出现了一次。

    所以第二位只需要 dp 到 k+1k+1,这样是 O(n2k)\mathcal{O}(n^2 k)。

    正解

    注意到转移是标准的求一个区间的和,前缀和优化即可。时间复杂度 O(nk)\mathcal{O}(nk)。

    • 1

    信息

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