1 条题解
-
0
题解:评估(assess)
题目中所求解的 ,这样我们可以不考虑绝对值。
对于 的数据,由于此时 较小,我们可以根据题意进行模拟,枚举 后直接求得答案,时间复杂度 。
对于 的数据,给出两种解法。
解法一:前缀和拆项
$(a_i - a_j)^2 = a_i^2 + a_j^2 - 2 \times a_i \times a_j$。于是我们将所求的答案拆分为 与 两部分。前一部分 与 独立,我们只需要对每一个 求出它的贡献,即
$$\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$$求和的部分可以用前缀和求解,总时间复杂度 。
解法二:值域桶计数
注意到 的值域较小,我们用桶记录每一个值出现的次数,接着考虑不同的桶之间相互的贡献。不妨设 出现的次数为 ,最后桶 之间的贡献为 。时间复杂度 ( 表示 的值域大小)。
- 1
信息
- ID
- 36
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 4
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者