# Lời giải đề thi HSG lớp 9 năm học 2023-2024
---

Xin chào các bạn.

Vào chiều nay (29/2), kỳ thi chọn HSGTP Đà Nẵng lớp 9 đã kết thúc.

Tối nay mình mới nhận được đề (có vẻ là nó đã bị thu lại). Sau khi đọc qua đề, mình có một số nhận xét sau:
- Thứ nhất, đề cơ bản đã có khả năng phân loại thí sinh ở câu 3, 4 (nhất là câu 4, sẽ hơi khó khăn nếu học sinh chưa học Quy hoạch động)
- Đối với câu 1, câu 2 thì lại quá nhẹ, nên số lượng học sinh nắm điểm tối đa ở hai bài này có thể sẽ khá nhiều.
- Đề thi khá tương đương về độ khó so với những kỳ thi HSGTP lớp 9 năm trước.

Bây giờ mình sẽ đi vào từng bài.

:::info
P/s: Hiện tại chưa có link nộp bài từ LQDOJ/TLEOJ, cho nên tạm thời các bạn đọc lời giải hãy đọc các lời giải xong đó hãy code ở trong máy. Hoặc nếu các bạn tìm được link nộp bài nào thì các bạn cứ nộp. Tuy nhiên mình không chắc chắn về tính chính xác của các bộ test ở các trang web khác ngoài LQDOJ/TLEOJ.

Mình khuyến khích mạnh mẽ mọi người hãy cố gắng tự code bằng những gì mình nghĩ ra được và sau khi đọc lời giải. Chỉ khi nào các bạn thật sự bí ý tưởng thì mới nên xem code mẫu của mình. Điều này sẽ giúp các bạn giỏi lên từng ngày!
:::

:::warning
:::spoiler Cảnh báo
- Tất cả các đánh giá trong lời giải này của mình đều là **Ý KIẾN CÁ NHÂN**, không có ý xúc phạm hay chê bai bất cứ điều gì.
:::

## Bài 1. Tính tổng
Tag: `implementation`, `sorting`
### Tóm tắt đề
Cho dãy số $N$ phần tử. Hãy tính tổng $K$ phần tử lớn nhất trong dãy đã cho.

### Lời giải
Vì bài này dễ quá nên mình xin phép trình bày lời giải tối ưu luôn.

Bài này đơn giản các bạn sort giảm dần mảng, xong lấy tổng $K$ phần tử đầu tiên là được.

### Code tham khảo:

:::success
:::spoiler Code tham khảo

int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++)
{
    cin >> a[i];
}
sort(a + 1, a + 1 + n, greater<int>());

int res = 0;
for (int i = 1; i <= k; i++)
{
    res += a[i];
}

cout << res;

:::

Độ phức tạp của thuật toán là $O(n \log n)$

### Đánh giá
Bài này là một bài **RẤT** cơ bản mà ai đã học Tin thì đều biết làm một cách rất nhanh chóng, vì vậy nếu như bạn không làm được hay làm không đạt điểm tối đa bài này thì nên xem lại phương pháp học của bản thân.

## Bài 2. Oẳn tù xì
Tag: `string`, `counting`, `implementation`

### Tóm tắt đề
Cho xâu $S$ chỉ gồm các ký tự `H`, `D`, `N`. Đếm số lượng ký tự `N` và `D` trong xâu.

### Lời giải
Cũng như bài trên, mình xin phép vào thẳng luôn lời giải tối ưu: Chỉ cần duyệt qua một vòng for để đếm số lượng ký tự `D` và `N`, sau đó in ra kết quả là xong.

Ngoài ra, bạn có thể sử dụng đếm phân phối.

### Code tham khảo (Duyệt)
:::success
:::spoiler `GAME.CPP`

string s;
cin >> s; // có thể dùng getline(cin, s) nếu sợ trong xâu S có ký tự trắng
int d = 0, n = 0;
for (int i = 0; i < s.size(); i++)
{
    if (s[i] == 'D') d++;
    if (s[i] == 'N') n++;
}

cout << d << " " << n;

:::

### Code tham khảo (Đếm phân phối)
:::success
:::spoiler `GAME.CPP`

string s;
cin >> s; // có thể dùng getline(cin, s) nếu sợ trong xâu S có ký tự trắng
for (int i = 0; i < s.size(); i++)
{
    d[s[i]]++;
}

cout << d['D'] << " " << d['N'];

:::

## Đánh giá hai bài đầu tiên

:::info
**Đánh giá**
Hai bài đầu tiên giúp học sinh "tránh liệt", điều mà không ai muốn trong các kỳ thi. Nếu như bạn không làm full 100% hai bài này thì khả năng có giải (ít nhất là giải khuyến khích) là rất thấp.
:::

## Bài 3. Chùm đèn
Tag: `implementation`, `two-pointer`
### Tóm tắt đề
Cho mảng $a$ gồm $n$ phần tử và số nguyên dương $k$. Đếm số đoạn con liên tiếp có số lượng phần tử lẻ là $k$.

### Subtask 1: $1 \leq N \leq 100$
Với subtask này, bạn duyệt trâu hai chỉ số $i$ và $j$ và kiểm tra trong dãy con $a_i a_{i+1}\ldots a_j$ có bao nhiêu phần tử lẻ và so khớp đáp án là ok.

Độ phức tạp của thuật toán này là $O(n^3)$.

### Code tham khảo subtask 1:
:::success
:::spoiler

int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++)
{
    cin >> a[i];
}

int res = 0;

for (int i = 1; i <= n - 1; i++)
{
    for (int j = i + 1; j <= n; j++)
    {
        int odd = 0;
        for (int t = i; t <= j; t++)
        {
            if (a[t] % 2 == 1)
            {
                odd++;
            }
        }
        if (odd == k) res++;
    }
}

cout << res;

:::

### Subtask 2: $100 \leq N \leq 5\times 10^3$

Đối với subtask này, bạn có thể tính trước số lượng phần tử có giá trị lẻ ở mỗi dãy con $a_1 a_2 \ldots a_i$ ($1 \leq i \leq n$), sau đó so khớp $k$ là xong.

Rõ ràng hơn: Gọi $m[i]$ là số lượng phần tử lẻ của dãy số $a_1, a_2, \ldots, a_i$. Sau đó bạn duyệt hai vòng for và kiểm tra xem đoạn $[i,j]$ có số lượng phần tử lẻ có bằng $k$ hay không.

Độ phức tạp: $O(n^2)$

### Code tham khảo
:::success
:::spoiler

int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++)
{
    cin >> a[i];
    if (a[i] % 2 == 1)
    {
        m[i] = m[i - 1] + 1;
    }
    else
    {
        m[i] = m[i - 1];
    }
    /*
     Có thể viết gọn lại thành:
     m[i] = m[i - 1] + (a[i] % 2 == 1);
     */
}

for (int i = 1; i <= n - 1; i++)
{
    for (int j = i + 1; j <= n; j++)
    {
        if (m[j] - m[i - 1] == k) res++;
    }
}

cout << res;

:::

### Subtask 3: $n \leq 10^6$

Subtask này có khá nhiều cách làm, mình trình bày cách dễ hiểu nhất bằng hai con trỏ cho các bạn lớp 9 như sau:

Đầu tiên thì bạn vẫn sẽ tính số lượng phần tử lẻ của mảng. Sau đó khởi tạo hai biến `start` = 0 và `end` = 0. Ý tưởng như sau:

- Ta sẽ duyệt mảng bằng biến `end`. Trong quá trình duyệt này, chúng ta tăng biến đếm nếu phần tử là số lẻ. Sau đó chúng ta đẩy `start` sang bên phải cho đến khi `count` bằng $k$.
- Với mỗi bước, ta update biến `ans` - số mảng con chứa chính xác $k$ số nguyên lẻ. Cuối cùng, ta sẽ trả về giá trị `ans`.

**Lưu ý**: Số đoạn con liên tiếp có đúng $k$ phần tử lẻ = (số đoạn con liên tiếp có **nhiều nhất** $k$ phần tử lẻ) $-$ (số đoạn con liên tiếp có **nhiều nhất** $k-1$ phần tử lẻ).

Độ phức tạp tổng thể là $O(n)$, đủ tốt cho subtask này.

### Code tham khảo
:::success
:::spoiler

while(end<n){
        if(nums[end]%2==1){
            count++;
        }
        while(count>k){
            if(nums[start]%2==1){
                count--;
            }
            start++;
        }
        ans += end-start+1;
        end++;
    }
    return ans;

:::

### Đánh giá

Bài này cũng tương đối dễ nghĩ ra thuật, ít nhất là với subtask 2, nếu bạn nào có tư duy tốt thì cũng rất dễ nghĩ ra subtask 3 bằng hai con trỏ như trên.

## Bài 4. Tặng quà
Tag: `dp`, `implementation`

:::info Lời cảm ơn
Lời giải bài này được tham khảo từ các nguồn tài liệu về LIS trên internet. Trân trọng cảm ơn các tác giả.
:::

Cho dãy số $a_1,a_2,\ldots,a_n$. Đếm số phần tử còn lại sau khi lọc ra các phần tử của dãy con tăng dài nhất trong dãy $a$.

### Subtask 1: $n \leq 25$

Với $n$ khá nhỏ, ta có thể đệ quy như sau:

Gọi $L[i]$ là độ dài của LIS (Longest Increasing Subsequence - Dãy con tăng dài nhất) kết thúc ở vị trí $i$ sao cho $a[i]$ là phần tử cuối cùng của LIS. Ta có công thức đệ quy như sau:
- $L[i] = 1 + max(L[j])$ với $0 < j < i$ và $a[j] < a[i]$;
- $L[i] = 1$, nếu không giá trị $j$ thoả mãn điều kiện trên.

Từ đó ta xây dựng quy trình code như sau:
- Tạo một hàm đệ quy
- Với mỗi lần gọi đệ quy, lặp từ $i=1$ cho đến vị trí hiện tại và thực hiện:
- Tìm độ dài có thể có của dãy con tăng dài nhất kết thúc ở vị trí hiện tại nếu dãy trước đó kết thúc tại $i$.
- Cập nhật lại độ dài.
- Lặp lại quá trình như trên cho đến khi hết mảng.

Độ phức tạp của thuật toán này là $O(2^n)$, khá ổn để full subtask này.
### Pseudo-code tham khảo
:::success
:::spoiler

int lis_end(int arr[], int curr)
{
    if(curr == 0)
        return 1
    int ans = 1
    for(i = curr - 1 to 0)
        if(arr[i] < arr[curr])
            ans = max(ans, 1 + lis_end(arr, i))
    return ans
}
int lis(int arr[], int N)
{
    int max_ans = 1
    for(i = 0 to N-1)
        max_ans = max(max_ans, lis_end(arr, i))
    return max_ans
}

:::
### Subtask 2: $25 \leq n \leq 2000$

Ta đặt $f_i$ là độ dài của LIS kết thúc ở phần tử thứ $i$.

Ta sẽ tính theo thứ tự $f[0], f[1], \ldots$ và cứ như thế. Giá trị ta cần tìm sẽ là phần tử lớn nhất mảng $f$.

Gọi phần tử hiện tại là $i$. Giả sử ta muốn tính $f_i$ và tất cả các phần tử $f_0, f_1, \ldots, f_{i-1}$ đều đã biết. Lúc này ta có hai lựa chọn như sau:
- $f_i=1$: Dãy con cần thiết chỉ chứa phần tử $a_i$
- $f_i > 1$: Dãy con sẽ kết thúc ở $a_i$, và ngay trước nó sẽ là một số phần tử $a_j$ với $j<i$ và $a_j < a_i$.
- Dễ dàng thấy được, dãy con kết thúc ở $a_j$ bản thân nó là một trong những LIS kết thúc ở $a_j$. Phần tử $a_i$ chỉ mở rộng LIS đó thêm một số.
- Vì vậy, ta có thể lặp qua mọi $j<i$ với $a_j < a_i$ và lấy LIS mà ta có được bằng việc thêm $a_i$ vào LIS kết thúc ở $a_j$. LIS kết thúc ở $a_j$ có độ dài $f_j$, việc thêm $a_i$ vào LIS sẽ tăng giá trị $f_j$ thêm $1$ đơn vị.

$$d[i] = \max_{\substack{j < i \\\\ a[j] < a[i]}} \left(d[j] + 1\right)$$

Ghép hai điều kiện ở trên lại, ta có công thức:

$$d[i] = \max\left(1, \max_{\substack{j < i \\\\ a[j] < a[i]}} \left(d[j] + 1\right)\right)$$

### Code tham khảo
:::success
:::spoiler

int lis(vector<int> const& a) {
    int n = a.size();
    vector<int> d(n, 1);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (a[j] < a[i])
                d[i] = max(d[i], d[j] + 1);
        }
    }

    int ans = d[0];
    for (int i = 1; i < n; i++) {
        ans = max(ans, d[i]);
    }
    return ans;
}

:::

### Subtask 3: $2000 < n \leq 10^5$

Subtask này có hai cách làm:
- Cách 1: Dùng Quy hoạch động & Tìm kiếm nhị phân
- Cách 2: Dùng CTDL (Segment Tree/Fenwick Tree/...)

Lời giải này hướng tới HS lớp 9 nên mình sẽ sử dụng cách 1.

Ta sẽ khởi tạo một mảng để lưu các LIS đã tìm được (tạm gọi là mảng $b$)

Với mỗi phần tử trong $a$:
- Nếu phần tử đang xét lớn hơn phần tử cuối cùng của phần tử cuối cùng trong $b$ (tức là phần tử cuối cùng trong dãy con đang xét), ta thêm phần tử này vào cuối dãy con đang xét.
- Mặt khác, ta thực hiện tìm kiếm nhị phân trên mảng $b$ để tìm phần tử nhỏ nhất lớn hơn hoặc bằng phần tử hiện tại.
- Khi tìm thấy vị trí cần cập nhật, ta thay thế phần tử đó bằng phần tử hiện tại.

### Code tham khảo subtask 3

:::success
:::spoiler

int subtask3(vector<int>& a)
{
 
    int n = a.size();
    vector<int> ans;
 
    ans.push_back(a[0]);
 
    for (int i = 1; i < n; i++) {
        if (a[i] > ans.back()) {
 
            ans.push_back(a[i]);
        }
        else {
 
            int low = lower_bound(ans.begin(), ans.end(),
                                  a[i])
                      - ans.begin();
 
            ans[low] = a[i];
        }
    }
 
    return ans.size();
}

:::

Độ phức tạp tổng thể là $O(n \log n)$, đủ tốt cho subtask này.

### Đánh giá
Đơn giản đây chỉ là bài toán LIS thông thường mà nếu như ai đã học qua Quy hoạch động chắc chắn đã nghe qua (và học qua). Hơn nữa, đề bài chỉ yêu cầu đưa ra độ dài, không đưa ra LIS nên bài toán có thể giải bằng nhiều phương pháp khác nhau, tuỳ vào trình độ và sự thông hiểu của người làm. Cá nhân mình thấy bài này đã làm tốt nhiệm vụ phân loại trình độ thí sinh.

## Tổng kết

Căn cứ vào biểu điểm của đề thi, độ khó của đề thi, mình dự đoán phổ điểm trung bình sẽ nằm khoảng từ 7 - 9.
### Ưu điểm
- Đề nhẹ nhàng, phù hợp với kiến thức của HS lớp 9.
- Dễ nghĩ ra thuật, dễ cài.

### Khuyết điểm
- Hai bài đầu hơi quá dễ.

Đánh giá cá nhân: 70/100 điểm

:::danger
:::spoiler Ý kiến cá nhân
Mình nghĩ rằng, với đề này thì khả năng lạm phát điểm $10$ như đề thi năm $2022$ là có thể trở lại. Thiết nghĩ rằng người ra đề cần có đánh giá một cách khách quan về thực lực của học sinh ngày nay, tránh quá dễ như đề $2022$ hay đề này, cũng như quá khó như đề Tuyển sinh 10 Đà Nẵng năm $2023$ (bài 1 DP Digit :skull:)
:::

Trên đây là lời giải cũng như đánh giá của mình về đề thi năm nay. Cảm ơn các bạn đã đọc lời giải này. Vì thực hiện trong thời gian nên chắc chắn có những sai sót. Nếu có bất kỳ thắc mắc hay có sai sót nào trong lời giải, vui lòng liên hệ với mình thông qua facebook của mình để giúp lời giải này hoàn thiện hơn.