1 条题解

  • 0
    @ 2026-11-15 13:56:23

    题目分析

    30 pts

    暴力枚举,复杂度 O(n3)O(n^3)。即枚举以 ii 开头,以 jj 结尾的区间,并 O(n)O(n) 求和

    60 pts

    预处理出前缀和数组 sum[i]sum[i],同样还是枚举区间,求和的复杂度降到了 O(1)O(1),总的复杂度为 O(n2)O(n^2)

    100 pts

    考虑每一个数会被多少个区间包括。

    例如:33 个数 [1,2,3][1,2,3]。包括 11 的区间有 [1,1],[1,2],[1,3][1,1], [1,2], [1,3],包括 22 的区间有 [1,2],[1,3],[2,2],[2,3][1,2],[1,3],[2,2],[2,3] 共四个。

    对于每个位置 ii,包含 A[i]A[i] 的区间共有 i∗(n−i+1)i*(n-i+1) 个,所以 A[i]A[i] 被统计了 i∗(n−i+1)i*(n-i+1) 次。

    用这个方法计算,时间复杂度为 O(n)O(n)。

    • 1

    信息

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