第一次打訓練賽，還是太嫩了，知識點不夠，
題目：
奉上當時自己寫的代碼，（用了3個for（）回圈，超時），
#include<iostream>
#include<cmath>
using namespace std;
int main()
{
int n,m;
int b1,b2;
while (cin>>n>>m)
{
int a[n];
for(int i=0;i<n;i++)
{
cin>>a[i];
}
for(int i=0;i<m;i++)
{
int sum=0;
cin>>b1>>b2;
for(int i=b1;i<=b2;i++)
{
sum=a[i-1]+sum;
}
cout<<sum<<endl;
}
}
return 0;
}
看了別人的題解后寫的代碼，
#include<bits/stdc++.h>//C++萬能頭檔案
using namespace std;
long long sum[1000005];
int main()
{
long long n,m,s;
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
cin>>s;
sum[i]=sum[i-1]+s;//一維前綴和
}
int i,j;
for(int i=1;i<=m;i++){
scanf("%d %d",&i,&j);
// //第1位到第j位的和減去第一位到第i-1位的和，得到第i位到第j位的和，
printf("%d\n",sum[j]-sum[i-1]);
}
return 0;
}
//
學了一個新的知識點：前綴和，
一維前綴和
??其實可以把它理解為數學上的一維數列的前n項和，
??對于一個給定的數列 A，他的前綴和數列 S 是通過遞推能求出來的基本資訊之一：
??S[i] = ∑A[j] ( j ∈ [1,i] ) 一個部分和，即數列 A 某個下表區間內的數的和，也可以表示為前綴和相減的形式：sum(l,r) = ∑A[i] ( i ∈ [l,r] ) = S[r] - S[l-1]，
??代碼：
int sum[1] = a[1];
for(int i=2;i<=n;i++){
sum[i] = sum[i-1] + a[i];
}
用了前綴和，oj都說行（AC），奧利給，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/252681.html
標籤：其他