【蓝桥杯每日一题】求和——前缀和

news/2024/12/25 1:43:13/

求和

蓝桥杯每日一题 2024-12-17 求和 前缀和

题目大意

给定 n n n 个整数 a 1 , a 2 , … , a n a_1, a_2, \ldots, a_n a1,a2,,an,求它们两两相乘再相加的和,即:

S = a 1 ⋅ a 2 + a 1 ⋅ a 3 + … + a 1 ⋅ a n + a 2 ⋅ a 3 + … + a n − 2 ⋅ a n − 1 + a n − 2 ⋅ a n + a n − 1 ⋅ a n S = a_1 \cdot a_2 + a_1 \cdot a_3 + \ldots + a_1 \cdot a_n + a_2 \cdot a_3 + \ldots + a_{n-2} \cdot a_{n-1} + a_{n-2} \cdot a_n + a_{n-1} \cdot a_n S=a1a2+a1a3++a1an+a2a3++an2an1+an2an+an1an

解题思路

将这个求和公式转化一下就变成了 : S = a 1 ⋅ ( a 2 + a 3 + … + a n ) + a 2 ⋅ ( a 3 + … + a n ) + a n − 2 ⋅ ( a n − 1 + a n ) + a n − 1 ⋅ a n S = a_1 \cdot ( a_2 + a_3 + \ldots + a_n) + a_2 \cdot (a_3 + \ldots + a_n) + a_{n-2} \cdot (a_{n-1} + a_n) + a_{n-1} \cdot a_n S=a1(a2+a3++an)+a2(a3++an)+an2(an1+an)+an1an

对于括号里的这些值的和就表示某个区间的前缀和

Accepted
#include <bits/stdc++.h>
using namespace std;typedef long long ll;
const int N = 200000;
ll a[N],b[N];
ll n;int main()
{cin>>n;for(int i = 1;i <= n;i++) {cin>>a[i];b[i] = b[i-1] + a[i];}ll sum = 0;for(int i = 1;i < n;i++) {sum += a[i] * (b[n]-b[i]);}cout<<sum<<endl;return 0;
}
思考

这道题算是前缀和的简单应用吧,学过前缀和就可以!

备注

想要一起备赛的同学可以评论区或私信留言!


http://www.ppmy.cn/news/1557877.html

相关文章

金融租赁系统的发展与全球化战略实施探讨

内容概要 金融租赁系统的演变并非一帆风顺&#xff0c;像一场跌宕起伏的电影。首先&#xff0c;咱们得看看它的起源及现状。随着经济的快速发展&#xff0c;金融租赁逐渐作为一种灵活的融资手段崭露头角。在中国市场中&#xff0c;企业对设备和技术更新换代的需求日益迫切&…

C++创建型模式之原型模式

C 原型模式&#xff08;Prototype Pattern&#xff09; 1. 解决的问题 原型模式&#xff08;Prototype Pattern&#xff09;是一种创建型设计模式&#xff0c;用于解决对象创建的问题&#xff0c;特别是在需要创建多个相似对象时&#xff0c;避免使用重复的构造代码。原型模式…

【Rust自学】6.1. 定义枚举

喜欢的话别忘了点赞、收藏加关注哦&#xff0c;对接下来的教程有兴趣的可以关注专栏。谢谢喵&#xff01;(&#xff65;ω&#xff65;) 6.1.1. 什么是枚举 枚举允许我们列举所有可能的值来定义一个类型。这与其他编程语言中的枚举类似&#xff0c;但 Rust 的枚举更加灵活和强…

深入解析 Apache APISIX

以下是“第一部分&#xff1a;背景与概述”的示例写作内容&#xff0c;供你参考和使用。你可根据实际需求和篇幅进行增删或细化。 一、背景与概述 1. 高性能动态网关的意义 1.1 微服务架构下的网关角色与价值 随着微服务架构在企业级应用中日益普及&#xff0c;系统被拆分为…

机器学习-逻辑回归和softmax回归

文章目录 逻辑回归逻辑回归算法表达式模型训练逻辑回归做多分类 softmax回归模型实例训练模型 注意代码 逻辑回归 logistic regression 并不是回归任务的算法&#xff0c;而是属于分类任务算法 逻辑回归算法表达式 一个 型曲线&#xff08;Sigmoid函数&#xff09;&#xff0…

WordPress源码解析-数据库表结构

WordPress是一个功能强大的内容管理系统&#xff0c;它使用MySQL数据库来存储和管理网站的内容、用户和配置信息。作为WordPress开发者&#xff0c;了解WordPress数据库的结构和各表的作用至关重要&#xff0c;因为这将帮助您更好地开发插件和主题&#xff0c;以及执行高级数据…

C++设计模式:享元模式 (附文字处理系统中的字符对象案例)

什么是享元模式&#xff1f; 享元模式是一个非常实用的结构型设计模式&#xff0c;它的主要目的是节省内存&#xff0c;尤其在需要创建大量相似对象时。 通俗解释&#xff1a; 想象我们在写一本书&#xff0c;每个字母都需要表示出来。如果每个字母都单独用对象表示&#xff…

小程序将对象通过url传递到下个页面

// 假设有一个对象需要传递 const obj { name: 张三, age: 25 };// 将对象转换为 JSON 字符串并编码 const objStr encodeURIComponent(JSON.stringify(obj));// 使用 wx.navigateTo 跳转并传递参数 wx.navigateTo({url: /pages/targetPage/targetPage?data${objStr}, });注…