1 条题解

  • 0
    @ 2026-11-15 19:08:58

    题目分析

    首先我们设 fif_i 表示以 ii 作为结尾的区间中总共有多少个 "bessie"。

    考虑转移。

    首先我们需要找到最近的一个 "bessie",我们可以考虑设一个 lstilst_i 表示找到的上一个 "bessie" 的前 ii 项的起始位置。

    举个例子,字符串 "bessie" 就有 lsti=1 (1≤i≤6)lst_i = 1\ (1 \le i \le 6)。

    那这个怎么算呢?我们找到一个字符 "bessie" 的哪一位,设为 xx 位,则它的开头显然是 lstx−1lst_{x-1}。

    接下来,我们把贡献分成两份,一份是上一个 "bessie" 的贡献,一份是其他 "bessie" 的贡献。

    后者的贡献我们发现就是 flst6−1f_{lst_{6}-1},因为往后的字符串与当前的这个 "bessie" 不可以同时出现。

    对于当前的字符串,我们发现对于 l∈[1,lst6]l \in [1, lst_6] 而言都可以包含当前这个 "bessie",因此 "bessie" 总数会增加 lst6lst_6。

    得转移方程:

    fi=flst6−1+lst6 f_i = f_{lst_6 - 1} + lst_6

    而问题问的是所有区间,所有我们需要把它们加起来,即: ans=∑i=1nfi ans = \sum_{i=1}^{n} f_i

    • 1

    信息

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