【1104】Sum of Number Segments (20分)【简单数学】

1.题目

https://pintia.cn/problem-sets/994805342720868352/problems/994805363914686464
求出一个正数数列中的连续子列（片段）和的累加。

2.思路

【法一】
可以暴力找数学规律，但是有点花时间，因为最终是要求第i个数的出现次数再最后累加，所以先抽象如为第1、2、3、…、7个数，依次计算第1、2、3、…7个数在长度为1的片段中出现的次数为1 1 1…1，同理计算1、2、3、…7个数在长度为1的片段中出现的次数为1 2 2…2 1，这样就累加计算出第1、2、3、…7个数总出现的次数为7 12 15 16 15 12 7。
根据7=17，12=26，15=35,16=44,…可以第k个数总出现次数为=k*(1+n-k)。

【法二】（更快）
现以第i个为中心确定片段temp，令选取的片段的首尾指针分别为p和q，对于p有i中选择（1、2、…、i），对于q有n-1-i种选择（i、i+1、i+2、…、n），所以组成片段temp种类个数=i*（n-i+1）。

3.代码

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>  
using namespace std;  
   
int main(){   
	int n;
	double v,ans=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%lf",&v);
		ans+=v*i*(n+1-i);  //第i位的总出现次数为v*i*(n+1-i)
	}
	printf("%.2f\n",ans);
	system("pause");
    return 0;   
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
 

文章来源: andyguo.blog.csdn.net，作者：山顶夕景，版权归原作者所有，如需转载，请联系作者。

原文链接：andyguo.blog.csdn.net/article/details/112425757