首页 > 其他分享 >前缀和

前缀和

时间:2023-04-07 21:45:38浏览次数:39  
标签:前缀 int sum cin a1 a2 ll

链接:https://ac.nowcoder.com/acm/contest/55407/E
来源:牛客网

给定 n 个整数 a1, a2, · · · , an ,求它们两两相乘再相加的和,即 S = a1 · a2 + a1 · a3 + · · · + a1 · an + a2 · a3 + · · · + an-2 · an-1 + an-2 · an + an-1 · an.

输入描述:

#include <iostream>
using namespace std;
const int N=2e5+10;
typedef long long ll;
ll sum[N],a[N];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin>>n;
for(int i=0;i<n;i++){
cin>>a[i];
sum[i]=sum[i-1]+a[i];
}
ll s=0;
for(int i=0;i<n;i++){
s=s+(sum[n-1]-sum[i])*a[i];
}
cout<<s;
return 0;
}

2023哈理工蓝桥杯模拟练习赛_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ (nowcoder.com)

标签:前缀,int,sum,cin,a1,a2,ll
From: https://www.cnblogs.com/saulgoodman1/p/17297445.html

相关文章

  • 前缀和与差分
    1.K倍区间来源:第八届蓝桥杯省赛C++B组,第八届蓝桥杯省赛JAVAB组原题链接题目描述给定一个长度为\(N\)的数列,\(A_1,A_2,…A_N\),如果其中一段连续的子序列\(A_i,A_{i+1},…A_j\)之和是\(K\)的倍数,我们就称这个区间\([i,j]\)是\(K\)倍区间。你能求出数列中总共有多......
  • 前缀和-leetcode303
    LeetCode上的题目"303.区域和检索-数组不可变",是一个相对简单的问题。问题描述:给定一个整数数组nums,求出该数组从索引i到j(i≤j)范围内元素的总和,包含i,j两点。实现NumArray类:NumArray(int[]nums)用整数数组nums初始化对象intsumRange(inti,intj)返回......
  • js用前缀名查找class或id节点,js模糊查询某个dom节点
    js在操作dom的场景中,有时候会有类似的场景需求。js用前缀名查找class节点//参数dom为htmldom节点//参数key为需模糊查询的名称字段functionqueryClassNode(dom,key){letcollectArray=[];for(vari=0;i<dom.childNodes.length;i++){ //核心点......
  • 用前缀树实现中文敏感词过滤器
    前言本文代码实现一个中文的敏感词过滤器,预先将准备好的敏感词写入前缀树数据结构中实现快速检索,并且节省内存。一般用于检查注册用户名称、言论是否包含不文明的词汇。可以判断内容是否包含敏感词;找出内容中的敏感词;将内容中的敏感词替换成设置的字符。运行环境代码使用了JDK......
  • 前缀和
    [acwing]4405.统计子矩阵#include<cstdio>usingnamespacestd;typedeflonglongLL;constintN=510;intn,m,k;ints[N][N];LLres;intmain(){scanf("%d%d%d",&n,&m,&k);for(inti=1;i<=n;i++)......
  • 咬咬龟对前缀和的反对
    咬咬龟对前缀和的反对在计算机科学中,前缀和(PrefixSum)是一种常见的算法技术,用于高效地处理数组或序列中某一区间内元素的和。然而,在最近的一次直播中,国内知名主播咬咬龟表达了他对前缀和算法的反对意见,引发了广泛的讨论和争议。咬咬龟指出,前缀和算法虽然在某些情况下可以提高算......
  • 【LBLD】小而美的算法技巧:前缀和数组
    【LBLD】小而美的算法技巧:前缀和数组一维数组中的前缀和classNumArray{private:vector<int>preSum;public:NumArray(vector<int>&nums){preSum.push_back(0);for(inti=1;i<nums.size()+1;i++){preSum.push_back(......
  • 前缀和和差分
    前缀和和差分前缀和#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>#include<vector>#include<cstring>#include<unordered_set>#include<set>#include<stack>#include<map&g......
  • LeetCode 周赛 338,贪心 / 埃氏筛 / 欧氏线性筛 / 前缀和 / 二分查找 / 拓扑排序
    本文已收录到AndroidFamily,技术和职场问题,请关注公众号[彭旭锐]提问。大家好,我是小彭。上周末是LeetCode第338场周赛,你参加了吗?这场周赛覆盖的知识点很多,第四题......
  • 如何自定义 elementui 的前缀
    1、安装插件:postcss-change-css-prefix2、在根目录下创建postcss.config.js文件,并写入如下内容:constaddCssPrefix=require('postcss-change-css-prefix')module.e......