1 条题解

  • 0
    @ 2026-11-15 17:07:44

    题目分析

    处理前缀和然后对所有前缀和 sumsum 模 pp,于是原题的合并 [l,r][l,r] 使得最后剩下的元素可以被 pp 整除,就等价为了判断 sum[l−1]sum[l-1] 是否等于 sum[r]sum[r]。

    接着考虑 dp。

    设 f[i]f[i] 表示序列 1∼i1\sim i 的答案为多少。

    显然如果要合并第 ii 个元素的话那么直到合出符合条件的元素才停(不然没必要合)。

    那么就有 f[i]=max⁡(f[i−1],f[pre[i]]+1)f[i]=\max(f[i-1],f[pre[i]]+1)。

    其中 pre[i]pre[i] 表示与第 ii 个前缀和相等的前一个的前缀和的位置,当然如果没有 pre[i]pre[i] 的话 f[i]=f[i−1]f[i]=f[i-1] 即可。

    • 1

    信息

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