THI THỬ HSG TỈNH K9 - 2025 - II

Thông tin

Sau đây là lời giải của đề thi thử Kỳ thi Chọn HSG tỉnh Bà Rịa - Vũng Tàu K9 lần II (được chuẩn bị theo ma trận kiến thức của Sở GD&ĐT tỉnh Bà Rịa - Vũng Tàu)

Thời gian: 20:00 - 22:30 ngày 02/03/2025

Bạn đọc có thể nộp và chấm bài TẠI ĐÂY

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

Lưu ý: Lời giải này chỉ hướng đến việc AC (tức là đạt trọn điểm) các bài.

• THI THỬ HSG TỈNH K9 - 2025 - II
  • Bài 1: Nỗi sợ của loài rồng (5 điểm)
    • Tóm tắt đề bài:
    • Mô hình hóa bài toán:
    • Lời giải
  • Bài 2: Mật mã cổ đại (5 điểm)
    • Tóm tắt đề bài:
    • Mô hình hóa bài toán:
    • Lời giải:
  • Bài 3: Chuyển nhà (5 điểm)
    • Tóm tắt đề bài:
    • Mô hình hóa bài toán
    • Lời giải:
  • Bài 4: Hộp ma thuật (5 điểm)
    • Tóm tắt đề bài:
    • Mô hình hóa bài toán:
    • Lời giải:

Bài 1: Nỗi sợ của loài rồng (5 điểm)

Tóm tắt đề bài:

Có

$n$ con rồng lần lượt bay đến tấn công lâu đài của Trâm.

• Những con rồng thứ
  $k,k\cdot 2,k\cdot 3,\dots$ sẽ bị kẹp đuôi.
• Những con rồng thứ
  $l,l\cdot 2,l\cdot 3,\dots$ sẽ bị cắt vuốt.

Yêu cầu: Đếm số lượng con rồng đã bị Trâm kẹp đuôi hoặc cắt vuốt.

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

$1\le k,l\le k\cdot l,n\le {10}^{18}$

Subtasks:

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

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

Bài toán đơn giản là đếm số lượng số từ

$1$ đến

$n$ chia hết cho

$k$ hoặc

$l$.

Lưu ý

Những số chia hết cho cả

$k$ và

$l$ chỉ được xem là

$1$ số.

Lời giải

Tip

Ta có công thức sau:

$$cn{t}_x=\lfloor \frac{n}{x}\rfloor$$
Với

$cn{t}_x$ là số lượng bội của

$x$ từ

$1$ đến

$n$.

Như vậy, ta có thể tính được số lượng bội của

$k$ và

$l$ là:

$$\lfloor \frac{n}{k}\rfloor +\lfloor \frac{n}{l}\rfloor$$

Tuy nhiên, với phép tính trên, những số vừa chia hết cho

$k$ vừa chia hết cho

$l$ đang bị đếm lặp lại

$2$ lần và cần trừ đi.

Nhận xét

Số nhỏ nhất vừa chia hết cho

$k$ và vừa chia hết cho

$l$ là bội chung nhỏ nhất của

$k$ và

$l$

Vì vậy, bội của bội chung nhỏ nhất của

$k$ và

$l$ là những số chúng ta cần trừ đi

Ta tính được bội chung nhỏ nhất của

$k$ và

$l$ bằng:

$$\frac{k\cdot l}{\mathrm{GCD}(k,l)}$$

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

$$\lfloor \frac{n}{k}\rfloor +\lfloor \frac{n}{l}\rfloor -\lfloor \frac{n}{\frac{k\cdot l}{\mathrm{GCD}(k,l)}}\rfloor$$

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

$O(\log min(k,l))$.

Độ phức tạp trên là độ phức tạp để tính

$\mathrm{GCD}$ bằng thuật toán Euclid.

Code

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

long long n, k, l;

long long __lcm(long long a, long long b) {
	return (a / __gcd(a, b)) * b;
}

int main() {
	cin >> n >> k >> l;
	cout << (n / k) + (n / l) - (n / __lcm(k, l));

	return 0;
}

Bài 2: Mật mã cổ đại (5 điểm)

Tóm tắt đề bài:

Cho

$q$ truy vấn, mỗi truy vấn gồm một số nguyên

$n$.

Yêu cầu: In ra các ước nguyên tố của

$n$ theo thứ tự giảm dần.

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

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

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

Subtasks:

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

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

Thực chất, bài toán yêu cầu phân tích thừa số nguyên tố của

$n$.

Lời giải:

Định nghĩa

$E_i$ là ước nguyên tố nhỏ nhất của

$i$.

VD:

$E_2=2,E_9=3$.

Giả sử đã tính được

$E_i$ với

$i$ từ

$1$ đến

$n$, có thể tìm được tất cả các ước số nguyên tố của

$n$ bằng cách không ngừng chia

$n$ cho

$E_n$ đến khi

$n=1$.

VD: Phân tích thừa số nguyên tố của

$n=40$

• $E_{40}=2\to n=\frac{40}{2}=20$
• $E_{20}=2\to n=\frac{20}{2}=10$
• $E_{10}=2\to n=\frac{10}{2}=5$
• $E_5=5\to n=\frac{5}{5}=1$

$n=40$ có các ước nguyên tố là

$2$ và

$5$.

Tip

Tạm gọi việc thực hiện tính trước mảng

$E$ là sàng ước nguyên tố. Đúng như tên gọi của nó, phương pháp này áp dụng tư tưởng của thuật toán sàng nguyên tố.

Cụ thể, ta duyệt

$i$ tăng dần từ

$2$, nếu

$i$ chưa tìm được ước nguyên tố

$(E_i=0)$, ta duyệt qua tất cả các bội của

$j$

$(i,i\cdot 2,i\cdot 3,\dots )$ và đánh dấu

$E_j=i$.

Vì với mỗi số, ta duyệt qua các bội của nó, do đó thuật toán trên có độ phức tạp:

$$O(\frac{n}{1}+\frac{n}{2}+\frac{n}{2}\dots )\approx O(n\log n)$$
Với

$n$ là giá trị lớn nhất cần sàng tới.

Tuy nhiên, trong thực tế, thuật toán trên chạy nhanh hơn rất nhiều vì ta chỉ duyệt qua bội của những số nguyên tố.

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

$O(n\log n)$.

Code

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

const int N = 1e6;
int q, n, E[N+1];

void sieve() {
    for (int i = 2; i <= N; ++i) {
        if (!E[i]) {
            for (int j = i; j <= N; j += i) {
                E[j] = i;
            }
        }
    }
}


int main() {
    sieve();
    
    cin >> q;
    while (q--) {
        cin >> n;
        
        while (n > 1) {
            int p = E[n];
            cout << p << " ";
            while (n % p == 0) {
                n /= curr;
            }
        }
        
        cout << "\n";
    }
    
    return 0;
}

Bài 3: Chuyển nhà (5 điểm)

Tóm tắt đề bài:

Khoa có

$n$ món đồ, món đồ thứ

$i$ có khối lượng là

$A_i$. Cậu cần xếp các món đồ vào thùng có sức chứa tối đa là

$k$.

Yêu cầu: Đếm số cách để Khoa chọn hai món đồ bỏ vào thùng.

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

$1\le n\le {10}^6$ và

$1\le A_i,k\le {10}^9$.

Subtasks:

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

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

Thực chất, bài toán yêu cầu đếm số cặp

$i<j$ thỏa

$A_i+A_j\le k$.

Lời giải:

Xét trường hợp ta cố định

$A_i$, khi đó cần đếm số lượng

$j$ thỏa:

• $j>i$.
• $A_j\le k-A_i$.

Điều này có thể thực hiện bằng tìm kiếm nhị phân cơ bản.

Caution

Có thể, khoảng

$A_j$ thỏa mãn chứa cả

$A_i$ mà ta đang cố định. Khi đó, cần trừ

$A_i$ ra.

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

$O(n\log n)$.

Code

#include <bits/stdc++.h>

using namespace std;
const int N = 1e6;

ll n, k, ans, A[N+1];

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

    sort(A+1, A+1+n);

    for(int i = 1; i < n; i++){
        if (A[i] >= k) break;
        int pos = upper_bound(A+1, A+1+n, k - a[i]) - A - 1;
        ans += max(0, pos - i);
    }

    cout << ans;

    return 0;
}

Bài 4: Hộp ma thuật (5 điểm)

Tóm tắt đề bài:

Tí có một chiếc hộp ma thuật và được đưa cho một hằng số

$K$. Có

$q$ truy vấn, mỗi truy vấn thuộc một trong hai dạng:

• + x: Thêm một viên ngọc có sức mạnh
  $x$ vào hộp.
• - x: Lấy ra một viên ngọc có sức mạnh
  $x$ (đảm bảo có ít nhất một viên trong hộp).

Yêu cầu: Với mỗi truy vấn, tính số cách lấy một số viên ngọc trong hộp để tổng sức mạnh bằng

$K$. In ra số cách chia dư cho

$998244353$

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

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

$2\le n\le {10}^6$.

Subtasks:

• $20\mathrm{\%}$ số điểm:
  $1\le q\le 20$.
• $40\mathrm{\%}$ số điểm:
  $1\le q,k\le 200$.
• $40\mathrm{\%}$ số điểm: Không có ràng buộc gì thêm.

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

Với mỗi truy vấn, đếm số cách chọn một tập con trong tập hợp các số để tổng bằng

$K$.

Đây là một bài toán quy hoạch động cái túi (balo) điển hình.

Lời giải:

• Định nghĩa:
  $d{p}_i$ là số cách tạo tổng bằng
  $i$.
• Khởi gán:
  • $d{p}_0=1$.
  • $d{p}_i=0$ với mọi
    $i\ne 0$.
• Công thức:
  • Khi thêm một giá trị
    $x$:
    $d{p}_i=d{p}_i+d{p}_{i-x}$ với
    $i\ge x$.

  Với những cách tạo ra tổng

  $i-x$ ban đầu, có thể thêm giá trị

  $x$ để tạo tổng

  $i$.

  • Khi xóa đi một giá trị
    $x$:
    $d{p}_i=d{p}_i-d{p}_{i-x}$

  Với những cách tạo ra tổng

  $i-x$ ban đầu, nay mất đi một giá trị

  $x$ để tạo tổng

  $i$.

• Kết quả:
  $d{p}_K$.

Lưu ý:

• Đối với truy vấn - x cần phải duyệt
  $i$ giảm dần để đảm bảo
  $d{p}_{i-x}$ đang lưu trạng thái của truy vấn trước chứ không phải truy vấn hiện tại.
• Ngược lại, đối với truy vấn + x cần phải duyệt
  $i$ tăng dần để
  $d{p}_{i-x}$ lưu trạng thái khi đã xét thêm giá trị
  $x$.

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

$O(q\cdot K)$.

Code

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

const int N = 5000;
const long long M = 998244353;
long long q, k, dp[N+1];

int32_t main() {
	dp[0] = 1;

	cin >> q >> k;
	while (q--) {
		char chr; int x;
		cin >> chr >> x;

		if (chr == '+')
			for (int i = k; i >= x; i--)
				(dp[i] += dp[i-x]) %= M;

		if (chr == '-')
			for (int i = x; i <= k; i++)
				(((dp[i] -= dp[i-x]) %= M) += M) %= M;

		cout << dp[k] << "\n";
	}

	return 0;
}