current position:Home>Fragment sum of 1049 sequence (20 points) (c + +)

Fragment sum of 1049 sequence (20 points) (c + +)

2022-01-27 04:30:36 BatmannLv

 Insert picture description here

1. Start by writing nested loops directly , Found timeout . So we need to use mathematical methods to solve .
	 Then refer to other people's blogs , Discover its regularity :
	 First observe a number , for example , about N=4 The serial number in the sequence is 3 The fragment of the number of is as follows :
	   ( Starting from 1)[(1,2,3),(1,2,3,4)];
	   ( Starting from 2)[(2,3),(2,3,4)];
	   ( Starting from 3)[(3),(3,4)];
	 You can see it , Including i In the number of clips , The beginning of the fragment can be 1,2,3..i, altogether i A choice ,
	( If included 3 The clips are 123 Three options )  The end of the clip can be i,i+1,...n, altogether n-i+1 A choice .
	( If included 3 The clips are 34 Two options ).
	 So we can promote , For length is N The serial number in the sequence is i Number of numbers , The clip can be divided into i Parts of , The first i Part of the starting point is i,
	 The end points are i,i+1,i+2,...,N, common (N-i+1) individual , So sequence i The frequency of occurrence of is i*(N-i+1).
2. About long long sum:

“N The larger the ,double Precision error caused by multiple accumulation of values of type , Because the input is decimal , Store in double In the middle of the day ,
 Binary representation is used inside the computer , And the word length of the computer is limited , Some decimal floating point numbers cannot be accurately represented by binary 
 It's only infinitely close , Under the limitation of word length, rounding error is inevitable , These subtle errors are N When it is large, it is accumulated many times 
 There will be large errors , So it is recommended not to use double Type for accurate calculation of multiple accumulation , Instead, it can accurately store 
 The integer of . Try to input double The value of type is expanded 1000 Double and turn to long long Integer accumulation , Use at the same time 
long long Type to save sum Value , Output divided by 1000.0 Convert to floating point type and then output ( It's equivalent to moving the decimal point back 3 Behind you 
 Calculate again , avoid double The decimal part of the type is stored imprecisely , After multiple accumulation, it will affect the results )  But I think multiplied by 1000
 Not necessarily rigorous , Maybe the test sample has at least three decimal places , If the test sample becomes four decimal places 、 Five place 、 Six ,
 multiply 1000 It is equivalent to truncating directly at three decimal places , The original fourth, fifth and sixth digits may still cause 
 Precision problem , But if you multiply by 10000 It will go beyond long long Value , I think the most accurate is to intercept the largest of all decimals 
 The one with the number of digits .. Maybe there's something missing in my idea , After testing , The test sample does not exceed three decimal places ,
 Although it is modified to multiply by 1000 The post code has AC, But if the test sample is slightly modified , It may lead to non AC 了 …
 So put a question mark on this question first , I guess the sample title may be revised in the future …”

my ( The code timed out )

#include <iostream>
#include <cstdio>
using namespace std;
int main(){
    int n;
    cin >> n;
    float a[n];
    for(int i = 0;i < n;i++){
        cin >> a[i];
    float sum1 = 0,sum2 = 0;
    for(int i = 0;i < n;i++){
            sum1 = 0;
        for(int j = i;j < n;j++){
            sum1 += a[j];
            sum2 += sum1;
    return 0;

Liunuo's code

#include <iostream>
using namespace std;
int main() {
    int n;
    cin >> n;
    double temp;
    long long sum = 0;
    for(int i = 1;i <= n;i++){
        cin >> temp;
        sum += (long long)(temp * 1000) * i * (n - i + 1); 
    printf("%.2f",sum / 1000.0);
    return 0;

copyright notice
author[BatmannLv],Please bring the original link to reprint, thank you.

Random recommended