Hướng dẫn cho Bài 4: Đẹp hoàn hảo (HSG 9 Đà Nẵng 2025-2026)

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Tóm tắt đề bài

Cho dãy số nguyên dương \(A\) gồm \(N\) phần tử và một số nguyên dương \(S\).

Độ đẹp của một dãy số là số lượng đoạn con ít nhất cần chia sao cho tổng mỗi đoạn không vượt quá \(S\).
Độ đẹp hoàn hảo là tổng độ đẹp của tất cả các đoạn con \([L, R]\) (với \(1 \leq L \leq R \leq N\)) của dãy \(A\).
Yêu cầu: Tính độ đẹp hoàn hảo của dãy \(A\).

Phân tích

Điều kiện: \(N \leq 10^5\), \(S \leq 10^9\), \(A_i \leq 10^6\).
Nhận xét 1 (Cách tính độ đẹp): Để chia một đoạn thành ít phần nhất có tổng không quá \(S\), ta sử dụng chiến thuật tham lam: Bắt đầu từ phần tử đầu tiên, gộp nhiều phần tử nhất có thể vào đoạn hiện tại sao cho tổng vẫn \(\leq S\), sau đó bắt đầu đoạn mới.
Nhận xét 2 (Độ đẹp của đoạn con): Gọi \(f(L, R)\) là độ đẹp của đoạn con từ \(L\) đến \(R\). Ta cần tính \(\sum_{L=1}^{N} \sum_{R=L}^{N} f(L, R)\).
Nhận xét 3 (Tiền xử lý): Với mỗi vị trí \(i\), ta có thể tìm vị trí \(go[i]\) là vị trí đầu tiên bên phải \(i\) sao cho tổng \(A[i \dots go[i]-1] \leq S\) nhưng \(A[i \dots go[i]] > S\). Nói cách khác, nếu một đoạn bắt đầu tại \(i\), đoạn con đầu tiên của nó sẽ kết thúc tại \(go[i]-1\). Ta có thể dùng kỹ thuật hai con trỏ (Two Pointers) để tìm tất cả \(go[i]\) trong \(O(N)\).

Cách làm đơn giản (Brute Force)

Ý tưởng

Duyệt qua mọi cặp \((L, R)\). Với mỗi cặp, thực hiện thuật toán tham lam để tính độ đẹp của đoạn \([L, R]\).

Độ phức tạp

Thời gian: \(O(N^3)\) hoặc \(O(N^2)\) nếu tối ưu.
Đánh giá: Chỉ phù hợp cho \(N \leq 1000\) (Subtask 1, 2, 3).

Code Brute Force

C++

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

int main() {
    int n;
    long long s;
    cin >> n >> s;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    long long total_beauty = 0;
    for (int l = 0; l < n; l++) {
        for (int r = l; r < n; r++) {
            int count = 0;
            int current_idx = l;
            while (current_idx <= r) {
                long long current_sum = 0;
                count++;
                while (current_idx <= r && current_sum + a[current_idx] <= s) {
                    current_sum += a[current_idx];
                    current_idx++;
                }
            }
            total_beauty += count;
        }
    }
    cout << total_beauty << endl;
    return 0;
}

Python

n, s = map(int, input().split())
a = list(map(int, input().split()))

total_beauty = 0
for l in range(n):
    for r in range(l, n):
        count = 0
        curr = l
        while curr <= r:
            curr_sum = 0
            count += 1
            while curr <= r and curr_sum + a[curr] <= s:
                curr_sum += a[curr]
                curr += 1
        total_beauty += count
print(total_beauty)

Hướng giải quyết (Tối ưu)

Ý tưởng quy hoạch động

Gọi \(F[i]\) là tổng độ đẹp của tất cả các đoạn con bắt đầu tại vị trí \(i\), tức là \(F[i] = \sum_{R=i}^{N-1} f(i, R)\).
Kết quả bài toán sẽ là \(\sum_{i=0}^{N-1} F[i]\).

Xét các đoạn con bắt đầu tại \(i\) và kết thúc tại \(R\) (\(i \leq R < N\)):

Nếu \(i \leq R < go[i]\):
- Tổng đoạn \([i, R] \leq S\), nên độ đẹp \(f(i, R) = 1\).
- Số lượng các đoạn này là \(go[i] - i\). Tổng độ đẹp đóng góp là \((go[i] - i) \times 1\).
Nếu \(go[i] \leq R < N\):
- Theo chiến thuật tham lam, đoạn đầu tiên sẽ là \([i, go[i]-1]\). Các đoạn tiếp theo sẽ được chia từ dãy \([go[i], R]\).
- Vậy \(f(i, R) = 1 + f(go[i], R)\).
- Tổng độ đẹp đóng góp cho các đoạn này là:
  
  \[ \sum_{R=go[i]}^{N-1} (1 + f(go[i], R)) = (N - go[i]) + \sum_{R=go[i]}^{N-1} f(go[i], R) = (N - go[i]) + F[go[i]] \]

Công thức truy hồi

\[F[i] = (go[i] - i) + (N - go[i]) + F[go[i]]\]

Rút gọn:

\[F[i] = N - i + F[go[i]]\]

Với cơ sở \(F[N] = 0\). Ta tính ngược từ \(N-1\) về \(0\).

Độ phức tạp

Thời gian: \(O(N)\) để tìm mảng \(go\) và \(O(N)\) để tính mảng \(F\). Tổng cộng \(O(N)\).
Bộ nhớ: \(O(N)\) để lưu mảng \(A, go, F\).

Code tham khảo

C++

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    long long s;
    cin >> n >> s;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    // Tìm mảng go[i] bằng kỹ thuật hai con trỏ
    vector<int> go(n);
    long long current_sum = 0;
    int right = 0;
    for (int left = 0; left < n; left++) {
        while (right < n && current_sum + a[right] <= s) {
            current_sum += a[right];
            right++;
        }
        go[left] = right;
        current_sum -= a[left];
    }

    // Quy hoạch động tính F[i]
    vector<long long> f(n + 1, 0);
    long long total_ans = 0;
    for (int i = n - 1; i >= 0; i--) {
        // f[i] = (go[i] - i) + (n - go[i]) + f[go[i]]
        f[i] = (long long)n - i + f[go[i]];
        total_ans += f[i];
    }

    cout << total_ans << endl;

    return 0;
}

Python

import sys

def solve():
    # Đọc dữ liệu nhanh
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    n = int(input_data[0])
    s = int(input_data[1])
    a = list(map(int, input_data[2:]))

    # Tìm vị trí xa nhất có thể nhảy tới từ mỗi vị trí i
    # go[i] là chỉ số j đầu tiên sao cho sum(a[i...j-1]) <= s
    go = [0] * n
    current_sum = 0
    right = 0
    for left in range(n):
        while right < n and current_sum + a[right] <= s:
            current_sum += a[right]
            right += 1
        go[left] = right
        current_sum -= a[left]

    # f[i] là tổng độ đẹp của tất cả các đoạn con bắt đầu từ i
    # f[i] = (go[i] - i) * 1 + sum_{R=go[i]}^{n-1} (1 + beauty([go[i], R]))
    # f[i] = (go[i] - i) + (n - go[i]) + f[go[i]]
    # f[i] = n - i + f[go[i]]
    f = [0] * (n + 1)
    ans = 0
    for i in range(n - 1, -1, -1):
        next_pos = go[i]
        f[i] = (n - i) + (f[next_pos] if next_pos < n else 0)
        ans += f[i]

    print(ans)

if __name__ == "__main__":
    solve()

Bình luận

Tải bình luận...

Không có bình luận nào.