1 条题解

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

    题目分析

    30 分

    暴力即可。

    60 分

    暴力跳肯定是对的,因为集合 SS 中最多就 q−1000q-1000 个数,所以复杂度最坏 O(1000q)\mathcal{O}(1000q)。

    正解

    实际上暴力就是对的(加上记忆化)!

    考虑只有加数没有删除数字,那么对于一个固定的 kk,这个 tt 肯定是不降的,于是每次记忆化即可。

    考虑这个算法的最坏复杂度,最坏情况下肯定是先加入 1,2,...,q1,2,...,q,然后询问 1,2,...q1,2,...q,这个复杂度是调和级数级别的,所以复杂度就是 O(qlog⁡q)\mathcal{O}(q\log q)。

    • 1

    信息

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