[蓝桥杯 2022 省 A] 求和——前缀和,差分

简介: [蓝桥杯 2022 省 A] 求和——前缀和,差分

蓝桥杯 2022 省赛 A 组 C 题

题目描述

给定 n 个整数 a1,a2,⋯,an, 求它们两两相乘再相加的和,即

S=a1⋅a2+a1⋅a3+⋯+a1⋅an+a2⋅a3+⋯+an−2⋅an−1+an−2⋅an+an−1⋅an


输入格式

输入的第一行包含一个整数 n 。

第二行包含 n 个整数 a1,a2,⋯an


输出格式

输出一个整数 S,表示所求的和。请使用合适的数据类型进行运算。

输入输出样例

输入 #1复制

4

1 3 6 9

输出 #1复制

117

说明/提示

对于 30 \%30% 的数据, 1001≤n≤1000,1≤ai≤100 。

对于所有评测用例, 1≤n≤2×10^5,1≤ai≤1000 。


暴力求解可以获得30%的分数:

#include<cstdio>
#include<iostream>
using namespace std;
typedef long long LL;
int main()
{
    LL sum = 0;
    int n;
    cin >> n;
    int g[200020];
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &g[i]);
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 1 + i; j < n; j++)
        {
            sum += g[i] * g[j];
        }
    }
    cout << sum << endl;
    return 0;
}

使用前缀和和差分(不超时代码:

#include<cstdio>
#include<iostream>
using namespace std;
typedef long long LL;
int main()
{
    LL sum = 0;
    int n;
    cin >> n;
    int g[200020];
    LL s[200020] = { 0 };
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &g[i]);
        s[i] = s[i - 1] + g[i];
    }
    for (int i = 1; i <= n; i++)
    {
        sum += g[i] * (s[n] - s[i]);
    }
    cout << sum << endl;
    return 0;
}
目录
打赏
0
0
0
0
4
分享
相关文章
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-462 求和
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-462 求和
72 0
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-444 算法训练 求和问题
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-444 算法训练 求和问题
104 1
第十四届蓝桥杯集训——练习解题阶段(无序阶段)- 基础练习 序列求和
第十四届蓝桥杯集训——练习解题阶段(无序阶段)- 基础练习 序列求和
74 0
蓝桥杯vip测试题系统-数组求和(解题思路以及解题代码,手画思路图虽然丑丑的)
蓝桥杯vip测试题系统-数组求和(解题思路以及解题代码,手画思路图虽然丑丑的)
90 0
《蓝桥杯每日一题》差分·Acwing3729. 改变数组元素
《蓝桥杯每日一题》差分·Acwing3729. 改变数组元素
88 0
《蓝桥杯每日一题》差分·Acwing3729. 改变数组元素
《蓝桥杯每日一题》 前缀和·Acwing 3956. 截断数组
《蓝桥杯每日一题》 前缀和·Acwing 3956. 截断数组
107 0
蓝桥杯 ADV_303 数组求和
蓝桥杯 ADV_303 数组求和
161 0
蓝桥杯 入门训练 序列求和 (Java)
蓝桥杯 入门训练 序列求和 (Java)
184 0
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问