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

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 - 2021: Editorial
  • Bài 1:
    • Tóm tắt đề bài
    • Tính S
    • Tính T
    • 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 số nguyên dương

$n$. Yêu cầu tính:

$$\begin{array}{rl}S& =\frac{2}{3}+\frac{3}{4}+\cdots +\frac{n-1}{n}\\ T& =\frac{1}{3}-\frac{1}{3^2}+\frac{1}{3^3}-\cdots +\frac{1}{3^{2n-1}}-\frac{1}{3^{2n}}\end{array}$$

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

$3\le n\le 100$.

Tính S

Cho biến

$i$ chạy vòng lặp từ

$3$ đến

$n-1$, cộng

$\frac{i-1}{i}$ vào kết quả.

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

$O\left(n\right)$.

Tính T

Nhận xét:

$$\frac{1}{3^i}=\frac{1}{3^{i-1}}\cdot \frac{1}{3}$$

Với mỗi số hạng từ

$1$ đến

$2n$, duy trì một biến

$cur=\frac{1}{3^i}$ là giá trị của số hạng đang xét, nếu

$i$ lẻ, cộng

$cur$ vào đáp án, ngược lại trừ đáp án đi

$cur$.

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

$O\left(n\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

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

int main(){
    int n;
    cin >> n;
    
    double S = 0.0, T = 0.0;
    
    for (int i = 3; i <= n; i++) {
        S += 1.0 * (i-1) / i;
    }

    double cur = 1.0 / 3;
    for (int i = 1; i <= 2*n; i++) {
        if (i % 2 == 1 {
            T += cur;
        }
        else {
            T -= cur;
        }
        cur /= 3;
    }

    cout << fixed << setprecision(5) << S << '\n' << T;

    return 0;
}

Bài 2:

Tóm tắt đề bài

Cho số nguyên dương

$n$ và

$a$, thực hiện các yêu cầu:

• Tìm số nguyên
  $k$ là số
  $n$ sau khi đã xóa đi tất cả các số
  $0$.
• Tìm chữ số tận cùng của
  $a^n$.

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

$2\le n\le {10}^{18}$ và

$1\le a\le 100$.

Yêu cầu 1

Dùng cấu trúc dữ liệu vector, lần lượt tách và đưa từng chữ số sau cùng của

$n$ (tức là

$nmod10$) vào vector (ngoại trừ các chữ số

$0$). Sau đó, loại bỏ chữ số đó đi bằng cách chia

$n$ cho

$10$.

Yêu cầu 2

Nhận xét

Đáp an của bài toán là

$a^{n}mod10$.

Để tính

$a^{n}mod10$ một cách nhanh chóng, dùng lũy thừa nhị phân kết hợp với modulo trong lúc tính.

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

$O(\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;

long long n;
int a;

int Pow(int a, long long n) {
    if (n == 0) {
        return 1;
    }
    
    int tmp = Pow(a, n/2);
    tmp = tmp * tmp;
    if (n % 2 == 1) {
        tmp = tmp * a;
    }
    
    return tmp % 10;
}

int main(){
    cin >> n >> a;

    //Yêu cầu 1
    long long tmp = n;
    vector<int> digits;
    
    while (tmp > 0) {
        if (tmp % 10 != 0) {
            digits.push_back(tmp % 10);
        }
        tmp /= 10;
    }
    
    for (int i = digits.size()-1; i >= 0; i--) {
        cout << digits[i];
    }
    
    cout << '\n';

    //Yêu cầu 2
    cout << Pow(a, n);

    return 0;
}

Bài 3:

Tóm tắt đề bài

Cho hai số nguyên dương

$n$,

$k$ và dãy số nguyên nguyên dương

$A_1,A_2,A_3,\dots ,A_n$. Thực hiện các yêu cầu:

• In ra các số
  $A_i$ có dạng
  $A_i=5\cdot h+2(h\in N)$.
• In ra số lượng số nguyên tố trong dãy.
• In ra khoảng cách lớn nhất giữa hai số chính phương (số lượng phần tử nhiều nhất nằm giữa hai số chính phương) trong dãy. In ra
  $-1$ nếu không tồn tại hai số chính phương.
• Chia dãy số thành hai phần sao cho: Phần thứ nhất có
  $k$ phần tử, phần thứ hai có
  $n-k$ phần tử. In ra độ chênh lệch lớn nhất giữa tổng của hai phần.

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

$2\le k\le n\le {10}^5$ và

$1\le A_i\le {10}^7$.

Yêu cầu 1

Nhận xét

$$\begin{array}{rl}{A}_i& =5h+2\\ \iff 5h& =A_i-2\\ \iff h& =\frac{A_i-2}{5}\end{array}$$
Mà

$h$ nguyên, do đó

$A_i-2$ chia hết cho

$5$, hay

$(A_i-2)mod5=0$.

Như vậy, ta duyệt qua dãy và in ra các số 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 2

Vì

$A_i\le {10}^7$, có thể dùng kĩ thuật sàng nguyên tố, sau đó với mỗi số

$A_i$ kiểm tra nhanh xem nó có phải số nguyên tố hay không và đếm.

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

$O(n\log \log n)$.

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

Để khoảng cách giữa hai số chính phương được chọn là xa nhất, ta chọn số chính phương đầu tiên và cuối cùng của dãy.

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

$O(n)$.

Yêu cầu 4

Nhận xét:

Chênh lệch giữa hai phần là lớn nhất khi một phần đạt tổng lớn nhất có thể và phần còn lại phải nhỏ nhất có thể.

Dễ dàng nhận thấy:

• Nếu
  $k\ge n-k$, ta nhóm
  $k$ phần tử lớn nhất chung với nhau và
  $n-k$ phần tử nhỏ nhất chung với nhau
• Nếu
  $k<n-k$, ta nhóm
  $n-k$ phần tử lớn nhất chung với nhau và
  $k$ phần tử nhỏ nhất chung với nhau

Có thể tìm nhanh tập các phần tử lớn nhất hoặc nhỏ nhát bằng cách sắp xếp lại dãy số.

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

const int N = 1e5 + 5;
const int A = 1e7 + 5;
int n, a[N], k, isPrime[A];

bool isSquare(int n) {
    int tmp = sqrt(n);
    
    if (tmp * tmp == n) {
        return 1;
    }
    
    return 0;
}

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

    /// Yêu cầu 1
        for (int i = 1; i <= n; i++) {
            if ((a[i]-2) % 5 == 0) cout << a[i] << ' ';
        }
    
        cout << '\n';

    /// Yêu cầu 2
        isPrime[1] = 1;
        for (int i = 2; i*i <= 1e7; i++) {
            if (isPrime[i] == 0) {
                for (int j = i*i; j <= 1e7; j += i) {
                    isPrime[j] = 1;
                }
            }
        }

        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            if (isPrime[a[i]] == 0) {
                cnt++;
            }
        }
    
        cout << cnt << '\n';

    /// Yêu cầu 3
        int L = -1, R = -1;
        for (int i = 1; i <= n; i++) {
            if (isSquare(a[i])) {
                if (L == -1) L = i;
                R = i;
            }
        }
    
        if (L == R) {
            cout << -1 << '\n';
        }
        else {
            cout << R - L - 1 << '\n';
        }

    /// Yêu cầu 4
        sort (a+1, a+1+n);
        k = min(k, n-k);
    
        long long S_max = 0, S_min = 0;
        for (int i = 1; i <= n; i++) {
            if (i > k) {
                S_max += a[i];
            }
            else {
                S_min += a[i];
            }
        }
    
        cout << S_max - S_min;

    return 0;
}

Bài 4:

Tóm tắt đề bài

Cho số nguyên

$n$ và dãy số nguyên

$A_1,A_2,A_3,\dots ,A_n$.

Yêu cầu: Chia dãy

$A$ thành hai phần sao cho tổng của mỗi phần đều là số nguyên tố và chênh lệch giữa hai phần là nhỏ nhất. In ra

$-1$ nếu không có cách chia.

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

$2\le n\le 100$ và

$1\le A_i\le {10}^4$.

Lời giải

Áp dụng quy hoạch động cái túi.

Định nghĩa:

$F_i$ là khả năng tạo ra tổng bằng

$i$ từ các phần tử trong dãy:

• $F_i=1$, có thể tạo được tổng
  $i$.
• $F_i=0$, không thể tạo được tổng
  $i$.

Khởi gán:

$F_0=1$ (không sử dụng phần tử nào).

Công thức: Xét mọi phần tử

$A_i$ và mọi tổng

$j$ bất kỳ. Nếu

$j-A_i\ge 0$ và

$F_{j-A_i}=1$ thì

$F_j=1$.

Lưu ý

Ta tính

$F_j$ dựa vào

$F_{j-A_i}$ và

$j-A_i<j$ nên cần duyệt

$j$ giảm dần, để khi lấy

$F_{j-A_i}$ ta đảm bảo đó là đáp án chưa được cập nhật bởi

$A_i$.

Nhận xét

Gọi tổng của cả dãy số là

$sum$.

Chênh lệch giữa hai phần là nhỏ nhất khi tổng của hai phần gần với

$\frac{sum}{2}$ nhất.

Trong hai phần, sẽ luôn có một phần với tổng

$D\le \frac{sum}{2}$ và phần còn lại là

$sum-D$ lớn hơn hoặc bằng

$\frac{sum}{2}$.

Không mất tính tổng quát, ta chỉ cần tính

$D\le \frac{sum}{2}$. Đáp án tối ưu khi D lớn nhất.

Đáp án hợp lệ khi

$D$ và

$sum-D$ là số nguyên tố, ta có thể kiểm tra điều này bằng kĩ thuật sàng nguyên tố.

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

$O(n\cdot \sum _{i=1}^n{A}_i+n\log \log n)$

$n\cdot \sum _{i=1}^n{A}_i$: Quy hoạch động.

$n\log \log n$: Sàng nguyên tố.

Mã nguồn mẫu

Code

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

const int N = 102 + 5;
const int S = 1e6 + 5;
int n, isPrime[S], a[N], f[S], sum;

int main(){
    isPrime[1] = 1;
    for (int i = 2; i*i <= 1e6; i++) {
        if (isPrime[i] == 0) {
            for (int j = i*i; j <= 1e6; j += i) {
                isPrime[j] = 1;
            }
        }
    }

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sum += a[i];
    }

    f[0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1e6; j >= a[i]; j--) {
            f[j] = max(f[j], f[j - a[i]]);
        }
    }

    int res = -1;
    for (int i = 1; i <= sum/2; i++) {
        if (isPrime[i] == 0 && f[i] == 1 && isPrime[sum-i] == 0 && f[sum-i] == 1) {
            res = i;
        }
    }

    if (res == -1) {
        cout << -1;
    }
    else {
        cout << res << ' ' << sum - res << ' ' << sum - 2*res;
    }
    
    return 0;
}