Try   HackMD

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

Thông tin

Sau đây là lời giải của Đề 4 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: Không tương đồng

Nhận xét

Để không tồn tại

2 số nguyên dương khác
1
là ước chung của
m
n
,
m
n
chỉ được phép có ước chung là
1
và tối đa một số nguyên tố (có thể có hoặc không)
.

Subtask 1

Duyệt mọi số

m[l,r], sau đó duyệt qua từng ước của
m
, và đếm số lượng ước chung của
m
n
.

Nếu số lượng ước chung khác

1 lớn hơn hoặc bằng
2
, cặp số
n,m
này không phải là cặp số không tương đồng. Ngược lại, ta ghi nhận thêm một cặp số không tương đồng.

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

O((rl+1)×m).

Code

Subtask 2

Nhận xét

Mọi uớc chung của

n
m
đều là ước của
UCLN(n,m)
.

Như vậy, để kiểm tra hai số

n,m có nhiều hơn
2
ước chung khác
1
hay không, ta chỉ cần kiểm tra xem
UCLN(n,m)
có không quá
2
ước khác
1
hay không.

Trường hợp trên chỉ xảy ra khi:

  • UCLN(n,m)=1
  • UCLN(n,m)
    là số nguyên tố.

Như vậy, để giải bài này, ta thực hiện kiểm tra

UCLN(n,m) có phải là số nguyên tố hay không với mọi
m[l,r]
.

Chú ý điều kiện

mn

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

O((rl+1)×logm×m).

log là chi phí để tính
UCLN
bằng hàm __gcd().
m
là chi phí để kiểm tra tính nguyên tố của
m
.

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

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

int main() {
    long long n, l, r;
    cin >> n >> l >> r;

    vector<long long> ans;
    for (long long i = l; i <= r; ++i) {
        long long g = __gcd(i, n);
        if (i != n && (g == 1 || isPrime(g))) {
            ans.push_back(i);
        }
    }

    cout << ans.size() << "\n";
    for (auto x : ans) {
        cout << x << " ";
    }
    
    cout << "\n";
    
    return 0;
}

Bài 2: Xếp đĩa

Lời giải

Nhận xét

Dễ dàng quan sất thấy, nên chọn đĩa có độ bền lớn nhất đặt làm đáy vì đĩa nằm ở dưới cùng sẽ phải chịu tải nhiều nhất.

Tổng quát hơn, đĩa càng nằm sâu ở dưới sẽ càng có độ bền lớn, tức là độ bền của đĩa giảm dần từ dưới đáy lên đỉnh.

Như vậy, ta sắp xếp lại các chiếc đĩa theo độ bền giảm dần và lần lượt xếp những chiếc đĩa từ đầu dãy tạo thành một tháp.

Trong lúc xây tháp, ta kiểm tra xem có đĩa nào bị quá tải hay không bằng cách duy trì biến

min là độ bền còn lại của đĩa có độ bền nhỏ nhất. Một khi độ bền về
0
, ta không thể đặt thêm đĩa được nữa.

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

O(nlogn).

Độ phức tạp của hàm sort().

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

const int N = 1e6 + 9;
int a[N];

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

    sort(a + 1, a + n + 1, greater<int>());

    int mini = a[1];
    int cnt = 1;

    for (int i = 2; i <= n; ++i) {
        if (mini <= 0) {
            break;
        }
            
        mini = min(mini - 1, a[i]);
        ++cnt;
    }

    cout << cnt;

    return 0;
}

Bài 3: Khôi phục mảng

Lời giải

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

  • Định nghĩa:
    dpi,j
    là số cách tạo ra một dãy thỏa mãn từ
    1
    đến
    i
    , trong đó
    Ai=j
    .
  • Khởi gán:
    • Ban đầu, mọi giá trị
      dp
      đều bằng
      0
      .
    • Nếu
      A1=0
      ,
      dp1,A1=1
      : Chỉ có một cách đặt giá trị cho
      A1
      A1
      .
    • Nếu
      A10
      ,
      dp1,j=1
      với
      j[1,m]
      : Vì
      A1
      chưa xác định, có thể đặt nó bằng giá trị từ
      1
      đến
      m
      .
  • Công thức (với
    i2
    ):
    • Nếu
      Ai=0
      ,
      dpi,j=dpi1,j1+dpi1,j+dpi1,j+1
      : Thử gán
      Ai=j
      với
      j
      chạy từ
      1
      đến
      m
      . Nếu muốn gán
      Ai=j
      thì
      Ai1
      không được chênh quá
      1
      đơn vị với
      j
      , tức là chỉ có thể nhận các giá trị
      j1,j,j+1
      .
    • Nếu
      Ai0
      ,
      dpi,Ai=dpi1,Ai1+dpi1,Ai+dpi1,Ai+1
      : Chỉ có thể giữ nguyên giá trị
      Ai
      , khi đó
      Ai1
      không được chênh quá
      1
      đơn vị với
      Ai
      , tức là chỉ có thể nhận các giá trị
      Ai1,Ai,Ai+1
      .

Độ phức tạp

O(nm).

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

const int N = 100006;
const int M = 105;
const int MOD = 1000000007;

int f[N][M];

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

    if (a == 0) {
        for (int i = 1; i <= m; ++i) {
            f[1][i] = 1;
        }
    } else {
        f[1][a] = 1;
    }

    for (int i = 2; i <= n; ++i) {
        cin >> a;
        if (a!=0) {
            f[i][a] = (f[i - 1][a + 1] + f[i - 1][a] + f[i - 1][a - 1]) % MOD;
        } else {
            for (int j = 1; j <= m; ++j) {
                f[i][j] = (f[i - 1][j + 1] + f[i - 1][j] + f[i - 1][j - 1]) % MOD;
            }
        }
    }

    int res = 0;
    for (int i = 1; i <= m; ++i) {
        res = (res + f[n][i]) % MOD;
    }

    cout << res << '\n';
    return 0;
}



Bài 4: Trung vị hình vuông

Subtask 1

Duyệt bảng, tính giá trị ở từng ô và đưa vào một mảng. Sau đó sắp xếp lại và đưa ra số trung vị của dãy.

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

O(n2logn2).

Ta cần sắp xếp một dãy có

n2 phần tử.

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

vector<long long> V;
long long n;

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			V.push_back((long long)i*j);

	sort(V.begin(), V.end());
	cout << V[n*n/2];

	return 0;
}

Subtask 2

Nhận xét

Gọi

f(x) là số lượng số nhỏ hơn hoặc bằng
x
trong bảng.

Đáp án của bài chính là số

x nhỏ nhất thỏa
f(x)>n22
. Vì
x
tăng thì
f(x)
cũng tăng, nên dễ dàng tính được đáp án bằng tìm kiếm nhị phân trên tập đáp án.

Giá trị nhỏ nhất trong bảng nhân là

1 và giá trị lớn nhất là
n2
, đây cũng là khoảng đáp án mà ta sẽ thực hiện tìm kiếm nhị phân.

Để tính

f(x) với một số
x
bất kỳ, ta thực hiện như sau:

  • Duyệt qua từng hàng từ
    1
    đến
    n
    .
  • Tại hàng
    i
    , ta có các giá trị
    i,2i,3i,,ni
    (tương ứng với ô ở cột
    1,2,,n)
    .
  • Số lượng số nhỏ hơn hoặc bằng
    x
    trong hàng
    i
    xi
    .

Các giá trị ở hàng

i có dạng
i×j
với
1jn
.
i×jxjxi

j
là số nguyên, do đó ta lấy
xi
làm tròn xuống.

Khi tính

f(x), chú ý chúng ta chỉ lấy số trong phạm vi của bảng, tức là tối đa chỉ có
n
số. Vậy số lượng số nhỏ hơn hoặc bằng
x
trong hàng
i
min(n,xi)
.

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

O(nlogn2)

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

long long n, res;

long long check(long long x) {
    long long cnt = 0;
    
    for (int i = 1; i <= n; i++) {
        cnt += min(x/i, n);
    }
    
    return cnt;
}

int main() {
    cin >> n;
    
    long long l = 1, r = n*n, k = (n * n ) / 2;
    while (l <= r) {
        long long mid = (l+r)/2;
        if (check(mid) > k){
            r = mid - 1;
            res = mid;
        }
        else {
            l = mid + 1;
        }
    }

    cout << res;

    return 0;
}