Đề TS10 - BRVT - 2019: 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 2019 - 2020.

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 - 2019: Editorial
  • Bài 1:
    • Tóm tắt đề bài
    • Tính biểu thức A
    • Tính biểu thức B
    • Mã nguồn mẫu
  • Bài 2:
    • Tóm tắt đề bài
    • Yêu cầu 1
    • Yêu cầu 2
    • Mã nguồn mẫu
  • Bài 3:
    • Tóm tắt đề bài
    • Yêu cầu 1
    • Yêu cầu 2
    • Yêu cầu 3
    • Yêu cầu 4
    • Mã nguồn mẫu
  • Bài 4:
    • Tóm tắt đề bài
    • Lời giải
    • Mã nguồn mẫu

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{array}{rl}A& =\frac{1}{3}+\frac{2}{4}+\cdots +\frac{n-1}{n+1}\\ B& =\frac{1}{4\times 6}+\frac{1}{6\times 8}+\frac{1}{2n\times (2n+2)}\end{array}$$

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

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

Mã nguồn mẫu

Độ 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;
    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}mod2019$$

Dữ liệu đảm bảo:

$2\le n\le {10}^6$.

Yêu cầu 1

Nhận xét

Những số

$n$ với

$nmod4$ bằng nhau có cùng chữ số tận cùng.

Chứng minh

Xuất phát từ

$3^0=1$.

$3^1=1\times 3=3\to 3mod10=3$

$3^2=3\times 3=9\to 9mod10=9$

$3^3=3\times 9=27\to 27mod10=7$

$3^4=3\times 27=81\to 81mod10=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à

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

• $nmod4=0\iff 3^{n}mod10=1$
• $nmod4=1\iff 3^{n}mod10=3$
• $nmod4=2\iff 3^{n}mod10=9$
• $nmod4=3\iff 3^{n}mod10=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

$mod$ vì sẽ tràn dữ liệu.

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}modc=\frac{amodp}{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)modp}{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

Độ 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

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\le {10}^5$ và

$1\le a_i\le {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

$xmod4=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

Kiểm tra số chính phương

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:

$${\lfloor \sqrt{x}\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:
  $d{p}_x$ là độ dài dãy con dài nhất kết thúc tại giá trị
  $x$.
• Khởi gán:
  $d{p}_x=1\mathrm{\forall }x$ (dãy con một phần tử cũng thỏa đề bài).
• Công thức:
  $d{p}_x=max(d{p}_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(d{p}_i)$ với mọi giá trị
  $i$.

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

$O(\sqrt{a_1}+\sqrt{a_2}+\cdots +\sqrt{a_n})=O(\sum _{i=1}^n\sqrt{a_i})$.

Mã nguồn mẫu

Độ 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;

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

Nhận xét

Một đoạn

$[l,r]$ có tổng bằng

$0$, tức là:

$$a_l+a_{l+1}+\cdots +a_r=0$$
Giả sử ta có mảng cộng dồn

$S_i=a_1+a_2+\cdots +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<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

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