Try   HackMD

Ô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)

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
    x
    , nếu
    n
    chia hết cho
    i
    thì nghĩa là tồn tại
    2
    ước của
    n
    i
    xi
    .

Chú ý trường hợp

i=xi.

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(l+l+1++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
    cntx
    là số lượng ước của
    x
    .
  • Với mỗi số từ
    1
    đến
    106
    , thực hiện duyệt qua các bội
    x
    của nó và tăng
    cntx
    lên
    1
    .

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

O(106log106).

1061+1062++106106106log106.

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

O(106log106)

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=p1x1×p2x2×p3x3pkxk, trong đó:

  • pi
    là thừa số nguyên tố thứ
    i
    của
    n
    .
  • xi
    là số mũ của thừa số nguyên tố thứ
    i
    của
    n
    .

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

(x1+1)×(x2+1)×(x3+1)(xk+1)

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

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

  • n=p8
    (số ước của
    n
    8+1=9
    ).
  • n=p12×p22
    (số ước của
    n
    (2+1)×(2+1)=3×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=p8
x=p12×p22=(p1×p2)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à
li8r
thì
i8
là một số thỏa mãn đề bài.

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

O(r8).

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

i8>r.

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

Ta có:

(p1×p2)2rp1×p2r
Đề bài cho
r109r<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(34012).

Độ 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à
    sum
    .
  • Khi này, ta chỉ cần bỏ thêm
    ksum
    đồ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(nlogn)

nlogn 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ế (ô
    i1
    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:

  • ai=ai+1==aj
  • ai>ai1
    aj>aj+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
    aj+1=aj
    , 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:
    ai>ai1
    aj>aj+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+k1,j+k1]
.

Để 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
k2
.

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(n5)

Đâ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,m50.

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
ai,j=1
và cũng có thể tạo ra ba hình vuông toàn
1
cạnh
x1
có góc phải dưới là ô
(i1,j),(i,j1),(i1,j1)
.
Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

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

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

fi,j=x nếu thỏa mãn đồng thời:

  • ai,j=1
  • fi1,jx1
    fi,j1x1
    fi1,j1x1
    .
  • Đáp án:
    • Cạnh lớn nhất của hình vuông thỏa mãn là
      max(fi,j)
      với mọi
      i,j
      .
    • Số lượng hình vuông thỏa mãn là số lượng
      fi,j
      bằng kết quả cạnh lớn nhất.

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

O(n2)

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;
}