1 条题解

  • 0
    @ 2026-11-15 11:56:44

    题解:评估(assess)

    题目中所求解的 ∣ai−aj∣2=(ai−aj)2|a_i - a_j|^2 = (a_i - a_j)^2,这样我们可以不考虑绝对值。

    对于 40%40\% 的数据,由于此时 nn 较小,我们可以根据题意进行模拟,枚举 i,ji,j 后直接求得答案,时间复杂度 O(n2)O(n^2)。

    对于 100%100\% 的数据,给出两种解法。

    解法一:前缀和拆项

    $(a_i - a_j)^2 = a_i^2 + a_j^2 - 2 \times a_i \times a_j$。于是我们将所求的答案拆分为 ai2+aj2a_i^2 + a_j^2 与 −2×ai×aj-2 \times a_i \times a_j 两部分。前一部分 ii 与 jj 独立,我们只需要对每一个 ii 求出它的贡献,即

    $$\sum_{i=1}^{n-1} \sum_{j=i+1}^n a_i^2 + a_j^2=\sum_{i=1}^n a_i^2 \times (n-1)$$

    对于后一部分

    $$\sum_{i=1}^{n-1} \sum_{j=i+1}^n -2 \times a_i \times a_j = \sum_{i=1}^{n-1} -2 \times a_i \times \sum_{j=i+1}^n a_j$$

    jj 求和的部分可以用前缀和求解,总时间复杂度 O(n)O(n)。

    解法二:值域桶计数

    注意到 aia_i 的值域较小,我们用桶记录每一个值出现的次数,接着考虑不同的桶之间相互的贡献。不妨设 ii 出现的次数为 cic_i,最后桶 i,ji,j 之间的贡献为 (i−j)2×ci×cj(i-j)^2 \times c_i \times c_j。时间复杂度 O(m2)O(m^2)(mm 表示 aia_i 的值域大小)。

    • 1

    信息

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