【题解】蓝桥杯2022年第十三届省赛(第二场)真题-求和
2022 蓝桥 题解 求和 真题 省赛 第十三届
2023-06-13 09:16:28 时间
给定 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,表示所求的和。请使用合适的数据类型进行运算。
4 1 3 6 9
117
对于 30% 的数据,1 ≤ n ≤ 1000,1 ≤ ai ≤ 100。
对于所有评测用例,1 ≤ n ≤ 200000,1 ≤ ai ≤ 1000。
题目解析
这道题,给我的第一印象是用前缀和。 如何处理相乘关系? 便输入边计算?时间复杂度在O(n^3),优化一下可以到n^2 下面是代码。
#include <iostream>
#include "algorithm"
#include "string.h"
using namespace std;
int main(){
int n;
cin>>n;
int a[n+1],b[n+1][n+1],c[n+1][n+1];
memset(a,0,sizeof a);
memset(b,1,sizeof b);
memset(c,0,sizeof c);
for (int i = 1; i <= n; ++i) {
cin>>a[i];
}
for (int i = 1; i <= n; ++i) {
for(int j=i;j<=n;++j){
b[i][j]=a[i]*a[j];//b[i][j]表示a[i]*a[j]的积
c[i][j]=c[i][j-1]+b[i][j];//前缀和
if(j==i)c[i][j]=c[i-1][n];//当a[i]开始变换时,存储值转移
}
}
cout<<c[n][n];
}
当然,这样子做空间复杂度太大了,我们还可以优化空间复杂度,没错,就是用滚动数组。
#include <iostream>
#include "string.h"
using namespace std;
int a[200005],b[2][200005],c[2][200005];
int main(){
int n;
cin>>n;
memset(a,0,sizeof a);
memset(b,1,sizeof b);
memset(c,0,sizeof c);
for (int i = 1; i <= n; ++i) {
cin>>a[i];
}
for (int i = 1; i <= n; ++i) {
for(int j=i;j<=n;++j){
b[i&1][j]=a[i]*a[j];
c[i&1][j]=c[i&1][j-1]+b[i&1][j];
if(j==i)c[i&1][j]=c[(i-1)&1][n];
}
}
cout<<c[n&1][n];
}
当然,时间复杂度还是有点大。 我们不难发现,我们每次可以提一个a[i]出来,那么每次计算的都是一个子前缀和,那么这样的话就很好办了,看代码
#include <iostream>
using namespace std;
long long a[200005];
long long b[200005];
int main(){
int n;
cin>>n;
for (int i = 1; i <= n; ++i) {
cin>>b[i];
a[i]=a[i-1]+b[i];
}
long long sum=0;
for(int i=1;i<=n;i++){
sum+=b[i]*(a[n]-a[i]);
}
cout<<sum;
}
相关文章
- pycharm如何配置anaconda环境_2022年冬奥会在哪举行
- 2022-08-26:用一个大小为 m x n 的二维网格 grid 表示一个箱子 你有 n 颗球。箱子的顶部和底部都是开着的。 箱子中的每个单元格都有一个对角
- HStreamDB Newsletter 2022-08|端到端压缩提升读写性能、HStream Cloud 即将上线
- MQTT X Newsletter 2022-08 | v1.8.2 发布、支持使用 Docker
- 2022-11-22:小美将要期中考试,有n道题,对于第i道题, 小美有pi的几率做对,获得ai的分值,还有(1-pi)的概率做错,得0分。 小美总分是每道题获
- 【愚公系列】2022年09月 微信小程序-three.js绘制多维旋转正方体
- 2022蓝桥杯(c/c++ B组)-刷题统计
- .NET周报【12月第1期 2022-12-08】
- Linux 赢了!2022 年开发者使用率已达 40%,甩 macOS 一大截
- 2022-12-08:给定n棵树,和两个长度为n的数组a和b i号棵树的初始重量为a[i],i号树每天的增长重量为b[i] 你每天最多能砍1棵树,这天收益 =
- 2022蓝桥杯(c/c++ B组)-刷题统计
- Changes in GreatSQL 8.0.25-16(2022-5-16)
- origin软件下载2022版(中文正式版) 数据分析软件Origin 2023安装