Đề THT B - BRVT - 2022: Editorial

Thông tin

Sau đây là lời giải của Kỳ thi Tin học trẻ bảng B tỉnh Bà Rịa - Vũng Tàu năm học 2021 - 2022.

Bạn đọc có thể nộp và chấm bài (test tự sinh) TẠI ĐÂY.

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

• Đề THT B - BRVT - 2022: Editorial
  • Bài 1: Tích nguyên tố (40 điểm)
    • Tóm tắt đề bài
    • Lời giải
  • Bài 2: Giao lưu (30 điểm)
    • Tóm tắt đề bài
    • Lời giải
  • Bài 3: Đội tuyển Tin học (30 điểm)
    • Tóm tắt đề bài
    • Lời giải:

Bài 1: Tích nguyên tố (40 điểm)

Tóm tắt đề bài

Cho số nguyên dương

$n$.

Yêu cầu: Tìm hai số nguyên tố khác nhau thỏa mãn tích của chúng là lớn nhất và tích đó không được vượt quá

$n$.

Lời giải

Tính chất 1

Với mọi số nguyên dương

$n$ luôn tồn tại hai số nguyên dương

$a,b$ thỏa

$n=a\times b$.

Không mất tính tổng quát, giả sử

$a\le b$. Khi đó ta có:

• $a\le \sqrt{n}$.
• $b\ge \sqrt{n}$.

Tính chất 2

Xét trong khoảng

${10}^9$ trở lại, cứ không quá

$200$ số nguyên liên tiếp, chắc chắn sẽ tồn tại một số nguyên tố.

Duyệt số nguyên tố

$a$ từ

$1$ đến

$n$ và tìm số nguyên tố

$b$ lớn nhất có thể thỏa mãn đề bài.

Ta biết:

$a\times b\le n$, tức là

$b\le \frac{n}{a}$. Như vậy, có thể duyệt

$b$ giảm dần từ

$\frac{n}{a}$ đến

$\frac{n}{a}-200$, nếu

$b$ là số nguyên tố thì lấy kết quả và chuyển tới số

$a$ tiếp theo.

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

$O(\sqrt{n}\times 200\times \sqrt{n})$.

Tuy nhiên, độ phức tạp thực tế thâp hơn nhiều, do các trường hợp ta tìm được

$b$ sớm, và khi kiểm tra tính nguyên tố ta cũng có không cần duyệt hết căn của số đó.

Code

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

int n;
bool isPrime[32000];

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

int main(){
    cin >> n;

    for (int i = 2; i*i <= n; i++) {
        isPrime[i] = true;
    }

    for (int i = 2; i*i*i*i <= n; i++) {
        if (isPrime[i] == true) {
            for (int j = i*i; j*j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }

    int MaxVal = 0, a, b;
    for (int i = 2; i*i <= n; i++) {
        if (isPrime[i] == true) {
            int lim = n / i;
            for (int j = lim; j >= 1; j--) {
                if (Prime(j)) {
                    if (i * j < MaxVal || i == j) break;
                    MaxVal = i * j;
                    a = i;
                    b = j;
                }
            }
        }
    }

    cout << a << ' ' << b;

    return 0;
}

Bài 2: Giao lưu (30 điểm)

Tóm tắt đề bài

Tại mỗi thời điểm, dữ liệu cho số

$0$ tương ứng với có

$1$ học sinh đi ra khỏi trường, và số

$1$ nếu có

$1$ học sinh đi vào trường.

Yêu cầu: Tính số học sinh ở trong trường nhiều nhất tại

$1$ thời điểm.

Lời giải

Gọi

$cur$ là số học sinh đang có trong trường.

Ta duyệt qua từng thời điểm:

• Nếu có học sinh ra khỏi trường (số
  $0$)
  $\to$
  $cur=cur-1$.
• Nếu có học sinh đi vào trường (số
  $1$)
  $\to$
  $cur=cur+1$.

Đáp án: Giá trị lớn nhất của

$cur$ tại mọi thời điểm.

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

$O(n)$

Code

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

int main(){
    int n; 
    cin >> n;
    
    int cur = 0, res = 0;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        
        if (x == 0) cur--;
        else cur++;
        
        res = max(res, cur);
    }
    
    cout << res;

    return 0;
}

Bài 3: Đội tuyển Tin học (30 điểm)

Tóm tắt đề bài

Có

$n$ học sinh, cho biết thời gian luyện tập của học sinh thứ

$i$ là từ

$l_i$ đến

$r_i$.

Thời gian luyện tập hiệu quả là thời gian mà chỉ có duy nhất một học sinh đang luyện tập.

Yêu cầu: Hãy chọn ra 1 số học sinh từ

$n$ học sinh trên sao cho tổng thời gian luyện tập hiệu quả là lớn nhất.

Lời giải:

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

Thứ tự quy hoạch động

Để có thứ tự quy hoạch động, ta cần sắp xếp các học sinh lại theo thứ tự tăng dần của thời gian kết thúc giờ luyện tập (

$r_i$ tăng dần).

• Định nghĩa:
  $f_i$ là thời gian luyện tập hiệu quả nhiều nhất nếu chọn một số học sinh trong
  $i-1$ học sinh trước đó và chắc chắn chọn học sinh
  $i$.
• Khởi gán:
  $f_i=r_i-l_i$ (trường hợp chỉ lấy học sinh
  $i$).
• Công thức: (nếu lấy học sinh thứ
  $i$ xếp vào ngay sau học sinh
  $j$)
  
  $$f_i=max(f_i,f_j-max(0,r_j-l_i)+r_i-max(r_j,l_i))$$

Trong đó:

• $r_j-l_i$ là khoảng thời gian học không hiệu quả.
• $r_i-max(r_j,l_i)$ là khoảng thời gian học tập hiệu quả của học sinh
  $i$.

Đáp án:

$max(f_i)\mathrm{\forall }i$.

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

$O(n^2)$.

Code

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

const int N = 1e4 + 5;
int n, f[N];

struct students {
    int L, R;
} a[N];

bool cmp(const students &a, const students &b) {
    return a.R < b.R;
}

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

    sort (a + 1, a + 1 + n, cmp);

    int res = 0;
    for (int i = 1; i <= n; i++) {
        f[i] = a[i].R - a[i].L;
        for (int j = 1; j < i; j++) {
            f[i] = max(f[i], f[j] - max(0, a[j].R - a[i].L) + a[i].R - max(a[j].R, a[i].L));
        }
        
        res = max(res, f[i]);
    }

    cout << res;

    return 0;
}