Đề TS10 - BRVT - 2015: Editorial

Thông tin

Sau đây là lời giải của Kỳ thi Tuyển sinh 10 trường THPT chuyên Lê Quý Đôn tỉnh Bà Rịa - Vũng Tàu năm học 2015 - 2016.

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)

• Đề TS10 - BRVT - 2015: Editorial
  • Bài 1:
    • Tóm tắt đề bài
    • Tính biểu thức A
    • Tính biểu thức B
    • Tính biểu thức C
  • Bài 2:
    • Tóm tắt đề bài
    • Tìm bội chung nhỏ nhất
    • Cho biết số có số lượng ước chẵn hay lẻ
  • Bài 3
    • Tóm tắt đề bài
    • Liệt kê mọi số nguyên dương chẵn
    • Tính giá trị nhỏ nhất của dãy
    • Kiểm tra xem dãy có gồm toàn số nguyên tố hay không
    • Tìm đoạn con liên tiếp có nhiều phần tử âm nhất
    • Tìm số nguyên dương nhỏ nhất không xuất hiện trong dãy
  • Bài 4: Công ty
    • Tóm tắt đề
    • Lời giải

Bài 1:

Tóm tắt đề bài

Cho số nguyên dương

$n$. Tính giá trị các biểu thức sau:

$$\begin{array}{rl}A& =\sum _{i=3}^n\frac{1}{i}\\ B& =\prod _{i=3}^n(\frac{i-2}{i-1}-\sqrt{i})\\ C& =\sum _{i=1}^{2n+1}(-1{)}^i\cdot \frac{2^i}{i!}\end{array}$$

Tính biểu thức A

Khởi gán

$A=0$. Duyệt qua mọi

$i\in [3,n]$ và cộng

$\frac{1}{i}$ vào A.

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

$O\left(n\right)$

Tính biểu thức B

Khởi gán

$B=1$. Duyệt qua mọi

$i\in [3,n]$ và nhân

$\frac{i-2}{i-1}-\sqrt{i}$ vào B.

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

$O\left(n\right)$

Tính biểu thức C

Gọi

$f(i)=\frac{2^i}{i!}$. Khi này:

• $f(0)=1$
• $f(i)=f(i-1)\cdot \frac{2}{i}$.

Khởi gán

$C=0$.

Duyệt qua mọi

$i\in [1,n]$, nếu

$i$ lẻ thì cộng

$f(i)$ vào

$C$, ngược lại trừ

$f(i)$ vào

$C$.

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

$O\left(n\right)$

Lưu ý: Vì bài toán liên quan tới số thực. Vậy nên cần sử dụng kiểu dữ liệu double hoặc long double để đảm bảo độ chính xác.

Độ phức tạp thời gian của cả bài toán là tổng độ phức tạp thời gian của từng yêu cầu.

Code

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

int n;
long double A = 0, B = 1, C = 0, v = 1;

int main() {
    cin >> n;
    for (int i = 3; i <= n; i++) {
        A += (long double)1 / i;
    }
    
    for (int i = 3; i <= n; i++) {
        B *=  (long double)(i - 2) / (i - 1) - sqrtl(i);
    }
    
    for (int i = 1; i <= 2*n+1; i++) {
        v *= (long double)2 / i;
        if (i & 1) {
            C += v;
        }
        else {
            C -= v;
        }
    }
    
    cout << fixed << setprecision(4) << A << '\n' << B << '\n' << C;
    
    return 0;
}

Bài 2:

Tóm tắt đề bài

Cho 3 số nguyên dương

$n,a,b$.

• Tìm bội chung nhỏ nhất của
  $a$ và
  $b$.
• Cho biết
  $n$ có số lượng ước chẵn hay lẻ.

Tìm bội chung nhỏ nhất

Tip

Bội chung nhỏ nhất của

$a$ và

$b$ là:

$$\mathrm{BCNN}(a,b)=\frac{a\cdot b}{\mathrm{UCLN}(a,b)}$$

Sử dụng hàm gcd() có sẵn trong thư viện STL của C++, dễ dàng tính được đáp án.

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

$O(\log min(a,b))$

Đây là độ phức tạp của thuật toán Euclid để tính UCLN.

Cho biết số có số lượng ước chẵn hay lẻ

Nhận xét

Nếu một số nguyên dương

$x\ne 1$ là số chính phương thì có số lượng ước lẻ, ngược lại số lượng ước là chẵn.

Chứng minh

• Một số nguyên dương
  $x\ne 1$ có thể được viết dưới dạng
  $p_1^{a_1}\times p_2^{a_2}\dots p_k^{a_k}$, với
  $p_i$ là ước số nguyên tố của
  $x$.

• Số lượng ước của
  $x$ được tính theo công thức
  $d(x)=(a_1+1)(a_2+1)\dots (a_k+1)$.

• Nếu
  $x$ là số chính phương khác
  $1$, mọi ước nguyên tố
  $p_i$ đều có số mũ chẵn, tức mọi
  $a_i$ chẵn, hay mọi
  $a_i+1$ đều là số lẻ. Khi này,
  $d(x)$ lẻ.
• Ngược lại, khi này tồn tại
  $p_i$ có số mũ lẻ, tức
  $a_i$ lẻ, hay
  $a_i+1$ là số chẵn. Khi này
  $d(x)$ chẵn.

Bài toán quy về kiểm tra một số có phải số chính phương hay không.

Ta có thể kiểm tra một số

$x$ có phải số chính phương hay không bằng cách lấy bình phương phần nguyên của

$\sqrt{x}$, nói cách khác, kiểm tra biểu thức sau đây có thỏa không:

$${\lfloor \sqrt{x}\rfloor }^2=x$$

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

$O(\log n)$

Đây là độ phức tạp của hàm sqrt() trong C++ STL.

Độ phức tạp thời gian của cả bài toán là tổng độ phức tạp thời gian của từng yêu cầu.

Code

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

long long a, b, n;

long long lcm(long long a, long long b) {
    return a * b / __gcd(a, b);
}

bool sqr(long long x) {
    long long t = sqrt(x);
    return t * t == n;
}

int main() {
    cin >> a >> b >> n;
    cout << lcm(a, b) << '\n' << sqr(n);
    return 0;
}

Bài 3

Tóm tắt đề bài

Cho dãy số nguyên gồm

$n$ phần tử

$a_1,a_2,\dots ,a_n$. Yêu cầu:

• Liệt kê mọi số nguyên dương chẵn
• Tính giá trị nhỏ nhất của dãy
• Kiểm tra xem dãy có gồm toàn số nguyên tố hay không
• Tìm đoạn con liên tiếp có nhiều phần tử âm nhất
• Tìm số nguyên dương nhỏ nhất không xuất hiện trong dãy

Liệt kê mọi số nguyên dương chẵn

Duyệt qua mọi

$i\in [1,n]$, nếu

$a_i$ chia hết cho 2 thì in ra

$a_i$

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

$O\left(n\right)$

Tính giá trị nhỏ nhất của dãy

Gọi

$f_{min}$ là giá trị nhỏ nhất của dãy, khởi gán

$f_{min}=\mathrm{\infty }$. Duyệt qua mọi

$i\in [1,n]$, nếu

$a_i<f_{min}$ gán

$f_{min}=a_i$.

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

$O\left(n\right)$

Kiểm tra xem dãy có gồm toàn số nguyên tố hay không

Sử dụng thuật toán kiểm tra số nguyên tố trong căn bậc 2 hoặc sàng nguyên tố Eratosthenes để giải bài toán.

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

• $O\left(\sum _{i=1}^n{\sqrt{a}}_i\right)$ nếu kiểm tra trong căn bậc 2.
• $O(A\log A)$ với
  $A=max(a_i)$ nếu kiểm tra bằng sàng nguyên tố.

Tìm đoạn con liên tiếp có nhiều phần tử âm nhất

Áp dụng quy hoạch động cơ bản.

Gọi

$f(i)$ là đoạn con có nhiều phần tử âm nhất kết thúc tại i. Khi này:

$$f(i)=\{\begin{array}{l}{a}_i<0,f(i-1)+1\\ a_i\ge 0,0\end{array}$$

Đáp án:

$max(f(1),f(2)\dots ,f(n))$.

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

$O\left(n\right)$

Tìm số nguyên dương nhỏ nhất không xuất hiện trong dãy

Gọi

$mark(x)$ biểu thị

$x$ có xuất hiện hay không:

• $mark(x)=0$ nếu x không tồn tại trong dãy.
• Ngược lại,
  $mark(x)=1$.

Duyệt qua mọi

$i\in [1,n]$, nếu

$a_i>0$ thì đánh dấu

$mark(a_i)=1$.

Sau đó duyệt qua mọi giá trị

$x\in [1,n+1]$, nếu

$mark(x)=0$ thì

$x$ là số nguyên dương nhỏ nhất không xuất hiện trong dãy.

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

$O\left(n\right)$

Độ phức tạp thời gian của cả bài toán là tổng độ phức tạp thời gian của từng yêu cầu.

Code

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

int main() { 
    int n;
    vector<int> a;
    vector<bool> f, mark;

    cin >> n;
    
    a.resize(n);
    f.resize(n+5,true);
    mark.resize(n+5,false);
    
    for (auto &x : a) {
        cin >> x;
    }
    for (auto &x : a) {
        if (x > 0 && !(x & 1)) {
            cout << x << ' ';
        }
    }
    
    cout << '\n' << *min_element(a.begin(),a.end()) << '\n';
    
    f[0] = f[1] = 0;
    for (int i = 1, t = sqrt(n); i <= t; i++) {
        if (f[i]) {
            for (int j = i * i; j <= n; j += i) {
                f[j] = 0;
            }
        }
    }
    
    bool ans = 1;
    for (auto &x : a) {
        if (x < 0 || !f[x]) {
            ans = 0;
            break;
        }
    }
    
    cout << (ans ? "YES" : "NO") << '\n';

    int max_len = 0, cur_len = 0;
    for (auto &x : a) {
        if (x >= 0) {
            if (cur_len > max_len) max_len = cur_len;
            cur_len = 0;
        }
        else {
            cur_len++;
        }
    }
    
    if (cur_len > max_len) {
        max_len = cur_len;
    }
    
    cout << max_len << '\n';

    for (auto &x : a) {
        if (!mark[x] && x > 0) {
            mark[x] = 1;
        }
    }
    
    for (int i = 1; i <= n + 1; i++) {
        if (!mark[i]) {
            cout << i;
            break;
        }
    }
}

Bài 4: Công ty

Tóm tắt đề

Cho

$n$ đoạn thẳng, đoạn thứ

$i$ kéo dài từ

$a_i$ đến

$b_i$. Hỏi số lượng đoạn thẳng giao nhau tại cùng một điểm nhiều nhất là bao nhiêu.

Lời giải

Đây là một bài toán sweep line cơ bản.

Nhận xét

Chỉ điểm đầu và điểm cuối của mỗi đoạn sẽ ảnh hưởng tới số lượng đoạn thẳng giao nhau tại một điểm.

Gọi

$f(x)$ là số lượng đoạn thẳng có chứa điểm

$x$. Với mọi

$i\in [1,n]$, tăng

$f(a_i)$ lên

$1$ và giảm

$f(b_i+1)$ đi

$1$.

Biểu thị khi đến điểm

$a_i$, đoạn thẳng thứ

$i$ bắt đầu xuất hiện, còn khi đến

$b_i+1$ thì đoạn thẳng thứ

$i$ kết thúc.

Sau đó duyệt qua mọi điểm

$x_i$ có tồn tại trong mảng

$f$ theo thứ tự tăng dần, ta tính được

$f(x_i)$ theo công thức sau

$f(x_i)=f(x_i)+f(x_{i-1})$.

Tại bất cứ thời điểm nào,

$f(x_i)$ cho ta biết số lượng đoạn thẳng đi qua điểm

$x_i$.

Đáp án là

$max(f(x_1),f(x_2),\dots ,f(x_k))$.

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

$O(n\log n)$

Code

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

int main() {
    int n;
    vector<array<int,2>> event;

    cin >> n;
    for (int i = 1; i <= n; i++) {
        int a, b;
        cin >> a >> b;
        event.push_back({a, 1});
        event.push_back({b+1, -1});
    }
    
    sort(event.begin(),event.end());
    int virus = 0, max_virus = 0;
    
    for (auto &e : event) {
        virus += e[1];
        max_virus = max(max_virus, virus);
    }
    
    cout << max_virus;
    
    return 0;
}