Hướng dẫn giải của [Ninh Bình - TS10 - 2024] Bài 4: Dãy số

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: noodles0428

Subtask 1: ~n = 10~ và dãy ban đầu là một dãy không giảm.

Đáp số chính là tổng tất cả các phần tử trong dãy ~a~, và in ra tất cả các phần tử trong dãy đó.

ĐPT: ~O~(~n~)

Subtask 2 + 3: ~11 \le n \le 10^3~

Ta sẽ duyệt tất cả các cặp phần tử trong mảng rồi kiểm tra xem:

  • Liệu đây có phải là dãy không giảm hay không?
  • Nếu có, ta sẽ maximize biến kết quả.

Sau đó, ta sẽ duyệt lại các cặp theo một lần nữa để xem đâu là các cặp số mà tổng tất cả phần tử nằm giữa chúng đúng bằng biến kết quả và là dãy con không giảm.

ĐPT: ~O~(~n^2~)

Subtask 4: ~(10^3 < n \leq 10^5)~

Nhận xét: Do các phần tử mảng ~a~ đều là số nguyên dương, ta có thể sử dụng thuật toán hai con trỏ để tối ưu việc tìm kiếm các cặp thỏa mãn.

Phần ý tưởng còn lại đều dựa vào subtask trên.

ĐPT: ~O~(~n~)

Code mẫu:

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 1e6 + 9;

int n, a[N];

namespace sub1 {
    bool valid() {
        return n <= 10;
    }

    void solve() {
        int sum = 0;
        for (int i = 1; i <= n; i++) {
            sum += a[i];
        }
        cout << sum << "\n";
        for (int i = 1; i <= n; i++) {
            cout << a[i] << " ";
        }
        exit(0);
    }
}

namespace sub3 {
    bool valid() {
        return n <= (int)1e3;
    }

    void solve() {
        int mx = 0;
        for (int i = 1; i <= n; i++) {
            int res = a[i];
            for (int j = i + 1; j <= n; j++) {
                if (a[j] < a[j - 1]) {
                    break;
                }
                res += a[j];
            }
            mx = max(mx, res);
        }

        cout << mx << "\n";

        for (int i = 1; i <= n; i++) {
            int res = a[i];
            for (int j = i + 1; j <= n; j++) {
                if (a[j] < a[j - 1]) {
                    break;
                }
                res += a[j];
            }
            if (res != mx) continue;
            cout << a[i] << " ";
            for (int j = i + 1; j <= n; j++) {
                if (a[j] < a[j - 1]) {
                    break;
                }
                cout << a[j] << " ";
            }
            cout << "\n";
        }
        exit(0);
    }
}

namespace sub4 {
    int pfs[N];
    void solve() {
        for (int i = 1; i <= n; i++) {
            pfs[i] = pfs[i - 1] + a[i];
        }
        int ans = 0;
        int l = 1;
        while (l <= n) {
            int r = l;
            while (r < n and a[r] <= a[r + 1]) ++r;
            ans = max(ans, pfs[r] - pfs[l - 1]);
            l = r + 1;
        }

        cout << ans << "\n";

        l = 1;

        vector<pair<int, int>> v;
        while (l <= n) {
            int r = l;
            while (r < n and a[r] <= a[r + 1]) ++r;
            if (pfs[r] - pfs[l - 1] == ans) {
                v.push_back(make_pair(l, r));
            }
            l = r + 1;
        }
        for (pair<int, int> i: v) {
            for (int j = i.first; j <= i.second; j++) {
                cout << a[j] << " ";
            }
            cout << "\n";
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    if (sub1::valid()) sub1::solve();
    if (sub3::valid()) sub3::solve();
    sub4::solve();
    return 0;
}

// <33

Bình luận

Hãy đọc nội quy trước khi bình luận.

Không có bình luận tại thời điểm này.