[Mảng 1 Chiều Cơ Bản]. Bài 43. Tổng của mọi dãy con

View as PDF

Submit solution

Points: 1.00 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Author:
Problem source:
28Tech
Problem type
Allowed languages
C, C#, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Cho mảng A[] gồm N phần tử, nhiệm vụ của bạn là tính tổng của mọi dãy con trong mảng, ví dụ mảng A[] = {1, 2, 3, 4} bạn phải tính tổng của các dãy con : {1}, {1, 2}, {1, 2, 3}, {1, 2, 3, 4}, {2}, {2, 3}, {2, 3, 4}, {3}, {3, 4}, {4}


Đầu vào

Dòng 1 là N : số phần tử trong mảng

Dòng 2 là N phần tử cách nhau 1 khoảng trắng


Giới hạn

1<=N<=1000

0<=A[i]<=1000


Đầu ra

In ra tổng của các dãy con trong mảng


Ví dụ :

Input 01
6
6 0 3 7 9 5
Output 01
6 6 9 16 25 30 0 3 10 19 24 3 10 19 24 7 16 21 9 14 5

Comments

Please read the guidelines before commenting.



  • 0
    knight01  commented on Feb. 5, 2025, 6:48 p.m.

    include <iostream>

    #include <numeric>
    using namespace std;
    int main() {
        int n; cin >> n;
        int a[n];
        for (int i = 0; i < n; ++i) cin >> a[i];
        for (int i = 0; i < n; ++i) {
            for (int j = i; j < n; ++j) cout << accumulate(a + i, a + j + 1, 0) << ' ';
        }
    }
    // :") độ phức tạp cao n mà nhìn clean
    

    • 1
      bengokyeuanh99  commented on May 2, 2025, 7:54 a.m.

      Nhìn thì tưởng "clean" đấy, nhưng thực ra đang cầm dao thái thịt mà đi mổ trâu rồi. accumulate(a+i, a+j+1, 0) bên trong vòng i, j là đang cộng lại nguyên đoạn [i..j] mỗi lần thành ra bạn đang chơi O(n³) chứ không phải O(n²) đâu.

      Với bài này, chỉ cần hiểu rõ dãy con liên tiếp là ta có thể dùng 1 biến sum tích lũy nội tuyến trong vòng j để đạt O(n²) thật sự:

      for (int i = 0; i < n; ++i) { int sum = 0; for (int j = i; j < n; ++j) { sum += a[j]; cout << sum << " "; } }

      Cái gọi là "code sạch" không chỉ nằm ở std:: hay ít dòng mà là ở tư duy giảm lặp, tiết kiệm tài nguyên, giữ logic tinh gọn. Độ phức tạp mới là clean thật sự.

      Cứ tưởng accumulate là shortcut xịn, ai ngờ shortcut chạy ngược hướng


  • -2
    VDev  commented on Jan. 18, 2025, 11:58 a.m.

    FULL AC

    #include <bits/stdc++.h>
    #include <iomanip>
    #include <cmath>
    #include <climits>
    #define ll long long
    using namespace std;
    ll a[10000011];
    ll cnt = 0, s = 0, mark[10000011], mot = 0, ko = 0;
    
    int main(){
        ll n;
        cin >> n;
        for(ll i = 0; i < n; i++){
            cin >> a[i];
        }
        for(ll i = 0; i < n; i++){
                for(ll j = i; j < n; j++){
                        cnt = 0;
                    for(ll h = i; h <= j; h++){
                    cnt += a[h];
                }
                cout << cnt << " ";
                }
        }
        return 0;
    }
    

  • -5
    Toan1410  commented on May 21, 2024, 7:39 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.