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

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

Bài 1:

Tóm tắt đề bài

Nhập vào một số nguyên dương

n

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

\begin{aligned} A & = \frac{1}{6} + \frac{2}{7} + \dots + \frac{2 n - 1}{2 n + 4} \\ B & = \frac{1}{7} - \frac{2}{7^{2}} + \dots + \frac{2 n + 1}{7^{2 n + 1}} \end{aligned}

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

2 \leq n \leq 100

Tính biểu thức A

Duyệt
$i$ từ
$1$ đến
$2 n - 1$ , mỗi lần cộng vào đáp án
$\frac{i}{i + 5}$ .
Độ phức tạp thời gian:
$O (n)$ .

Tính biểu thức B

Duyệt
$i$ từ
$1$ đến
$2 n + 1$ , mỗi lần cộng vào đáp nếu
$i$ lẻ và trừ vào đáp án nếu
$i$ chẵn một lượng là
$\frac{i}{7^{i}}$
Việc tính riêng tử và mẫu của
$\frac{i}{7^{i}}$ là không khả thi do vấn đề về giới hạn lớn.
Ta biến đổi
$\frac{i}{7^{i}} = i \times \frac{1}{7^{i}}$ . Gọi biến
$p$ là giá trị
$\frac{1}{7^{i}}$ . Dễ dàng nhận thấy với mỗi lần chay ta chỉ cần gán lại giá trị cho
$p = \frac{p}{7}$ tương ứng với việc số mũ của
$7$ tăng lên
$1$ theo
$i$ .
Độ phức tạp thời gian:
$O (n)$ .

Note

Tuy

7^{i}

là rất lớn, và lưu trữ bằng kiểu số thức sẽ dẫn đến sai số nghiêm trọng, nhưng thực tế ta xét

\frac{1}{7^{i}}

, do đó sai số chỉ ở những hàng thập phân phía sau. Vì vậy không ảnh hưởng đến kết quả.

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 <= 2 * n - 1; i++) {
        A += (double)i/(i + 5);
    }

    double B = 0, p = 1;
    for (int i = 1; i <= 2 * n + 1; i++) {
        p = (double) p / 7;
        if (i % 2 == 1)
            B += ((double) i * p);
        else 
            B -= ((double) i * p);
    }
    
    cout << fixed << setprecision(5) << A << '\n' << B << '\n';

    return 0;
}

Bài 2:

Tóm tắt đề bài

Cho các số nguyên dương

a

b

c

k

x

y

Yêu cầu:

Tính biểu thức
$A = \frac{a \cdot b \cdot c}{k}$ .
Tính biểu thức
$B = ((x + 1) \cdot (x + 2) \dots (x + y)) m o d 2020$ .

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

1 \leq a, b, c, k \leq 10^{18}

1 \leq x \leq 10^{9}

và

1 \leq y \leq 10^{6}

Tính biểu thức A

Nếu tính thông thường thì biểu thức

A

sẽ tràn dữ liệu. Do đó cần xử lý số lớn để tính toán.

Ban đầu ta chuyển đổi giá trị

a

thành một mảng số nguyên

A_{i}

với

A_{i}

là giá trị tại vị trí

i

từ phải sang trái của số

a

Ví dụ:
$a = 123$ thì
$A_{1} = 3$ .

Sau đó ta tính thông thường, nhân từng phân tử

A_{i}

với

B

từ

i = 1, 2, 3, \dots, n

với

n

là độ dài hiện tại của mảng

A_{i}

. Sau đó ta nhận lần lượt

A_{i}

với

C

tương tư như nhân với

B

Cuối cùng, dời

A_{i}

lên

5

vị trí, tức là

A_{i + 5} = A_{i}

, để khi chia ta lưu được

6

số thập phân sau dấu phẩy trong

A_{i}

với

i \in [0, 5]

Nhận xét về độ dài số

Độ dài tối đa của mảng

A

bé hơn 100 vì độ dài giá trị của tích

10^{18} \times 10^{18} \times 10^{18}

là

57

sau đó ta thêm

5

chữ số hàng thập phân thì tối đa độ dài đạt

62

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

O (1)

Yêu cầu 2

Nếu chạy lần lượt

i

từ

1

đến

y

để tính

(x + i)

và nhân vào kết quả thì sẽ bị tràn dữ liệu.

Do đó, áp dụng tính chất chia lấy dư để xử lý tránh bị tràn số:

(a \times b) mod c = [(a mod c) \times (b mod c)] mod c

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

O (y)

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

Nguyễn Minh
#include <bits/stdc++.h>
using namespace std;

long long a, b, c, k, X, Y;
long long A[1000];
long long d[1000];

int main() {
    cin >> a >> b >> c >> k >> X >> Y;
    int B = 1;
    for (int i = 1; i <= Y; i++)
        B = B * ((X + i) % 2020) % 2020;

    int n = 0;
    while (a > 0)
    {
        int p = a % 10;
        a /= 10;
        n++;
        A[n] = p;
    }

    for (int i = 1; i <= 100; i++)
    {
        long long phu = A[i] * b + d[i]; // d[i] = tổng nhớ tại vị trí i.
        d[i] = 0;
        A[i] = phu % 10;
        phu /= 10;
        int j = i;
        while (phu > 0)
        {
            j++;
            int p = phu % 10;
            phu /= 10;
            d[j] += p;
        }
    }

    for (int i = 1; i <= 100; i++)
    {
        long long phu = A[i] * c + d[i];
        A[i] = phu % 10;
        phu /= 10;
        int j = i;
        while (phu > 0)
        {
            j++;
            int p = phu % 10;
            phu /= 10;
            d[j] += p;
        }
    }

    for (int i = 100; i >= 1; i--)
        if (A[i] != 0)
    {
        n = i; //Xác định độ dài hiện tại của mảng A[i]
        break;
    }

    for (int i = n + 5; i > 5; i--)
        {
            A[i] = A[i - 5]; // Dời giá trị lên 5 vị trí
            A[i - 5] = 0;
        }

    long long giatri = 0;
    for (int i = n + 5; i >= 0; i--)
    {
        giatri *= 10;
        giatri += A[i];
        A[i] = 0;
        if (giatri >= k)
        {
            A[i] = giatri / k;
            giatri = giatri % k;
        }
    }

    for (int i = n + 5; i >= 0; i--)
        if (A[i] != 0)
        {
            n = i; // xác định lại độ dài của mảng A[i]
            break;
        }

// Vì làm tròn đến số thập phân thứ 5 nên ta sẽ kiểm tra số thập phân thứ 6
    int q = 0;
    if (A[0] >= 5)
        q = 1;

    for (int i = 1; i <= n; i++)
        {
            A[i] += q;
            q = 0;
            if (A[i] == 10)
                {
                    A[i] = 0;
                    q = 1;
                }

            if (q == 0)
                break;
        }

    if (q == 1)
    {
        n++;
        A[n] = 1;
    }

    for (int i = n; i > 5; i--)
        cout << A[i];
    cout << ".";
    for (int i = 5; i >= 1; i--)
        cout << A[i];
    cout << "\n";

    cout << B;

    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 - 1}, a_{n}

Yêu cầu:

In ra các phần tử của dãy có dạng
$7 \times k$ (
$k$ là số nguyên).
Nếu tồn tại hai số nguyên âm nằm kề nhau in ra chữ số
$1$ , ngược lại in ra chữ số
$0$ .
Tìm độ dài lớn nhất của đoạn con liên tiếp có các phần tử là số nguyên tố (nếu không tồn tại dãy có ít nhất
$2$ phần tử in ra
$0$ ).
Tìm giá trị tuyệt đối nhỏ nhất của tổng hai phần tử bất kỳ.

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

n \leq 10^{5}

và

| a_{i} | \leq 10^{7}

Yêu cầu 1

Một số nguyên dương

x

có dạng

7 k

khi

x mod 7 = 0

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 (n)

Yêu cầu 2

Duyệt qua mọi cặp số kề nhau và kiểm tra xem hai số có thỏa mãn hay không.

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

O (n)

Yêu cầu 3

Sử dụng thuật toán sàng nguyên tố để đánh dấu những giá trị nào là số nguyên tố.

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

Định nghĩa:
$d p_{i}$ là độ dài đoạn con liên tiếp có nhiều phần tử nhất kết thúc ở vị trí
$i$ .
Công thức:
- Nếu
  $a_{i}$ là số nguyên tố,
  $d p_{i} = d p_{i - 1} + 1$ .
- Ngược lại,
  $d p_{i} = 0$ .
Kết quả:
$m a x (d p_{i})$ .

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

O (n \log \log n)

Độ phức tạp của sàng nguyên tố.

Yêu cầu 4

Nhận xét

Ta cần tìm tổng hai số trong dãy có giá trị gần bằng

0

nhất.

Sắp xếp lại mảng

a

theo thứ tự không giảm, sau đó áp dụng thuật toán hai con trỏ:

Con trỏ
$i$ bắt đầu từ
$1$ .
Con trỏ
$j$ bắt đầu từ
$n$ .
Tổng đang xét là tổng của
$a_{i}$ và
$a_{j}$ .

Nếu tăng

i

lên thì giá trị của tổng sẽ tăng lên, ngược lại, nếu giảm

j

xuống thì giá trị của tổng sẽ giảm xuống.

Chính vì tính chất đó, ta có thể di chuyển con trỏ tối ưu để tổng có thể gần bằng

0

nhất và giá trị tuyệt đối của tổng là bé nhất.

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

O (n \log n)

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 n;
long long a[1000005], dp[100005];
int vis[10000005];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
   
    for (int i = 1; i <= n; i++)
        if (a[i] % 7 == 0)
            cout << a[i] << " ";
    
    cout << "\n";

    bool kt = false;
    for (int i = 2; i <= n; i++)
        if (a[i] < 0 && a[i - 1] < 0)
        {
            kt = true;
            break;
        }
    
    if (kt == true) cout << 1;
    else cout << 0;
    cout << "\n";

    for (int i = 1; i <= n; i++)
        t[i] = 0;

    for (int i = 2; i * i <= 1e7; i++)
        if (vis[i] == 0)
            for (int j = i; j * i <= 1e7; j++)
                vis[j * i] = 1;
    vis[1] = 1;
    vis[0] = 1;

    long long ans = 0;
    for (int i = 1; i <= n; i++)
        if (vis[abs(a[i])] == 0 && a[i] > 0)
            {
                dp[i] = dp[i - 1] + 1;
                ans = max(ans, dp[i]);
            }
    if (ans <= 1)cout << 0;
    else cout << ans;
    cout << "\n";

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

    ans = 1e18;
    int j = n;
    for (int i = 1; i <= n; i++)
    {
        if (i > 1)
            ans = min(ans, abs(a[i] + a[i - 1]));
        if (j > 0)
            ans = min(ans, abs(a[i] + a[j]));
        while (abs(a[j]) > abs(a[i]) && j > i)
        {
            ans = min(ans, abs(a[i] + a[j]));
            j--;
        }
        if (j > 0)
            ans = min(ans, abs(a[i] + a[j]));
    }
    cout << ans;
    return 0;
}

Bài 4:

Tóm tắt đề bài

Cho một dãy

n

số nguyên dương

a_{i}

và một dãy

m

số nguyên dương

b_{i}

Yêu cầu: Tìm số lượng phần tử trong mảng

b_{i}

có giá trị bằng tổng của ít nhất

1

dãy con trong mảng

a_{i}

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

1 \leq n, a_{i} \leq 100

và

1 \leq m, b_{i} \leq 10^{4}

Lời giải

Nhận xét

Bài toán yêu cầu kiểm tra có thể tạo được tổng

b_{i}

bằng một tập con của

a

không.

Áp dụng thuật toán quy hoạch động cái túi

Định nghĩa:
$d p_{i, j}$ đánh dấu tổng
$j$ có thể tạo được với
$i$ số đầu tiên không:
- $d p_{i, j} = 1$ nghĩa là tạo được tổng có giá trị bằng
  $j$ .
- $d p_{i, j} = 0$ là không tạo được.
Khởi gián:
$d p_{0, 0} = 1$ .
Công thức:
$d p_{i, j} = 1$ khi
$d p_{i - 1, j - a_{i}} = 1$ hoặc
$d p_{i - 1, j} = 1$ .

Duyệt qua

b_{i}

, nếu

d p_{n, b_{i}} = 1

nghĩa là giá trị

s_{b}

thỏa yêu cầu đề bài, ta tăng đáp án.

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

O (n \times max (b_{i}))

Mã nguồn mẫu

Code

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

const int N = 100, M = 1e4;
int dp[N+1][M+1], n, a[N+1];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    
    dp[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= 10000; j++) {
            dp[i][j] = dp[i-1][j];
            if (j >= a[i] && dp[i - 1][j - a[i]] == 1) {
                dp[i][j] = 1;
            }
        }
    }

    long long ans = 0;
    for (int i = 1; i <= m; i++) {
        if (dp[n][b[i]] == 1) {
            ans++;
        }
    }
    
    cout << ans;
    return 0;
}

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

Tính biểu thức A

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

Read more

Ôn tập TS10 & THTB 2025 - Đề 5: Editorial

Ôn tập TS10 & THTB 2025 - Đề 2: Editorial

Ôn tập TS10 & THTB 2025 - Đề 4: Editorial

Ôn tập TS10 & THTB 2025 - Đề 3: Editorial