Đề TS10 - BRVT - 2016: 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 2016 - 2017.

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 - 2016: Editorial
  • Bài 1:
    • Tóm tắt đề bài
    • Kiểm tra tính chẵn lẻ
    • Tính biểu thức A
    • Tính biểu thức B
  • Bài 2
    • Tóm tắt đề bài
    • Tối giản phân số
    • Đếm số lượng số chia hết cho 3 trong đoạn
  • Bài 3:
    • Tóm tắt đề bài
    • Liệt kê các phần tử có dạng 3k+2
    • Tìm số có giá trị lớn nhất của dãy.
    • Tìm số có giá trị nhỏ nhất của dãy.
  • Bài 4
    • Tóm tắt đề bài
    • Lời giải

Bài 1:

Tóm tắt đề bài

Cho số nguyên dương

$n$.

Yêu cầu:

• Cho biết
  $n$ có phải số chẵn không
• Tính các biểu thức sau:
  
  $$\begin{array}{rl}& A=\prod _{i=3}^n\frac{1}{i\cdot (i-1)}\\ & B=\sum _{i=1}^n\frac{2\cdot i-1}{2\cdot i+1}\end{array}$$

Kiểm tra tính chẵn lẻ

Nếu

$n$ chia hết cho

$2$ thì

$n$ chẵn, ngược lại

$n$ lẻ. Sử dụng phép toán

$mod$ để kiểm tra.

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

$O\left(1\right)$

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\cdot (i-1)}$ 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=0$. Duyệt qua mọi

$i\in [1,n]$ và cộng

$\frac{2\cdot i-1}{2\cdot i+1}$ vào

$B$.

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

$O\left(n\right)$

Lưu ý: Vì bài toán liên quan đến 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.

Độ 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;
double A, B;

int main() {
    cin >> n;
    for (int i = 3; i <= n; i++) {
        A += (double)1/((i-1)*i);
    }
    for (int i = 1; i <= n; i++) {
        B += (double)(2*i-1)/(2*i+1);
    }
    cout << (n & 1 ? "NO" : "YES") << '\n' << fixed << setprecision(2) << A << '\n' << B;
    return 0;
}

Bài 2

Tóm tắt đề bài

Cho

$2$ số nguyên dương

$a$ và

$b$.

Yêu cầu:

• Tối giản phân số
  $\frac{a}{b}$.
• Đếm số lượng số chia hết cho
  $3$ trong đoạn
  $[a,b]$.

Tối giản phân số

Để tối giản

$\frac{a}{b}$, ta chia

$a$ và

$b$ cho

$\mathrm{UCLN}(a,b)$.

C++ cung cấp sẵn hàm gcd() để tìm UCLN của hai số.

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

$O(\log min(a,b))$

Độ phức tạp của hàm gcd() trong C++ STL.

Đếm số lượng số chia hết cho 3 trong đoạn

Tip

Số lượng số chia hết cho

$x$ từ

$1$ đến

$n$ là:

$\lfloor \frac{n}{x}\rfloor$

Gọi

$f(x)$ là số lượng số chia hết cho

$3$ trong đoạn

$[1,x]$. Khi này,

$f(x)=\lfloor \frac{x}{3}\rfloor$.

Đáp án: %f(b) - f(a-1)$.

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

$O\left(1\right)$

Độ 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 a, b;
    cin >> a >> b;  
    
    int gcd = __gcd(a,b);
    cout << a / gcd << '/' << b / gcd << '\n' << b / 3 - (a - 1) / 3;
    
    return 0;
}

Bài 3:

Tóm tắt đề bài

Cho dãy số nguyên dương gồm

$n$ phần tử

$a_1,a_2,\dots ,a_n$.

• Liệt kê các phần tử có dạng
  $3k+2$.
• Tìm số có giá trị lớn nhất của dãy.
• Tìm số có giá trị nhỏ nhất của dãy.

Liệt kê các phần tử có dạng

$3k+2$

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

$x$ có dạng

$3k+2$ khi

$x\equiv 2(\mathrm{mod}3)$ hay

$x-2\equiv 0(\mathrm{mod}3)$.

Nghĩa là

$xmod3=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\left(n\right)$

Tìm số có giá trị lớn nhất của dãy.

Gọi

$f_{max}$ là giá trị lớn nhất của dãy.

• Khởi gán
  $f_{max}=-\mathrm{\infty }$.
• Duyệt qua mọi
  $i\in [1,n]$, nếu
  $f_{max}<a_i$ thì gán
  $f_{max}=a_i$.

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

$O\left(n\right)$

Tìm số có giá trị nhỏ nhất của dãy.

Gọi

$f_{min}$ là giá trị lớn nhất của dãy.

• Khởi gán
  $f_{min}=\mathrm{\infty }$.
• Duyệt qua mọi
  $i\in [1,n]$, nếu
  $f_{min}>a_i$ thì gán
  $f_{min}=a_i$.

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

$O\left(n\right)$

Độ 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;
    vector<int> a(n);
    for (auto& x : a) {
        cin >> x;
    }

    for (auto& x : a) {
        if ((x - 2) % 3 == 0) {
            cout << x << ' ';
        }
    }

    cout << '\n' << *max_element(a.begin(),a.end()) << '\n' << *min_element(a.begin(),a.end());
    
    return 0;
}

Bài 4

Tóm tắt đề bài

Cho dãy nguyên dương gồm

$n$ phần tử

$a_1,a_2,\dots ,a_n$.

Gọi

$S_1$ là tổng các đồ vật từ

$1$ đến

$k$ và

$S_2$ là tổng các đồ vật từ

$k+1$ đến

$n$

$(1\le k<n)$.

Yêu cầu: Tìm cách chia sao cho

$S_1\cdot S_2$ lớn nhất.

Lời giải

Áp dụng prefix sum (mảng cộng dồn) cơ bản.

Gọi

$f_i=\sum _{j=1}^i{a}_j$ (tổng

$i$ số đầu tiên của mảng).

Khi này, ta có:

• Tổng của các phần tử trong đoạn
  $[1,k]$ là
  $S_1=f_k$.
• Tổng các phần tử trong đoạn
  $[k+1,n]$ là
  $S_2=f_n-f_k$.

Duyệt qua mọi

$i\in [1,n)$ và tìm vị trí

$i$ để

$f_i\cdot (f_n-f_i)$ lớn nhất.

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

$O\left(n\right)$

Code

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

int main() {
    int n;
    cin >> n;
    vector<long long> f(n+5,0);
    for (int i = 1; i <= n; i++) {
        int a;
        cin >> a;
        f[i] = f[i-1] + a;
    }
    
    long long ans = 0;
    array<int,2> f;
    
    for (int i = 1; i < n; i++) {
        long long v = f[i] * (f[n] - f[i]);
        if (ans < v) {
            ans = v;
            f = {f[i], f[n] - f[i]};
        }
    }
    
    cout << f[0] << ' ' << f[1];
    
    return 0;
}