Đề HSG9 - BRVT - 2022: Editorial

Bài 1: Đếm số ô trống (6 điểm)

Cho số nguyên dương

$n$

$(n\le {10}^{18})$, đếm tổng số ô trống có trong các chữ số của

$n$, biết mỗi chữ số có các ô trống như sau:

• Chữ số
  $8$ có
  $2$ ô trống.
• Chữ số
  $0,4,6,9$ có
  $1$ ô trống
• Chữ số
  $1,2,3,5,7$ không có ô trống.

Accepted:

Để thuận tiện, ta dựng sẵn mảng

$d$ với

$d_i$ là số ô trống của chữ số

$i$.

Sau đó ta duyệt qua từng chữ số và cộng số ô trống vào đáp án.

Độ phức tạp thời gian:

$O\left(D\right)$ với

$D$ là số lượng chữ số của

$n$.

Code

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

int n, d[10] = {1, 0, 0, 0, 1, 0, 1, 0, 2, 1};

int main() {

    cin >> n;
    int res = 0;
    while (n > 0) {
        res += d[n % 10];
        n /= 10;
    }
    
    cout << res;

    return 0;
}

Bài 2: Tam giác đều lớn nhất (7 điểm)

Có

$n$ thanh gỗ có độ đài là

$A_1,A_2,\dots ,A_n$

$(n\le {10}^5,A_i\le {10}^9)$. Hãy cho biết có bao nhiêu tam giác đều có cạnh lớn nhất có thể được tạo ra bằng cách ghép các thanh gỗ đã cho.

Biết rằng: nếu có

$k$ thanh gỗ có cùng độ dài thì có thể tạo ra

$\frac{(k-2)\cdot (k-1)\cdot k}{6}$ tam giác đều.

Accepted:

Sử dụng kiểu dữ liệu map, đặt

$d_x$ là số lượng thanh gỗ độ dài

$x$.

Không thể sử dụng mảng bình thường vì

$x\le {10}^9$.

Đặt

$res$ là độ dài

$x$ lớn nhất thỏa mãn có ít nhất ba thanh gỗ độ dài

$x$

$(d_x\ge 3)$.

Kết quả của bài toán là:

$\frac{(d_{res}-2)\cdot (d_{res}-1)\cdot d_{res}}{6}$.

Độ phức tạp thời gian:

$O(n\log n)$.

Vì mỗi thao tác trên map mất chi phí thời gian là

$\log n$.

Code

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

int n;
map<int, int> d;

main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n;
    int res = 0;
    for (int i = 1; i <= n; i++){
        int x;
        cin >> x;
        
        d[x]++;
        if (d[x] == 3) {
            res = max(res, x);
        }
    }
    
    long long k = d[res];
    cout << k * (k-1) * (k-2) / 6;

    return 0;
}

Bài 3: Aladdin (7 điểm)

Có

$n$ cổ vật có giá trị là

$A_1,A_2,\dots ,A_n$

$(n\le 1000,A_i\le {10}^9)$. Tìm cách lấy các cổ vật để đạt tổng giá trị lớn nhất thỏa mãn quy tắc sau:

• Cổ vật lấy sau phải có số thứ tự lớn hơn cổ vật lấy trước.
• Cổ vật lấy sau phải có giá trị lớn hơn cổ vật lấy ngay trước và không được hơn quá
  $k$ đơn vị
  $(k\le {10}^9)$.

Brute - force:

Quay lui thử tất cả các cách chọn.

Độ phức tạp thời gian:

$O\left(2^n\right)$.

Accepted:

Quy hoạch động cơ bản.

Đặt

$d{p}_i$ là tổng giá trị lớn nhất có thể nhận được nếu xét

$i$ cổ vật đầu tiên và bắt buộc lấy cổ vật thứ

$i$ ở vị trí cuối cùng.

Công thức quy hoạch động:

• Khởi gán:
  $d{p}_i$ =
  $A_i$ (chỉ lấy cổ vật thứ
  $i$).
• $d{p}_i=max\left(d{p}_j\right)+A_i$
  $(\mathrm{\forall }j<i,A_j\le A_i\le A_j+k)$

Kết quả của bài toán:

$max(d{p}_i)$

$(1\le i\le n)$

Độ phức tạp thời gian:

$O\left(n\right)$.

Code

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

const int N = 1003;
int n, k, A[N];
long long dp[N], res;

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> A[i];
        dp[i] = A[i];
        
        for (int j = 1; j < i; j++) {
            if (A[i] > A[j] && A[i] <= A[j]+k) {
                dp[i] = max(dp[i], dp[j] + A[i]);
            }
        }
        
        res = max(res, dp[i]);
    }
    
    cout << res;

    return 0;
}