# Đề TS10 - BRVT - 2015: Editorial

>[!Note] 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](https://chuyentin-brvt.online/contest/algi_ts10_15_24).
>
>:::info
>Chuẩn bị bởi ==team Logica==, thuộc khuôn khổ dự án [**The Algitect (ALGI Project)**](https://www.facebook.com/algitect.project)
>:::

[toc]

## 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{align}
A &= \sum_{i=3}^{n} \; \frac{1}{i} \\
B &= \prod_{i=3}^{n} \; \left( \frac{i-2}{i-1} - \sqrt{i} \right) \\
C &= \sum_{i=1}^{2n+1} \; (-1)^{i} \cdot \frac{2^i}{i!}
\end{align}

### 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)$

:::danger
**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.
:::

:::info
Độ 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.
:::

:::success
:::spoiler 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à:
> :::info
> $$
> \operatorname{BCNN}(a, b) = \frac{a \cdot b}{\operatorname{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 \left( \log \min(a, b) \right)$
> Đâ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ẻ

>[!Tip] Nhận xét
> Nếu một số nguyên dương $x \not = 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==.

>[!Note] Chứng minh
>:::info
>- Một số nguyên dương $x \not = 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$.
>:::
>:::info
>- 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)$.
>:::
>:::info
>- 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:
$$
\left \lfloor \sqrt x \right \rfloor ^ 2 = x
$$

**Độ phức tạp thời gian:** $O \left( \log n \right)$
> Đây là độ phức tạp của hàm `sqrt()` trong C++ STL.

:::info
Độ 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.
:::

:::success
:::spoiler 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} = \infty$. Duyệt qua mọi $i \in [1,n]$, nếu $a_i \lt 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**](https://blog.28tech.com.vn/sang-so-nguyen-to) để 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 \left( A \log A \right)$ 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{cases}
a_i \lt 0 , \; f(i-1) + 1\\
a_i \ge 0 , \; 0
\end{cases}
$$

**Đá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)$

:::info
Độ 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.
:::

:::success
:::spoiler 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.

>[!Tip] 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 \left( n \log n \right)$

:::success
:::spoiler 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;
}

:::