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

Thông tin

Sau đây là lời giải của Đề 3 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 - Đề 3: Editorial

Bài 1: Số chín ước

Subtask 1

Đếm ước

Để đếm số lượng ước của một số

x

, ta thực hiện:

Duyệt từ
$1$ đến
$\sqrt{x}$ , nếu
$n$ chia hết cho
$i$ thì nghĩa là tồn tại
$2$ ước của
$n$ là
$i$ và
$\frac{x}{i}$ .

Chú ý trường hợp

i = \frac{x}{i}

Duyệt các số từ

l

đến

r

và đếm số lượng số có

9

ước.

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

O (\sqrt{l} + \sqrt{l + 1} + \dots + \sqrt{r})

Code

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

int l, r;

int uoc(int n){
    int res = 0;
    for (int i = 1; i*i <= n; i++) {
        if (n%i == 0) {
            res += 2;
            if (i*i == n) res--;
        }
        
        if (res > 9) return res;
    }
    
    return res;
}

int main(){
    cin >> l >> r;
    
    int res = 0;
    for (int i = l; i <= r; i++)
        if (uoc(i) == 9) 
            res++;
    
    cout << res;

    return 0;
}

Subtask 2

Cải tiến đếm ước

Áp dụng kĩ thuật sàng ước:

Với mỗi số
$x$ , lưu
$c n t_{x}$ là số lượng ước của
$x$ .
Với mỗi số từ
$1$ đến
$10^{6}$ , thực hiện duyệt qua các bội
$x$ của nó và tăng
$c n t_{x}$ lên
$1$ .

Thao tác trên mất chi phí

O (10^{6} \log 10^{6})

$\frac{10^{6}}{1} + \frac{10^{6}}{2} + \dots + \frac{10^{6}}{10^{6}} \approx 10^{6} \log 10^{6}$ .

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

O (10^{6} \log 10^{6})

Code

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

const int N = 1e6 + 5;
int l, r, cnt[N];

int main(){
    //Sàng ước
    for (int i = 1; i <= 1e6; i++) {
        for (int j = i; j <= 1e6; j += i) {
            //Duyệt qua bội j của i
            cnt[j]++;
        }
    }

    cin >> l >> r;
    int res = 0;
    for (int i = l; i <= r; i++) {
        if (cnt[i] == 9) {
            res++;
        }
    }
    
    cout << res;

    return 0;
}

Subtask 3

Cải tiến đếm ước

Với một số

n = p_{1}^{x_{1}} \times p_{2}^{x_{2}} \times p_{3}^{x_{3}} \dots p_{k}^{x_{k}}

, trong đó:

$p_{i}$ là thừa số nguyên tố thứ
$i$ của
$n$ .
$x_{i}$ là số mũ của thừa số nguyên tố thứ
$i$ của
$n$ .

Số ước của n là:

(x_{1} + 1) \times (x_{2} + 1) \times (x_{3} + 1) \dots (x_{k} + 1)

Để biểu thức trên bằng

9

, ta chỉ cần xét hai trường hợp:

$n = p^{8}$ (số ước của
$n$ là
$8 + 1 = 9$ ).
$n = p_{1}^{2} \times p_{2}^{2}$ (số ước của
$n$ là
$(2 + 1) \times (2 + 1) = 3 \times 3 = 9$ ).

Như vậy, bài toán trở thành:

Đếm số lượng số nguyên dương

x

có dạng

x = p^{8}

và

x = p_{1}^{2} \times p_{2}^{2} = (p_{1} \times p_{2})^{2}

Nói cách khác, đáp án chính là số lượng số nguyên tố mũ

8

cộng với số lượng bình phương tích của hai số nguyên tố khác nhau sao cho chúng có giá trị nằm trong đoạn

[l, r]

Đếm số lượng số nguyên tố mũ 8

Duyệt từng số nguyên

i

bằng vòng lặp, kiểm tra nếu

i

là số nguyên tố và

l \leq i^{8} \leq r

thì

i^{8}

là một số thỏa mãn đề bài.

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

O (\sqrt[8]{r})

Lưu ý, cần phải thoát ra khỏi vòng lặp khi

i^{8} > r

Đếm số lượng bình phương của tích hai số nguyên tố khác nhau

Ta có:

\begin{array}{r} (p_{1} \times p_{2})^{2} \leq r \\ \Leftrightarrow p_{1} \times p_{2} \leq \sqrt{r} \end{array}

Đề bài cho

r \leq 10^{9} \Rightarrow \sqrt{r} < 31623

, như vậy ta chỉ cần xét các số nguyên tố nhỏ hơn hoặc bằng

31623

Từ

1

đến

31623

chỉ có

3401

số nguyên tố. Ta lấy ra trước các số nguyên tố này, sau đó chạy hai vòng lặp lồng nhau lấy ra mọi cặp số nguyên tố.

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

O (3401^{2})

Độ phức tạp thời gian của cả bài là tổng độ phức tạp thời gian của hai thao tác.

Code

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

int l, r;

bool isPrime(int n) {
    for (int i = 2; i*i <= n; i++)
        if (n % i == 0) {
            return false;
        }
    
    return true;
}

int main(){
    cin >> l >> r;

    vector<int> prime;
    //Danh sách các số nguyên tố
    
    for (int i = 2; i*i <= r; i++) {
        if (isPrime(i)) {
            prime.push_back(i);
        }
    }

    int res = 0;
    for (int i = 0; i < prime.size() - 1; i++) {
        for (int j = i+1; j < prime.size(); j++) {
            //p[i]^2 * p[j]^2
            long long x = 1ll * prime[i] * prime[i] * prime[j] * prime[j];
            if (x >= l && x <= r) res++;
        }
    }

    for (int i = 2; i*i*i*i*i*i*i*i <= r; i++) {
        //i^8
        int x = i*i*i*i*i*i*i*i;
        if (isPrime(i) && x >= l && x <= r) {
            res++;
        }
    }

    cout << res;

    return 0;
}

Bài 2: Rương tiết kiệm

Lời giải

Nhận xét

Chaien luôn lấy rương có nhiều xu nhất, để đảm bảo số xu bỏ vào sẽ không phí, Suneo sẽ phải bỏ vào rương nhiều xu nhất.

Ta làm như sau:

Sắp xếp mảng theo thứ tự giảm dần của giá trị.
Mô phỏng Chaien đang lấy tiền, chạy vòng lặp từ
$1$ đến
$n$ (tức là từ rương nhiều xu nhất đến ít xu nhất), cộng số xu vào tổng nếu sau khi cộng tổng vẫn bé hơn hoặc bằng
$k$ . Tức là Chaien lấy nhiều xu nhất có thể mà không vượt quá
$k$ , gọi đó là
$s u m$ .
Khi này, ta chỉ cần bỏ thêm
$k - s u m$ đồng xu vào rương có nhiều xu nhất (do nhận xét ở trên).

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

O (n \log n)

$n \log n$ là số thao tác để sắp xếp mảng bằng hàm sort().

Code

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

const int N = 3e5 + 5;
int n, a[N], k;

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

    long long sum = 0, res = LLONG_MAX;
    for (int i = 1; i <= n; i++) {
        sum += a[i];
   
        if (sum > k) {
            break;
        }
        
        res = min(res, k - sum);
    }
    
    cout << res;

    return 0;
}

Bài 3: Bấm nút

Lời giải

Nhận xét:

Dựa vào việc nút bấm sau phải có số điểm nhỏ hơn nút đã bấm trước đó, ta có:

Tại một vị trí

i

, sẽ không cần phải triệu hồi rô-bốt (tức là ô này đảm bảo sẽ được bấm mà tại đó không cần triệu hồi rô-bốt) khi và chỉ khi:

Một trong hai ô kế (ô
$i - 1$ và
$i + 1$ ) có số điểm lớn hơn ô
$i$ .
Một trong hai ô kế đó có số điểm bằng ô
$i$ và đã được đảm bảo là sẽ được bấm.

Vì từ những ô kế
$i$ được nhắc đến ở trên, rô-bốt có thể di chuyển sang ô
$i$ và bấm nút.

Như vây, chỉ cần phải triệu hồi một rô-bốt ở vị trí bất kỳ trên một đoạn liên tiếp

[i, j]

mà thỏa mãn:

$a_{i} = a_{i + 1} = \dots = a_{j}$
$a_{i} > a_{i - 1}$ và
$a_{j} > a_{j + 1}$ .

Ví dụ:
$[7, 7, 9, 9, 3, 2]$ , có đoạn
$[9, 9]$ thỏa mãn yêu cầu trên.

Tta chỉ cần triệu hồi rô-bốt ở
$1$ trong
$2$ ô đó và sẽ luôn có cách di chuyển rô-bốt qua các ô xung quanh để bấm nút theo thứ tự điểm giảm dần.

Áp dụng kĩ thuật hai con trỏ:

Chạy vòng lặp cố định đầu
$i$ , đầu
$j$ xuất phát từ
$i$ , nếu
$a_{j + 1} = a_{j}$ , ta dịch đầu
$j$ lên. Làm như vậy nhằm tìm được các đoạn liên tiếp bằng nhau.
Kiểm tra điều kiện:
$a_{i} > a_{i - 1}$ và
$a_{j} > a_{j + 1}$

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

O (n)

Code

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

const int N = 1e6 + 5;
int n, res, a[N];

int main(){
    cin >> n;
    
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    
    a[0] = a[n+1] = 0;
    
    while (i <= n) {
        int j = i;
        
        while (j < n && a[j+1] == a[i]) {
            j++;
        }
        
        if (a[i] > a[i-1] && a[j] > a[j+1]) {
            res++;
        }
        
        i = j+1;
    }
    
    cout << res;

    return 0;
}

Bài 4: Hình vuông

Subtask 1

Nhận xét

Một hình vuông kích thước cạnh

k

có góc trái trên là ô

[i, j]

thì sẽ có góc phải dưới là ô

[i + k - 1, j + k - 1]

Để kiểm tra một hình vuông có gồm toàn số

1

hay không, ta duyệt qua các ô trong đó để tính tổng các giá trị, tổng này phải bằng

k^{2}

Thử mọi kích thước

k

có thể của hình vuông từ lớn đến bé, nếu có tồn tại hình vuông kích thước

k

thì đáp án là

k

và số lượng hình vuông có kích thước

k

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

O (n^{5})

Đây là độ phức tạp lý thuyết - độ phức tạp thực tế sẽ nhỏ hơn nhiều, đủ để chạy với giới hạn
$n, m \leq 50$ .

Code

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

const int N = 1e3 + 5;
int n, m, a[N][N];

bool full(int x, int y, int k) {
    for (int i = x; i <= x + k - 1; i++) {
        for (int j = y; j <= y + k - 1; j++) {
            if (a[i][j] == 0) {
                return 0;
            }
        }
    }
    
    return 1;
}

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

    for (int k = n; k >= 1; k--) {
        int cnt = 0, check = 0;
        for (int i = 1; i <= n - k + 1; i++) {
            for (int j = 1; j <= m - k + 1; j++) {
                 if (full(i, j, k)) {
                    check = 1;
                    cnt++;
                 }
            }
        }
        
        if (check) {
            //Ngừng chương trình để không tốn thời gian chạy
            cout << k << ' ' << cnt;
            return 0;
        }
    }

    cout << -1;

    return 0;
}

Subtask 2

Nhận xét

Có thể tạo ra hình vuông toàn

1

cạnh

x

có góc phải dưới là ô

[i, j]

khi và chỉ khi

a_{i, j} = 1

và cũng có thể tạo ra ba hình vuông toàn

1

cạnh

x - 1

có góc phải dưới là ô

(i - 1, j), (i, j - 1), (i - 1, j - 1)

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

Định nghĩa:
$f_{i, j}$ là hình vuông lớn nhất tạo được với ô
$a_{i, j}$ là góc phải dưới của hình vuông đó.
Công thức:
$f_{i, j} = min (f_{i - 1, j}, f_{i, j - 1}, f_{i - 1, j - 1}) + 1$

$f_{i, j} = x$ nếu thỏa mãn đồng thời:

$a_{i, j} = 1$

$f_{i - 1, j} \geq x - 1$ và
$f_{i, j - 1} \geq x - 1$ và
$f_{i - 1, j - 1} \geq x - 1$ .

Đáp án:
- Cạnh lớn nhất của hình vuông thỏa mãn là
  $max (f_{i, j})$ với mọi
  $i, j$ .
- Số lượng hình vuông thỏa mãn là số lượng
  $f_{i, j}$ bằng kết quả cạnh lớn nhất.

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

O (n^{2})

Code

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

const int N = 1e3 + 5;

int n, m, f[N][N], a[N][N], res = 0, mp[N];

int main() {
    cin >> n >> m;
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a[i][j] == 1) {
                f[i][j] = min({f[i-1][j], f[i][j-1], f[i-1][j-1]}) + 1;
            }
            else {
                f[i][j] = 0;
            }
            
            res = max(res, f[i][j]);
            mp[f[i][j]]++;
        }
    }
    
    if (res == 0) {
        cout << -1;
    } 
    else {
        cout << res << ' ' << mp[res];
    }

    return 0;
}

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

Bài 1: Số chín ước

Subtask 1

Subtask 2

Subtask 3

Bài 2: Rương tiết kiệm

Lời giải

Bài 3: Bấm nút

Lời giải

Bài 4: Hình vuông

Subtask 1

Subtask 2

Read more

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

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

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

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