# Đề TS10 - BRVT - 2019: 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 2019 - 2020.
>
>**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 một số nguyên dương $n$.

**Yêu cầu:** Tính giá trị các biểu thức:

$$\begin {flalign}\
A &= \frac{1}{3}+\frac{2}{4}+\dots+\frac{n-1}{n+1}
\\
B &= \frac{1}{4 \times 6} + \frac{1}{6 \times 8} + \frac{1}{2n \times (2n + 2)}
\end {flalign}
$$

**Dữ liệu đảm bảo:** $2 \le n \le 100$.

### **Tính biểu thức A**
- Duyệt $i$ từ $1$ đến $n-1$, cộng vào đáp án $\frac{i}{i+2}$.
- **Độ phức tạp thời gian**: $O(n)$.

### **Tính biểu thức B**
- Duyệt $i$ từ $2$ đến $n$, cộng vào đáp án $\frac{1}{2i \times (2i + 2)}$.
- **Độ phức tạp thời gian**: $O(n)$.

:::danger
**Lưu ý**: Lưu đáp án bằng kiểu **số thực**.
:::

### **Mã nguồn mẫu**

:::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;
    cin >> n;
    
    double A = 0;
    for (int i = 1; i <= n - 1; i++) {
        A += (double)i / (i + 2);
    }

    double B = 0;
    for (int i = 2; i <= n; i++) {
        B += (double) 1 / (i * 2 * (i * 2 + 2));
    }
    
    cout << fixed << setprecision(5) << A << '\n' << B << '\n';

    return 0;
}

:::

## Bài 2:

### Tóm tắt đề bài

Cho một số nguyên dương $n$.

**Yêu cầu**:
- Tìm chữ số tận cùng của $3^n$.
- Tính biểu thức:
$$
C =\frac{n \times (n^2 - 1) \times (n^2 - 4) }{5} \bmod 2019
$$

**Dữ liệu đảm bảo:** $2 \le n \le 10^6$.

### **Yêu cầu 1**

>[!Tip] Nhận xét
> Những số $n$ với ==$n \bmod 4$== bằng nhau có cùng ==chữ số tận cùng==.

:::info
**Chứng minh**

Xuất phát từ $3^0 = 1$.

$3^1 = 1 \times 3 = 3 \rightarrow 3 \bmod 10 = 3$

$3^2 = 3 \times 3 = 9 \rightarrow 9 \bmod 10 = 9$

$3^3 = 3 \times 9 = 27 \rightarrow 27 \bmod 10 = 7$

$3^4 = 3 \times 27 = 81 \rightarrow 81 \bmod 10 = 1$

Ta lại quay về giá trị $3^0 = 1$ ở ban đầu, dẫn đến sau đó ==chu kỳ== gồm ==$1, 3, 9, 7$== này sẽ lặp đi lặp lại.

Như vậy, với những số $n$ mà $n \bmod 4$ bằng nhau thì chữ số tận cùng của $3^n$ tương ứng cũng bằng nhau.
:::

Cụ thể, ta có các trường hợp:
- $n \bmod 4 = 0 \Leftrightarrow 3^n \bmod 10 = 1$
- $n \bmod 4 = 1 \Leftrightarrow 3^n \bmod 10 = 3$
- $n \bmod 4 = 2 \Leftrightarrow 3^n \bmod 10 = 9$
- $n \bmod 4 = 3 \Leftrightarrow 3^n \bmod 10 = 7$

**Độ phức tạp thời gian**: $O(1)$.

### **Yêu cầu 2**

Ta không thể tính trực tiếp biểu thức $C$ rồi sau đó mới $\bmod$ vì sẽ tràn dữ liệu.

>[!Tip] Tính chất chia dư
> Ta thừa nhận tính chất sau đây với $p = b \times c$:
> $$
> \frac{a}{b} \bmod c = \frac {a \bmod p}{b}
> $$

Thay vào biểu thức $C$ với $p = 2018 \times 6$ ta được
$$
C =\frac{n \times (n^2 - 1) \times (n^2 - 4) \bmod p}{6}
$$
> Chú ý kết hợp modulo khi nhân để tránh tràn số

**Độ phức tạp thời gian:** $O\left( 1 \right)$

### **Mã nguồn mẫu**

:::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

:::

## Bài 3:

### Tóm tắt đề bài

Nhập vào một dãy số nguyên dương gồm $n$ phần tử $a_1, a_2, \dots, a_n$

**Yêu cầu:**
- In ra các phần tử của dãy có chữ số tận cùng là $0$ hoặc $5$.
- In ra số lượng các phần tử của dãy có dạng $4k + 1$ ($k$ là số nguyên).
- In ra các phần tử của dãy là số chính phương (số nguyên dương $x$ được gọi là số chính phương nếu tồn tại số nguyên $k$ sao cho $k^2 = x$).
- In ra độ dài lớn nhất của dãy con xuất hiện trong dãy sao cho các phần tử (trừ phần tử đầu tiên) là bội số của phần tử đứng liền trước trong dãy con.

**Dữ liệu đảm bảo:** $2 \le n \leq 10^5$ và $1 \le a_i \leq 10^6$.

### **Yêu cầu 1**

Duyệt qua từng giá trị trong dãy, lấy ==chữ số tận cùng== của giá trị bằng cách chia dư cho $10$. Nếu chữ số cuối cùng là $0$ hoặc $5$ thì in ra số đó.

**Độ phức tạp thời gian:** $O \left(n\right)$.

### **Yêu cầu 2**

Một số nguyên dương $x$ có dạng $4k+1$ khi ==$x \bmod 4 = 1$==.

Do đó, ta duyệt qua mọi phần tử và in ra các phần tử thỏa mãn điều kiện trên.

**Độ phức tạp thời gian:** $O \left( n \right)$.

### **Yêu cầu 3**

>[!Tip]Kiểm tra số chính phương
>:::success
>==Số chính phương== là bình phương của một số nguyên.
>:::
>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$== so sánh với ==$x$==.
>Nghĩa là, $x$ chính phương khi và chỉ khi:
>$$
>\left \lfloor \sqrt x \right \rfloor ^ 2 = x
>$$

Duyệt qua các phần tử trong mảng và thực hiện như trên. Có thể tính nhanh $\sqrt x$ bằng hàm có sẵn trong thư viện của C++ là `sqrt()`.

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

### **Yêu cầu 4**

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

- **Định nghĩa:** $dp_x$ là độ dài dãy con dài nhất kết thúc tại giá trị $x$.
- **Khởi gán:** $dp_x = 1 \; \forall \; x$ (dãy con một phần tử cũng thỏa đề bài).
- **Công thức:** $dp_x = \max( dp_y + 1)$ với $j$ là ước của $i$. Ta có thể duyệt qua các ước của $i$ trong $\sqrt i$.
- **Đáp án:** $\max(dp_i)$ với mọi giá trị $i$.

**Độ phức tạp thời gian:** $O( \sqrt{a_1} + \sqrt{a_2} + \dots + \sqrt{a_n} ) = O( \sum_{i=1}^n \sqrt{a_i} )$.

### **Mã nguồn mẫu**

:::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;

const int N = 1e5 + 5, M = 1e6 + 5;
int n, a[N], cnt, dp[M], mx[M];

bool checkSqr(int x) {
    int t = sqrt(x);
    return t * t == x;
}

int main(void) {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (a[i] % 10 == 0 || a[i] % 10 == 5)
            cout << a[i] << ' ';
        if ((a[i] - 1) % 4 == 0)
            cnt++;
    }

    cout << '\n' << cnt << '\n';
    for (int i = 1; i <= n; i++)
        if (checkSqr(a[i]))
            cout << a[i] << ' ';

    int ans = 0;
    for (int i = 1; i <= n; i++) {
        dp[a[i]] = 1;
        for (int j = 1; j * j <= a[i]; j++) {
            if (a[i] % j == 0) {
                dp[a[i]] = max(dp[a[i]], mx[j] + 1);
                dp[a[i]] = max(dp[a[i]], mx[a[i] / j] + 1);
            }
        }

        mx[a[i]] = max(mx[a[i]], dp[a[i]]);
        ans = max(ans, dp[a[i]]);
    }

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

:::

## Bài 4:

### Tóm tắt đề bài

Cho một dãy số nguyên $a$ gồm $N$ phần tử $a_1,a_2,...,a_N$.

**Yêu cầu:** Cho biết số lượng các đoạn con có tổng giá trị các phần tử trong đoạn bằng $0$.

**Dữ liệu đảm bảo:** $2 \le N \le 10^6$ và $|a_i| \le 10^6$.

### Lời giải

>[!Tip] Nhận xét
> Một đoạn $[l, r]$ có tổng bằng $0$, tức là:
> $$
> a_l + a_{l+1} + \dots + a_r = 0
> $$
> Giả sử ta có mảng cộng dồn $S_i = a_1 + a_2 + \dots + a_i$, biểu thức này tương đương:
> $$
> S_r - S_{l-1} = 0
> $$

Nếu ta cố định từng vị trí $r$ trên mảng, bài toán trở thành ==đếm số lượng số $l$== thỏa mãn:
- $l \lt r$
- $S_r - S_{l-1} = 0$ hay $S_{l-1} = S_r$

Sử dụng cấu trúc dữ liệu `map` để thực hiẹn việc này.

**Độ phức tạp thời gian:** $O(n \log n )$.

### **Mã nguồn mẫu**

:::success
:::spoiler Code

#include <bits/stdc++.h>

using namespace std;
const long long N = 1e6;

long long n , ans;
long long a[N+5] , pre[N+5];
map<long long, long long> mp;

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

    mp[0]++;
    for(ll i = 1; i <= n; i++){
        ans += mp[pre[i]];
        mp[pre[i]]++;
    }

    cout << ans;

    return 0;
}

:::