Ôn tập TS10 & THTB 2025 - Đề 2: Editorial

Thông tin

Sau đây là lời giải của Đề 2 trong chuỗi đề ôn tập TS10 & THTB 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)

Ôn tập TS10 & THTB 2025 - Đề 2: Editorial

Bài 1: Truy đuổi

Lời giải

Mô phỏng lại cuộc truy đuổi bằng cách đặt hai biến tượng trưng cho vị trí của rô-bốt và kẻ trộm. Sau mỗi giây, thay đổi hai vị trí này và kiểm tra khoảng cách.

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

O (n)

Code

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

int n, k, p;

int main() {
    cin >> n >> k >> p;

    int ans = 0;
    long long robot = 0, thief = 0;
    while (n--) {
        long long x;
        cin >> x;

        robot += x;
        thief += k;

        if (abs(robot - thief) <= p) {
            ans++;
        }
    }

    cout << ans;
    return 0;
}

Bài 2: Bài toán khó

Subtask 1

Nhận xét

Vì

BCNN (A, B) = n

nên ta có

A, B

là ước của

n

Thử duyệt qua mọi cặp ước của

n

, kiểm tra cặp số có thỏa mãn điều kiện không, sau đó lấy đáp án nhỏ nhất.

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

O ({\sqrt{n}}^{2}) = O (n)

Code

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

long long n, m, res = 1e18;

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

int main() {
    cin >> m >> n;
    for (long long i = 1; i*i <= n; i++)
        for (long long j = 1; j*j <= n; j++) {
            if (__gcd(i, j) == m && __lcm(i, j) == n)
                res = min(res, i + j);
            if (__gcd(n/i, j) == m && __lcm(n/i, j) == n)
                res = min(res, n/i + j);
            if (__gcd(i, n/j) == m && __lcm(i, n/j) == n)
                res = min(res, i + n/j);
            if (__gcd(n/i, n/j) == m && __lcm(n/i, n/j) == n)
                res = min(res, n/i + n/j);
        }

    if (res == 1e18) res = -1;
    cout << res;

    return 0;
}

Subtask 2

Nhận xét

Vì

UCLN (A, B) = m

nên ta có

A, B

là bội của

m

, viết lại thành:

$A = m \times x$
$B = m \times y$

Với
$x, y$ là các số nguyên dương.

Lại có:

\begin{aligned} BCNN (A, B) & = \frac{A \times B}{UCLN (A, B)} = \frac{m \times x \times m \times y}{m} = m \times x \times y \\ \Leftrightarrow n = m \times x \times y \\ \Leftrightarrow x \times y = \frac{n}{m} \end{aligned}

Như vậy, nếu

n

không chia hết cho

m

thì không tồn tại đáp án thỏa mãn, ngược lại ta có

x

và

y

là ước của

\frac{n}{m}

đồng thời

x \times y = \frac{n}{m}

Duyệt các cặp

(x, y)

bằng cách duyệt qua các ước của

\frac{n}{m}

, tính

A = m \times x

, và

B = m \times y

, sau đó kiểm tra điều kiện

UCLN (A, B) = m

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

O (\sqrt{\frac{n}{m}})

Code

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

long long m, n;

int main() {
    cin >> m >> n;

    if (n % m != 0) {
        cout << -1;
        return 0;
    }

    long long s = n / m;
    long long ans = LLONG_MAX;

    for (long long x = 1; x * x <= s; ++x) {
        if (s % x == 0) {
            long long y = s / x;
            long long a = m*x, b = m*y;
            if (__gcd(a, b) == m) {
                ans = min(ans, a + b);
            }
        }
    }

    cout << (ans == LLONG_MAX ? -1 : ans);
    return 0;
}

Bài 3: Mật mã

Lời giải

Bài toán này chỉ kiểm tra khả năng sử dụng kiểu dữ liệu xâu.

Chữ số và kí tự

Cần phải hiểu, trong kiểu dữ liệu xâu, kí tự 9 khác với giá trị số 9. Ký tự này mang một giá trị mã ASCII để thực hiện tính.

VD:
9 =

57

trong bảng mã ASCII.
A =

65

trong bảng mã ASCII.

Để thao tác với số 9, ta cần lấy giá trị

9

của nó bằng cách lấy kí tự 9 - 0:

9 =
$57$ trong bảng mã ASCII.
0 =
$48$ trong bảng mã ASCII.
9 - 0 =
$57 - 48$ =
$9$ .

Nguyên lí này dựa vào việc các số 0, 1, 2, …, 9 được sắp xếp liền kề và tăng dần trong bảng mã ASCII, có giá trị từ
$48$ đến
$57$

Trong bảng mã ASCII, các chữ cái in hoa A, B, …, C được xếp liền kề nhau. Do đó, khi dịch các chữ cái ta chỉ việc cộng thêm vào ký tự một khoảng cần dịch.

Lưu ý

Ta cần mô phỏng việc xoay vòng bảng chữ cái (khi hết ký tự Z thì quay lại kí tự A).

Dễ dàng thực hiện điều này bằng câu lệnh điều kiện.

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

O (L)

với

L

là độ dài xâu.

Code

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

string s;

int main() {
    cin >> s;
    string res = "";

    for (int i = 0; i < s.size(); i += 2) {
        //Lấy số bước dịch chuyển
        int step = s[i+1] - '0';
        
        //Nếu cộng vào vượt ra khỏi `Z`, cần quay lại `A`.
        if (s[i] + step > 'Z') step -= 26;
        
        res.push_back(s[i] + step);
    }

    cout << res;
    return 0;
}

Bài 4: Tuyến xe buýt

Subtask 1

Với

k = 2

, ta thử mọi cặp vị trí để mở trạm.

Giả sử ta mở hai trạm

i, j (i < j)

, ta có:

Hành khách đi qua cổng
$i$ để đến trạm
$i, i + 1, \dots, j - 1$ .
Hành khách đi qua cổng
$j$ để đến trạm
$j + 1, j + 2, \dots, n, 1, 2, \dots, i - 1$ .

Để dễ xử lý, nhất là trường hợp thứ hai, đoạn bị cắt ra làm hai phần (cuối mảng và đầu mảng), thì ta thực hiện nhân đôi mảng ban đầu. Khi đó, vị trí

n + 1, n + 2, \dots

cũng tương ứng với vị trí

1, 2, \dots

Tính nhanh tổng quãng đường

Để tính nhanh được giá trị này, ta cần lưu hai mảng cộng dồn như sau:

$S$ là mảng cộng dồn thông thường với
$S_{i} = A_{1} + A_{2} + \dots + A_{i}$ .
$F$ là mảng cộng dồn "bậc thang" với
$F_{i} = A_{1} + A_{2} \times 2 + A_{3} \times 3 + \dots + A_{i} \times i$ .

Khi đó, từ trạm

i

, tổng chi phí để đến các trạm

i + 1, i + 2, \dots, j

là:

\begin{aligned} r_{i + 1} \times 1 + r_{i + 2} \times 2 + \dots + r_{j} \times (j - i) \\ = (r_{i} \times i + r_{i + 1} \times (i + 1) + r_{i + 2} \times (i + 2) + \dots + r_{j} \times j) - i \times (r_{i} + r_{i + 1} + \dots + r_{j}) \\ = F_{j} - F_{i - 1} - i \times (S_{j} - S_{i - 1}) \end{aligned}

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

O (n^{2})

Code

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

const int K = 7, N = 100;
const long long MX = 1e18;

int n, k, A[N+1];
long long S[2*N+1], F[2*N+1], res = MX;

long long cost(int i, int j) {
    if (j < i) j += n;
    return F[j] - F[i-1] - (S[j] - S[i-1])*i;
}

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

    for (int i = n+1; i <= 2*n; i++) {
        S[i] = S[i-1] + A[i-n];
        F[i] = F[i-1] + (long long)i*A[i-n];
    }

    for (int i = 1; i <= n; i++)
        for (int j = i+1; j <= n; j++)
            res = min(res, cost(i, j-1) + cost(j, i-1));

    cout << res;

    return 0;
}

Subtask 2

Bài toán con

Xét bài toán đơn giản hơn như sau:

Cho

$n$ trạm xe buýt xếp thành một hàng thẳng được đánh số từ
$1$ đến
$n$ từ trái sang phải. Từ trạm
$i$ chỉ có thể đi đến trạm
$i + 1$ . Chỉ có
$k$ trạm được mở, mỗi trạm có chỉ tiêu
$r_{i}$ hành khách. Tìm tổng quãng đường ít nhất các hành khách phải di chuyển mà vẫn đạt chỉ tiêu.

Bản chất, bài toán này là bài toán chia đoạn thành

k

nhóm liên tiếp. Trong đó, để ghép một đoạn liên tiếp

i, i + 1, i + 2, \dots, j

thành một nhóm sẽ mất chi phí là tổng quãng đường để các hành khách xuất phát từ trạm

i

và đến trạm

i + 1, i + 2, \dots, j

Đó là:

r_{i + 1} \times 1 + r_{i + 2} \times 2 + \dots + r_{j} \times (j - i)

Để tính chi phí này nhanh cho nhiều đoạn, có thể áp dụng mảng cộng dồn như subtask trước, hoặc duyệt ngược và duy trì tổng hậu tố (xem code để rõ hơn).

Nếu xem xét kỹ, để giải bài toán gốc, ta chỉ cần giải bài toán con như trên với vị trí bắt đầu lần lượt là

1, 2, \dots, n

. Sau đó lấy đáp án nhỏ nhất.

VD: Với

n

= 5. Đặt vị trí bắt đầu là

3

, ta có

n

trạm xe buýt thẳng hàng là:

3, 4, 5, 1, 2

SAU ĐÂY LÀ HƯỚNG DẪN GIẢI BÀI TOÁN CON

Áp dụng quy hoạch động.

Định nghĩa:
$d p_{i, j}$ là tổng quãng đường nhỏ nhất các hành khách phải đi thỏa mãn
$n$ trạm đều đạt chỉ tiêu, khi đã mở cửa
$i$ trạm, và
$j$ trạm đầu tiên đạt chỉ tiêu.
Khởi gán:
- $d p_{0, 0} = 0$ : Khi chưa mở cửa trạm nào thì cũng không trạm nào đạt chỉ tiêu.
- Mọi giá trị
  $d p$ còn lại gán bằng
  $\infty$ .
Công thức:
- $d p_{i, j} = min (d p_{i - 1, t - 1} + C (t, j))$ với
  $1 \leq t \leq j$ và
  $C (t, j)$ là tổng quãng đường để hành khách đi từ trạm
  $t$ đến các trạm
  $t + 1, t + 2, \dots, j$ . Tức là thử các TH sau:
  - Ghép trạm
    $j$ thành một nhóm
  - Ghép trạm
    $j, j - 1$ thành một nhóm
  - …
  - Ghép giạm
    $1, 2, \dots, j$ thành một nhóm
Kết quả:
$d p_{k, n}$ : Mở cửa
$k$ trạm, và cả
$n$ trạm đều đạt chỉ tiêu.

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

O (k n^{3})

Code










































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

const int K = 10, N = 100;
const long long MX = 1e18;
int n, k, A[N+1], B[N+1];
long long dp[K+1][N+1], res = MX;

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

    for (int beg = 1; beg <= n; beg++) {
        for (int i = 1; i <= n; i++) {
            int pos = beg + i - 1;
            if (pos > n) pos -= n;
            B[i] = A[pos];
        }

        for (int p = 0; p <= k; p++)
            for (int i = 0; i <= n; i++)
                dp[p][i] = MX;

        dp[0][0] = 0;
        for (int p = 1; p <= k; p++)
            for (int i = 1; i <= n; i++) {
                long long sum = 0, cost = 0;
                for (int j = i; j >= 1; j--) {
                    cost += sum;
                    sum += B[j];
                    dp[p][i] = min(dp[p][i], dp[p-1][j-1] + cost);
                }
            }

        res = min(res, dp[k][n]);
    }

    cout << res;

    return 0;
}

Ôn tập TS10 & THTB 2025 - Đề 2: Editorial

Bài 1: Truy đuổi

Lời giải

Bài 2: Bài toán khó

Subtask 1

Subtask 2

Bài 3: Mật mã

Lời giải

Bài 4: Tuyến xe buýt

Subtask 1

Subtask 2

Read more

Ôn tập TS10 & THTB 2025 - Đề 5: Editorial

Ôn tập TS10 & THTB 2025 - Đề 4: Editorial

Ôn tập TS10 & THTB 2025 - Đề 3: Editorial

Ôn tập TS10 & THTB 2025 - Đề 1: Editorial