Đề HSG9 - BRVT - 2025: Editorial

Thông tin

Sau đây là lời giải của Kỳ thi Chọn HSG9 tỉnh Bà Rịa - Vũng Tàu năm học 2024 - 2025.

Thời gian thi: 08:00 - 10:30 ngày 04/03/2025.

Bạn đọc có thể nộp và chấm bài (test tự sinh) TẠI ĐÂY.

Chuẩn bị bởi team Logica, thuộc khuôn khổ dự án The Algitect (ALGI Project)

• Đề HSG9 - BRVT - 2025: Editorial
  • Bài 1: Số đẹp (5 điểm)
    • Tóm tắt đề bài
    • Subtask 1
    • Subtask 2
  • Bài 2: Phát quà (5 điểm)
    • Tóm tắt đề bài
    • Mô hình hóa bài toán
    • Subtask 1
    • Subtask 2
  • Bài 3: Tổng liên tiếp (5 điểm)
    • Tóm tắt đề bài
    • Subtask 1
    • Subtask 2
    • Subtask 3
    • Subtask 4
  • Bài 4: Cắt hoa (5 điểm)
    • Tóm tắt đề bài
    • Mô hình hóa bài toán
    • Subtask 1
    • Subtask 2
    • Subtask 3

Bài 1: Số đẹp (5 điểm)

Tóm tắt đề bài

Đếm số lượng số chính phương nhỏ hơn hoặc bằng

$n$ có tổng các chữ số là một số Fibonacci.

Dữ liệu đảm bảo:

$1\le n\le {10}^9$.

Subtasks:

• $60\mathrm{\%}$ số điểm:
  $1\le n\le {10}^6$.
• $40\mathrm{\%}$ số điểm: Không có ràng buộc gì thêm.

Subtask 1

Duyệt

$i$ từ

$1$ đến

$n$, kiểm tra và tăng kết quả nếu:

• $i$ là số chính phương.
• Tổng các chữ số của
  $i$ là một số Fibonacci.

Kiểm tra số chính phương

Vì số chính phương là bình phương của một số nguyên, ta có thể kiểm tra một số

$x$ có phải số chính phương hay không bằng cách lấy bình phương phần nguyên của

$\sqrt{x}$ so sánh với

$x$.

Tức là kiểm tra biểu thức sau có thỏa mãn hay không:

$${\lfloor \sqrt{x}\rfloor }^2=x$$

Cài đặt mẫu

bool isSqr(int x) {
   int tmp = floor(sqrt(x));
   
   if (tmp * tmp == x) {
       return true;
   }
   
   return false;
}

Kiểm tra số Fibonacci

Xây dựng mảng

$F$ với

$F_i$ là số Fibonacci thứ

$i$. Sau đó dùng mảng đánh dấu hoặc cấu trúc dữ liệu map để đánh dấu lại các số Fibonacci đã tìm được ở trên.

Nhận xét: Tổng chữ số của

$i$ luôn nhỏ hơn hoặc bằng

$9\cdot 9=81$ (số có tổng chữ số lớn nhất là

$999999999$).

Mà

$F_{11}=89>81$. Do đó, ta chỉ cần quan tâm đến

$10$ số Fibonacci đầu tiên

Cài đặt mẫu (đánh dấu số Fibonacci)

f[1] = f[2] = 1;
for (int i = 3; i <= 10; i++) f[i] = f[i-1] + f[i-2];
for (int i = 1; i <= 10; i++) mp[f[i]] = 1;

Cài đặt mẫu (tính tổng các chữ số của một số)

int digits(int x) {
   int ans = 0;
   while (x != 0) {
       ans += x % 10;
       x /= 10;
   }
   return ans;
}

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

$O\left(n\right)$.

Code

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

const int N = 82;
int n, F[N], mp[N];

int digits(int x) {
	int ans = 0;
    
	while (x != 0) {
		ans += x % 10;
		x /= 10;
	}
    
	return ans;
}

bool check(int x) {
	int tmp = sqrt(x);
    
	if (tmp * tmp == x) {
        return true;
    }
    
	return false;
}

int main() {
    F[1] = F[2] = 1;
    for (int i = 3; i <= 10; i++) {
        F[i] = F[i-1] + F[i-2];
    }
    for (int i = 1; i <= 10; i++) {
        mp[F[i]] = 1;
    }

    cin >> n;
    int res = 0;
    for (int i = 1; i <= n; i++) {
        if (mp[digits(i)] == 1 && check(i)) {
            res++;
        }
    }

    cout << res;

    return 0;
}

Subtask 2

Kế thừa tư tưởng thuật toán của thuật toán trước, ta cần một số cải tiến.

Nhận xét

Vì những số đẹp phải là số chính phương nên ta có thể tối ưu công đoạn duyệt tìm các số thỏa mãn bằng cách chỉ duyệt qua các số chính phương bé hơn hoặc bằng

$n$.

Để chỉ duyệt qua các số chính phương có dạng

$i^2$ và bé hơn hoặc bằng

$n$, ta có:

$$x^2\le n\iff i\le \sqrt{n}$$

Như vậy, ta duyệt qua mọi

$i$ từ

$1$ đến

$\lfloor \sqrt{n}\rfloor$, ta tính được

$i^2\le n$ là một số chính phương. Lúc này ta chỉ cần kiểm tra điều kiện còn lại.

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

$O\left(\sqrt{n}\right)$

Code

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

const int N = 82;
int n, F[N], mp[N];

int digits(int x) {
	int ans = 0;
    
	while (x != 0) {
		ans += x % 10;
		x /= 10;
	}
	return ans;
}

main(){
    F[1] = F[2] = 1;
    for (int i = 3; i <= 10; i++) {
        F[i] = F[i-1] + F[i-2];
    }
    
    for (int i = 1; i <= 10; i++) {
        mp[F[i]] = 1;
    }

    cin >> n;
    int res = 0;
    for (int i = 1; i*i <= n; i++) {
        if (mp[digits(i*i)] == 1) {
            res++;
        }
    }

    cout << res;

    return 0;
}

Bài 2: Phát quà (5 điểm)

Tóm tắt đề bài

Thầy Minh có

$X$ chiếc bút và

$Y$ quyển tập. Với một số lượng học sinh nhất định, thầy muốn phát hết số bút và quyển tập này, đồng thời số bút và số tập cũng phải được chia đều cho tất cả các bạn.

Yêu cầu: Tìm tất cả các cách phát quà thỏa mãn điều kiện của thầy Minh.

Mô hình hóa bài toán

Cho hai số nguyên

$X$ và

$Y$, đếm số lượng số nguyên dương

$n$ thỏa:

• $Xmodn=0$
• $Ymodn=0$

Subtask 1

Nhận xét

Các số nguyên

$n$ thỏa mãn yêu cầu đề bài bắt buộc phải bé hơn hoặc bằng

$X$ và

$Y$.

Duyệt

$n$ từ

$1$ đến

$min(X,Y)$ và đếm tất cả các số thỏa mãn yêu cầu đề bài.

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

$O(min(X,Y))$.

Code

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

int x, y, res;

int main(){
    cin >> x >> y;
    for (int i = 1; i <= min(x, y); i++) {
        if (x % i == 0 && y % i == 0) {
            res++;
        }
    }

    cout << res;

    return 0;
}

Subtask 2

Nhận xét

Xét

$n$ bất kỳ, nếu

$Xmodn=0$ và

$Ymodn=0$, dễ thấy

$\mathrm{UCLN}(X,Y)modn=0$

Bài toán trở thành: Đếm số lượng ước của

$\mathrm{UCLN}(X,Y)$.

Vì

$\mathrm{UCLN}(X,Y)\le X,Y\le {10}^{14}$, có thể duyệt qua tất cả các ước của

$\mathrm{UCLN}(X,Y)$ trong

$O\left(\sqrt{\mathrm{UCLN}(X,Y)}\right)$.

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

$O(\sqrt{\mathrm{UCLN}(X,Y)}+\log min(X,Y))$.

Tìm

$\mathrm{UCLN}(X,Y)$ bằng thuật toán Euclid mất thời gian

$\log min(X,Y)$.

Code

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

long long x, y;

int main(){
    cin >> x >> y;
    long long a = __gcd(x, y);

    long long res = 0;
    for (int i = 1; i*i <= a; i++){
        if (a % i == 0) res += 2;
        if (i * i == a) res--;
    }

    cout << res;

    return 0;
}

Bài 3: Tổng liên tiếp (5 điểm)

Tóm tắt đề bài

Cho mảng số nguyên

$A_1,A_2,\dots ,A_n$. Tìm đoạn con

$[l,r]$ với

$1\le l\le r\le n$ sao cho

$A_l+A_{l+1}+\cdots +A_{r-1}+A_r$ lớn nhất.

Dữ liệu đảm bảo:

$1\le N\le {10}^5$ và

$|A_i|\le {10}^9$.

Subtask:

• 20% số điểm:
  $n\le 100$.
• 20% số điểm:
  $n\le {10}^4$.
• 20% số điểm:
  $A_i\ge 0$.
• 40% số điểm: Không có ràng buộc gì thêm.

Subtask 1

Duyệt

$l$ và

$r$ để thử qua mọi đoạn con. Tương ứng với mỗi đoạn

$[l,r]$, duyệt từ

$l$ đến

$r$ để tính tổng của đoạn.

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

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

Code

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

const int N = 100;
int n, A[N+5];
long long res = -1e18;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> A[i];
    }

    for (int r = 1; r <= n; r++) {
        for (int l = 1; l <= r; l++) {
            long long sum = 0;
            for (int i = l; i <= r; i++) {
                sum += A[i];
            }

            res = max(res, sum);
        }
    }

    cout << res;
    
    return 0;
}

Subtask 2

Kế thừa tư tưởng của subtask trước, ta có thể tối ưu công đoạn tính tổng của một đoạn

$[l,r]$ bất kỳ bằng cách sử dụng mảng cộng dồn (prefix sum).

Tip

Gọi

$pr{e}_i$ là tổng của

$i$ phần tử đầu tiên của mảng

$A$, tức:

$$pr{e}_i=A_1+A_2+\cdots +A_i$$

Do đó, ta có tổng của một đoạn

$[l,r]$ là:

$$\begin{array}{rl}pr{e}_r-pr{e}_{l-1}& =(A_1+A_2+\cdots +A_r)-(A_1+A_2+\cdots +A_{l-1})\\ & =A_l+A_{l+1}+\cdots +A_r\end{array}$$

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

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

Code

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

const int N = 1e4;
int n, A[N+5];
long long pre[N+5], res = -1e18;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> A[i];
        pre[i] = pre[i-1] + A[i];
    }

    for (int r = 1; r <= n; r++) {
        for (int l = 1; l <= r; l++) {
            res = max(res, pre[r] - pre[l-1]);
        }
    }

    cout << res;
    
    return 0;
}

Subtask 3

Vì mọi số trong mảng

$A$ đều không âm, dễ thấy đoạn con có tổng lớn nhất là toàn bộ mảng, tức đoạn

$[1,n]$.

Như vậy, đáp án của bài toán là

$A_1+A_2+\cdots +A_n$.

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

$O\left(n\right)$.

Code

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

const int N = 1e5;
int n, A[N+5];
long long res = 0;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> A[i];
        res += A[i];
    }

    cout << res;
    
    return 0;
}

Subtask 4

Tip

Bài toán tìm đoạn con liên tiếp có tổng lớn nhất là một ứng dụng điển hình của thuật toán quy hoạch động Kadane.

• Định nghĩa:
  $f_i$ là tổng lớn nhất của một đoạn con liên tiếp kết thúc tại
  $i$.
• Khởi gán:
  $f_0=0$ (xem như một đoạn con rỗng).
• Công thức:
  $f_i=max(f_{i-1}+A_i,A_i)$.
  • Với
    $f_i=f_{i-1}+A_i$: Thêm
    $A_i$ vào đoạn con tối ưu kết thúc tại
    $i-1$.
  • Với
    $f_i=A_i$: Bắt đầu một đoạn con mới có bắt đầu với
    $A_i$.

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

$O\left(n\right)$.

Code

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

const int N = 1e5;
int n;
long long res = -1e18, A[N+5], f[N+5];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> A[i];
    }

    for (int i = 1; i <= n; i++){
        f[i] = max(A[i], f[i-1] + A[i]);
        res = max(res, f[i]);
    }

    cout << res;
    
    return 0;
}

Bài 4: Cắt hoa (5 điểm)

Tóm tắt đề bài

Vườn hoa của nhà Minh có

$N$ khóm hoa, khóm hoa thứ

$i$ có

$A_i$ bông hoa. Minh cần tìm cách cắt một số khóm hoa để tổng số bông hoa có được là nhiều nhất mà không được cắt

$K$ khóm hoa liên tiếp.

Yêu cầu: Hãy xác định số lượng bông hoa nhiều nhất có thể cắt được.

Subtask:

• $40\mathrm{\%}$ số điểm:
  $K=3$.
• $40\mathrm{\%}$ số điểm:
  $2\le K\le N\le {10}^3$.
• $20\mathrm{\%}$ số điểm: Không có ràng buộc gì thêm.

Mô hình hóa bài toán

Cho mảng số nguyên

$A_1,A_2,\dots ,A_n$, tìm dãy con có tổng lớn nhất thỏa mãn không có

$K$ phần tử nào liên tiếp nhau trong mảng.

Subtask 1

Với

$K=3$, có thể xác định rõ ràng các trạng thái để thực hiện quy hoạch động.

• Định nghĩa: (Xét
  $i$ phần tử đầu tiên của mảng)
  • $d{p}_{i,0}$ là tổng dãy con lớn nhất không kết thúc tại
    $A_i$.
  • $d{p}_{i,1}$ là tổng dãy con lớn nhất kết thúc tại
    $A_i$ và trước đó không có
    $A_{i-1}$.
  • $d{p}_{i,2}$ là tổng dãy con lớn nhất kết thúc tại
    $A_i$ và trước đó là
    $A_{i-1}$.
• Khởi gán:
  $d{p}_{0,0}=d{p}_{0,1}=d{p}_{0,2}=0$.
• Công thức: (bám vào yêu cầu của đề là không được chọn
  $3$ phần tử liên tiếp)
  • $d{p}_{i,0}=max(d{p}_{i-1,0},d{p}_{i-1,1},d{p}_{i-1,2})$: Không lấy phần tử
    $A_i$.
  • $d{p}_{i,1}=d{p}_{i-1,0}+A_i$: Lấy phần tử
    $A_i$, vì không lấy
    $A_{i-1}$ nên xét trạng thái
    $d{p}_{i-1,0}$.
  • $d{p}_{i,2}=d{p}_{i-1,1}+A_i$: Lấy phần tử
    $A_i$, vì lấy cả
    $A_{i-1}$ nên xét trạng thái
    $d{p}_{i-1,1}$.
• Kết quả:
  $max(d{p}_{n,0},d{p}_{n,1},d{p}_{n,2})$.

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

$O\left(n\right)$.

Code

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

const int N = 1e5;
long long n, k, A[N+1], dp[N+1][3];

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> A[i];
        dp[i][0] = max({dp[i-1][0], dp[i-1][1], dp[i-1][2]});
        dp[i][1] = dp[i-1][0] + A[i];
        dp[i][2] = dp[i-1][1] + A[i];
    }

    cout << max({dp[n][0], dp[n][1], dp[n][2]});

    return 0;
}

Subtask 2

Cần tổng quát hóa tư tưởng quy hoạch động.

• Định nghĩa:
  $d{p}_i$ là tổng dãy con lớn nhất xét
  $i$ phần tử đầu tiên.
• Khởi gán:
  • $d{p}_0=0$ (dãy con rỗng).
  • $d{p}_1=A_1$ (dãy con chỉ gồm
    $A_1$).
• Công thức: (với
  $i\ge 2$)

$$d{p}_i=max(max(d{p}_0,d{p}_1,\dots ,d{p}_{j-2})+A_j+A_{j+1}+\cdots +A_i)$$

Hướng dẫn áp dụng công thức

• Ta có điều kiện với
  $j$ là
  $i-j+1<k$ và
  $1\le j\le i$.

Điều kiện này tương đương với

$i-k+1<j\le i$.

• Để tính nhanh
  $max(d{p}_0,d{p}_1,\dots ,d{p}_{j-2})$, ta sử dụng một mảng prefix max.

$${\mathrm{prf}}_i=max(d{p}_0,d{p}_1,\dots ,d{p}_i)$$

• Để tính nhanh
  $A_j+A_{j+1}+\cdots +A_i$, ta sử dụng một mảng prefix sum.

$$S_i=A_1+A_2+\cdots +A_i$$

Như vậy, công thức cuối cùng của ta với

$i$ từ

$2$ đến

$n$ và

$i-k+1<j\le i$ là:

$$d{p}_i=max({\mathrm{prf}}_{j-2}+S_i-S_{j-1})$$

• Kết quả:
  $max(d{p}_1,d{p}_2,\dots ,d{p}_n)$.

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

$O(n\cdot k)$.

Code

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

const int N = 1e5;
int n, k, A[N+1];
long long dp[N+1], prf[N+1], res;

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

    for (int i = 1; i <= n; i++) {
        long long sum = 0;
        for (int j = i; j >= max(1, i-k+2); j--) {
            sum += A[j];
            dp[i] = max(dp[i], prf[max(0, j-2)] + sum);
        }

        res = max(res, dp[i]);
        prf[i] = max(prf[i-1], dp[i]);
    }

    cout << res;

    return 0;
}

Subtask 3

Kế thừa tư tưởng từ subtask trước, nhưng biến đổi để tối ưu hơn.

Biến đổi công thức

Biến đổi công thức quy hoạch động từ subtask trước, ta có:

$$\begin{array}{r}d{p}_i=max({\mathrm{prf}}_{j-2}+S_i-S_{j-1})\\ \iff d{p}_i=S_i+max({\mathrm{prf}}_{j-2}-S_{j-1})\end{array}$$

Như vậy, để tính

$d{p}_i$, ta cần tính

$max({\mathrm{prf}}_{j-2}-S_{j-1})$ với

$i-k+1<j\le i$.

Điều này dễ dàng được thực thi với kỹ thuật deque tìm max trên đoạn tịnh tiến.

Lưu ý

Một lựa chọn thay thế cho kỹ thuật trên là sử dụng cấu trúc dữ liệu set / multiset.

Code

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

const int N = 1e5;
int n, k, A[N+1];
long long val[N+1], dp[N+1], prf[N+1], S[N+1], res;

deque<int> dq;

void push(int id) {
    while (!dq.empty() && val[dq.back()] <= val[id]) {
        dq.pop_back();
    }

    dq.push_back(id);
}

void pop(int id) {
    if (!dq.empty() && dq.front() == id) {
        dq.pop_front();
    }
}

int32_t main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> A[i];
        S[i] = S[i-1] + A[i];
    }

    dp[0] = 0;
    dp[1] = prf[1] = A[1];
    res = dp[1];

    push(0);
    push(1);

    for (int i = 2; i <= n; i++) {
    	val[i] = prf[i-2] - S[i-1];
        push(i);

        if (i - k + 1 >= 0) {
        	pop(i - k + 1);
        }

        dp[i] = S[i] + val[dq.front()];
        prf[i] = max(prf[i-1], dp[i]);

        res = max(res, dp[i]);
    }

    cout << res;

    return 0;
}