Try   HackMD

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

Thông tin

Sau đây là lời giải của Đề 5 trong chuỗi đề ôn tập TS10 & THTB 2025.

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

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

Bài 1: Bộ ba máy

Subtask 1

Ta duyệt qua mọi bộ

3 phần tử trong mảng rồi tìm giá trị
UCLN
lớn nhất của chúng.

Cách tính UCLN của ba số

  • UCLN(x,y)=
    __gcd(x, y)
  • UCLN(x,y,z)=UCLN(UCLN(x,y),z)

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

O(n3log).

Với

log tượng trưng cho độ phức tạp của hàm __gcd().

Code
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6;
int n, a[N+5];

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

    int res = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j < i; j++)
            for (int k = 1; k < j; k++)
                res = max(res, __gcd(__gcd(a[i], a[j]), a[k]));

    cout << res;

    return 0;
}

Subtask 2

Nhận xét

Ai106
UCLN(x,y,z)min(x,y,z)
, nên kết quả của bài chắc chắn sẽ nhỏ hơn hoặc bằng
106
.

Do đó, chúng ta có cách tiếp cận khác: Duyệt từng số

k và kiểm tra xem đó có phải
UCLN
của một bộ ba số bất kỳ trong mảng hay không.

Dễ thấy, nếu

k=UCLN(x,y,z) thì
k
phải thỏa mãn:
xmodk=ymodk=zmodk=0

Hay

kước chung của
x,y,z
, tức là trong mảng tồn tại ít nhất
3
số
chia hết cho
k
.

Để thực hiện được điều trên, ta gọi

cntjsố lượng số j có trong mảng
A
, và số
k
thỏa mãn điều kiện nếu
max(cntx)3
với
x
là bội của
k
.

Giải thích

Mặc dù số

k thỏa mãn điều kiện trên chưa chắc là
UCLN
của
x,y,z
.

Tuy nhiên, điều này không ảnh hưởng đến kết quả, vì ta sẽ lấy kết quả lớn nhất.

VD:

x=4,y=6,z=8
k=2
thỏa, đồng thời
k=4
(đáp án chuẩn) cũng thỏa.

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

O(XlogX) với
X=max(A1,A2,,An)
.

Với mỗi số từ

1 đến
X
, ta phải duyệt qua tất cả các bội của nó. Do đó số thao tác là:
X1+X2++XXXlogX

Code
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6;
int n, cnt[N+5], a[N+5];

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

    for (int x = N; x >= 1; x--) {
        int sum = 0;
        for (int j = x; j <= N; j += x) {
            //Duyệt qua tất cả bội của x
            sum += cnt[j];
            if (sum >= 3) {
                //Đã tìm thấy đáp án lớn nhất, ngừng chương trình
                cout << x;
                return 0;
            }
        }
    }
    
    return 0;
}

Bài 2: Mua hàng

Subtask 1

Tip

Ta có thể tính

k=rl+12 như sau:
Tính
x
bằng cách lấy
rl+1
chia nguyên cho 2: x = (r-l+1)/2;

  • Nếu
    rl+1
    lẻ thì
    k=x+1
    .
  • Nêú
    rl+1
    chẵn thì
    k=x
    .

Vì mảng

A đã được sắp xếp tăng dần, với mỗi truy vấn
(l,r)
ta dễ dàng tính được trọng số của đoạn là
al+rl+121
. Sau đó chỉ cần so sánh giá trị này với
k
.

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

O(q)

Code
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6;
long long n, q, k, a[N+5], pre[N+5], l[N+5], r[N+5];

int main() {
    cin >> n >> q >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    
    while (q--) {
        int l, r;
        cin >> l >> r;
        
        int pos = (r-l+1)/2;
        if ((r-l+1) % 2 != 0) pos++;
        
        if (a[l+pos-1] <= k)
            cout << "YES\n";
        else
            cout<<"NO\n";
    }
    
    return 0;
}

Subtask 2

Nhận xét

Ta không cần tính chính xác trọng số của đoạn.

Thay vào đó ta chỉ cần quan tâm trọng số của đoạn lớn hơn hay nhỏ hơn

k.

Để giá trị nhỏ thứ

rl+12 của đoạn lớn hơn hoặc bằng
k
, thì mọi phần tử sau phần tử trên cũng phải lớn hơn hoặc bằng
k
, tức là đoạn đó phải có ít nhất
(rl+1)rl+12
+ 1 phần tử lớn hơn hoặc bằng
k
.

VD: Đoạn có

5 phần tử,
rl+12=3
. Để phần tử nhỏ thứ
3
lớn hơn hoặc bằng
k
thì mọi phần tử nhỏ thứ
3,4,5
cũng phải lớn hơn hoặc bằng
k
.

Như vậy, bài toán trở thành đếm số lượng số trong đoạn lớn hơn hoặc bằng

k. Dễ dàng thực hiện được điều này bằng cách gán:

  • Những số lớn hơn hoặc bằng
    k
    thành
    1
    .
  • Những số bé hơn
    k
    thành
    0
    .

Sau đó sử dụng mảng cộng dồn (prefix sum) để tính nhanh số lượng số

1 trong đoạn.

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

O(n).

Code
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6;
int n, k, q, a[N+5], pre[N+5];

int main() {
    cin >> n >> q >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        
        if (a[i] > k) a[i] = 1;
        else a[i] = 0;
        
        pre[i] = pre[i-1] + a[i];
    }

    for (int i = 1; i <= q; i++) {
        int l, r;
        cin >> l >> r;
        
        int len = (r - l + 1);
        int k = len/2;
        if (len % 2 != 0) k++;
        
        if (pre[r] - pre[l-1] >= len - k + 1)
            cout << "NO\n";
        else
            cout << "YES\n";
    }
    
    return 0;
}

Bài 3: Dịch bệnh

Subtask 1

Nhận xét

Giá trị

d không thể lớn hơn phạm vi có đồng cỏ.

Như vậy, vì

ab104 nên
d104
.

Ta có thể duyệt từng giá trị

d và kiểm tra xem giá trị này có hợp lệ hay không như sau:

Đi theo chiều dương của trục số, nếu ta đặt một con bò ở vị trí

i thì ta sẽ đặt con bò tiếp theo ở vị trí
j
nhỏ nhất thỏa
ji+len
nhằm để dành những thảm cỏ ở xa hơn cho những con bò còn lại.

Để làm được như vậy, ta cần sắp xếp các đồng cỏ theo thứ tự tăng dần của đầu mút phải. Sau đó khởi tạo một con trỏ tại đồng cỏ đầu tiên tượng trưng cho vị trí để đặt bò, cùng lúc với việc đặt bò, ta sẽ di chuyển con trỏ từng chút một để tìm đồng cỏ gần nhất thỏa mãn điều kiện về khoảng cách.

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

O(mX) với
X
là phạm vi có cỏ.

Code
#include <bits/stdc++.h>
#define ii pair<long long,long long>
#define fi first
#define se second
using namespace std;
const int N = 1e6;
long long n, m, k, mx;
ii a[N+5];

bool check(long long len) {
    int pos = 1, cur = 1, cnt = 1;
    //pos: vị trí đặt bò hiện tại
    //cur: chỉ số của đồng cỏ đang xét
    
    while (pos+len <= mx) {
        //Nếu pos+len > mx thì không thể đặt thêm bò
        
        while (pos+len > a[cur].se && cur <= m) {
            //Nếu khoảng đồng cỏ cur không chứa tới pos+len
            //thì tìm đồng cỏ tiếp theo
            cur++;
        }
        
        if (cur > m) break;
        //Hết đồng cỏ, không đặt bò được
        
        pos = max(pos+len, a[cur].fi);
        cnt++;
        
        if (cnt == n) {
            //Đã đặt đủ n con bò
            return true;
        }
    }
    
    //Không đặt đủ n con bò
    return false;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> a[i].fi >> a[i].se;
        mx = max(mx, a[i].se);
    }

    sort(a+1, a+1+m);
    for (int i = 10000; i >= 1; i--){
        if (check(i)) {
            //Đã tìm thấy đáp án
            cout << i;
            break;
        }
    }
    
    return 0;
}

Subtask 2

Kế thừa tư tưởng của subtask 1, tuy nhiên có thêm nhận xét quan trọng sau đây:

Nhận xét

Vì khoảng cách giữa hai con bò càng nhỏ thì số bò đặt được càng nhiều, ngược lại với khi khoảng cách càng lớn, nên:

  • Nếu tồn tại cách đặt
    n
    con bò với
    d=x
    , các khoảng cách
    d<x
    cũng thỏa mãn.
  • Nếu không tồn tại cách đặt
    n
    con bò với
    d=x
    , các khoảng cách
    d>x
    cũng sẽ không thỏa mãn.

Đây là điều kiện cần thiết để thực hiện tìm kiếm nhị phân trên tập đáp án. Thay vì phải duyệt hết mọi giá trị

d để thử, ta chỉ phải thử
logX
giá trị
d
với
X
là khoảng tối đa mà có tồn tại cỏ.

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

O(mlogX).

Code
#include <bits/stdc++.h>
#define ii pair<long long, long long>
#define fi first
#define se second
using namespace std;
const int N = 1e5;
long long n, m, k, mx;
ii a[N+5];

bool check(long long len) {
    long long pos = a[1].fi, cur = 1, cnt = 1;
    //pos: vị trí đặt bò
    //cur: chỉ số của đồng cỏ đang xét

    while (pos+len <= mx) {
        while (pos+len > a[cur].se && cur <= m) {
            cur++;
        }

        if (cur > m) break;

        pos = max(pos+len, a[cur].fi);
        cnt++;

        if (cnt == n) {
            //Đã đặt đủ n con bò
            return true;
        }
    }

    //Không đặt đủ n con bò
    return false;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> a[i].fi >> a[i].se;
        mx = max(mx, a[i].se);
    }

    sort(a+1, a+1+m);

    long long l = 1, r = 1e18, res = 0;
    while (l <= r) {
        long long mid = (l+r)/2;
        if (check(mid)) {
            l = mid+1;
            res = mid;
        }
        else {
            r = mid-1;
        }
    }

    cout << res;

    return 0;
    }

Bài 4: Vương quốc

Lời giải

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

  • Định nghĩa:

    • dp1,i
      là chi phí nhỏ nhất để chiếu đèn cho
      i
      tòa nhà đầu tiên, trong đó tòa nhà thứ
      i
      được chiếu đèn màu lam.
    • dp2,i
      là chi phí nhỏ nhất để chiếu đèn cho
      i
      tòa nhà đầu tiên, trong đó tòa nhà thứ
      i
      được chiếu đèn màu chàm.
    • dp3,i
      là chi phí nhỏ nhất để chiếu đèn cho
      i
      tòa nhà đầu tiên, trong đó tòa nhà thứ
      i
      được chiếu đèn màu tím.
  • Khởi gán:

    • dp1,i=a1
      : Chiếu đèn màu lam cho tòa nhà
      1
      tốn chi phí
      a1
      .
    • dp2,i=b1
      : Chiếu đèn màu chàm cho tòa nhà
      1
      tốn chi phí
      b1
      .
    • dp3,i=c1
      : Chiếu đèn màu tím cho tòa nhà
      1
      tốn chi phí
      c1
      .
  • Công thức (với

    i2):

    • dp1,i=min(dp2,i1,dp3,i1)+ai
      : Nếu chiếu đèn màu lam cho tòa nhà thứ
      i
      , thì tòa nhà thứ
      i1
      chỉ có thể chiếu đèn màu chàm hoặc tím.
    • dp2,i=min(dp1,i1,dp3,i1)+bi
      : Nếu chiếu đèn màu chàm cho tòa nhà thứ
      i
      , thì tòa nhà thứ
      i1
      chỉ có thể chiếu đèn màu lam hoặc tím.
    • dp3,i=min(dp1,i1,dp2,i1)+ci
      : Nếu chiếu đèn màu tím cho tòa nhà thứ
      i
      , thì tòa nhà thứ
      i1
      chỉ có thể chiếu đèn màu lam hoặc chàm.
  • Kết quả:

    min(dp1,n,dp2,n,dp3,n).

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

O(n)

Code
#include <bits/stdc++.h> using namespace std; const int N = 1e6; int n; long long a[N+5], b[N+5], c[N+5], dp[5][N+5]; int main() { cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i] >> b[i] >> c[i]; } for (int i = 1; i <= n; i++) { dp[1][i] = min(dp[2][i-1], dp[3][i-1]) + a[i]; dp[2][i] = min(dp[1][i-1], dp[3][i-1]) + b[i]; dp[3][i] = min(dp[1][i-1], dp[2][i-1]) + c[i]; } cout << min({f[1][n], f[2][n], f[3][n]}); return 0; }