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

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 - 2018: 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
    • Tìm số nguyên tố bé nhất và lớn nhất trong phạm vi
    • 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}{4}+\frac{2}{5}+\cdots +\frac{2n-1}{2n+2}\\ B& =(1+\frac{1}{2})\times (1+\frac{1}{4})\cdots (1+\frac{1}{2^n})\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
  $2n-1$, mỗi lần cộng vào đáp án
  $\frac{i}{i+3}$.
• Độ thức tạp:
  $O(n)$

Tính biểu thức B

• Duyệt
  $i$ từ
  $1$ đến
  $n$, mỗi lần nhân vào đáp án
  $1+\frac{1}{2^i}$
• Độ thức tạp:
  $O(n)$

Note

Tuy

$2^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}{2^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ả.

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

Tóm tắt đề bài

Cho ba số nguyên dương

$n$,

$a$ và

$b$.

Yêu cầu:

• Tính biểu thức
  $A=\frac{n\times (n+1)\times (n+2)\times (2n-1)}{6}mod2018$.
• Tìm số nguyên tố bé nhất và số nguyên tố lớn nhất trong phạm vi từ
  $a$ đến
  $b$.

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

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

$2\le a<b\le {10}^9$.

Tính biểu thức A

Ta không thể tính trực tiếp biểu thức

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

$A$ với

$p=2018\times 6$ ta được

$$A=\frac{(nmodp)\times ((n+1)modp)modp\times ((n+2)modp)modp\times ((2n-1)modp)modp}{6}$$

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

$O(1)$.

Tìm số nguyên tố bé nhất và lớn nhất trong phạm vi

Duyệt qua mọi giá trị trong phạm vi

$a$ đến

$b$ và kiểm tra xem có số nguyên tố nào không.

• Với số nguyên tố bé nhất, ta duyệt từ bé đến lớn và lấy số nguyên tố đầu tiên ta gặp.
• Với số nguyên tố lớn nhất, ta duyệt từ lớn về bé và lấy số nguyên tố đầu tiên ta gặp.

Ta kiểm tra số nguyên tố bằng cách duyệt tới căn bậc hai số đó như sau

Vì sao thuật toán trên không chạy quá thời gian?

Trong các số từ

$1$ đến

${10}^9$, khoảng cách giữa hai số nguyên tố liên kề nhau không đáng kể, cụ thể là bé hơn

$282$.

Độ phức tạp thời gian: không quá

$O(282\times \sqrt{{10}^9})$.

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() {
    cin >> a >> b;
    
    for (int i = a; i <= b; i++) {
        bool check = true;
        if (i == 1) {
            check = false;
        }
        
        for (int j = 2; j * j <= i; j++) {
            if (i % j == 0) {
                check = false;
                break;
            }
        }
        
        if (check == true) {
            cout << i << " ";
            break;
        }
    }

    for (int i = b; i >= a; i--) {
        bool check = true;
        
        if (i == 1) {
            check = false;
        }
        
        for (int j = 2; j * j <= i; j++) {
            if (i % j == 0) {
                check = false;
                break;
            }
        }
        
        if (check == true) {
            cout << i;
            break;
        }
    }

    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:

• Liệt kê tất cả giá trị của phần tử trong dãy có chữ số tận cùng là
  $6$ hoặc
  $8$.
• Tính trung bình cộng tất cả phần tử trong dãy có giá trị dương lẻ.
• Tìm độ dài lớn nhất của đoạn con có các phần tử liên tiếp bằng nhau.
• Tìm độ dài của dãy con tăng có nhiều phần tử nhất đều dương.

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

$n\le {10}^4$ và

$|a_i|\le {10}^9$.

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

$mod10$. Nếu chữ số cuối cùng là

$6$ hoặc

$8$ thì in ra.

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

$O\left(n\right)$.

Yêu cầu 2

Duy trì một biến đếm và một biến tổng. Duyệt qua từng giá trị trong dãy, kiểm tra xem giá trị đó có vừa lẻ và dương hay không? Nếu thỏa mãn, tăng biến đếm và biến tổng lên.

Đáp án: Tổng chia cho số lượng (biến đếm).

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

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

$O\left(n\right)$.

Yêu cầu 3

Tip

Gọi

$t_i$ là độ dài lớn nhất của đoạn con liên tiếp kết thúc tại

$i$.

Duyệt qua từng phần tử

$a_i$ trong dãy:

• Nếu
  $a_i=a_{i-1}$ thì
  $t_i=t_{i-1}+1$ (đoạn con kết thúc tại
  $i-1$ có thể mở rộng ra
  $i$).
• Nếu
  $a_i\ne a_{i-1}$ thì
  $t_i=1$ (đoạn con một phần tử).

Đáp án:

$max(t_1,t_2,..t_n)$.

Lưu ý: Nếu kết quả bằng

$1$ ta in ra

$0$ vì đoạn con phải có ít nhất

$2$ phần tử.

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

$O(n)$.

Yêu cầu 4

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

• Định nghĩa:
  $d{p}_i$ là độ dài dãy con tăng dài nhất kết thúc tại
  $i$.
• Khởi gán:
  $d{p}_i=1$ với
  $i$ từ
  $1$ đến
  $n$ (dãy con một phần tử cũng là dãy con tăng).
• Công thức:
  $d{p}_i=max(d{p}_j+1)$ với
  $j<i$ và
  $A_j<i$.

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

$O(n^2)$

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>
#define ll long long
#define str string
#define ii pair <ll,ll>
#define fi first
#define se second

using namespace std;
const ll N = 1e6;

ll n , sum_q2 , cnt_q2 , cnt_q4 , ans_q4;
ll a[N+5] , f[N+5];
vector <ll> q1 , q4;

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

        if(a[i] > 0 && (a[i] % 10 == 6 || a[i] % 10 == 8)){
            q1.push_back(a[i]);
        }

        if(a[i] > 0 && a[i] % 2 == 1){
            sum_q2 += a[i];
            cnt_q2++;
        }

        if(a[i] % 2 == 0){
            q4.push_back(a[i]);
            cnt_q4++;
        }
    }

    /// Query 1
    for(ll i : q1){
        cout << i << " ";
    }
    cout << "\n";

    /// Query 2
    long double q2 = sum_q2*1.0 / cnt_q2*1.0;
    cout << fixed << setprecision(2) << q2 << "\n";

    /// Query 3
    bool check = 0;
    ll max_len = 1 , cur_len = 1;

    for(ll i = 2; i <= n; i++){
        if(a[i] == a[i-1]){
            cur_len++;
            check = 1;
        }
        else{
            max_len = max(max_len , cur_len);
            cur_len = 1;
        }
    }

    if(!check)  cout << "NO\n";
    else{
        cout << "YES " << max_len << "\n";
    }

    /// Query 4
    
    for(ll i = 0; i < cnt_q4; i++){
        f[i] = 1;
        for(ll j = 0; j < i; j++){
            if(q4[i] > q4[j]){
                f[i] = max(f[i] , f[j] + 1);
            }
        }
        ans_q4 = max(ans_q4 , f[i]);
    }

    cout << ans_q4;

    return 0;
}

Bài 4:

Tóm tắt đề bài

Cho một dãy

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

$a_i$.

Yêu cầu: Tìm số lượng tổng khác nhau có thể tạo thành từ một tập con của dãy

$a$.

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

$1\le n,a_i\le 100$.

Lời giải

Nhận xét

Vì

$n,a_i\le {10}^2$, tổng tối đa của một tập con của

$a$ là

$n\times a_i={10}^4$.

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

• Định nghĩa:
  $d{p}_{i,j}$ là khả năng tạo ra tổng bằng
  $i$ từ
  $i$ phần tử đầu tiên:
  • Nếu
    $d{p}_{i,j}=1$, có thể tạo được tổng
    $i$ từ
    $i$ phần tử đầu tiên.
  • Nếu
    $d{p}_{i,j}=0$, không thể tạo được tổng
    $i$ từ
    $i$ phần tử đầu tiên.
• Khởi gán:
  $d{p}_{i,0}=1$ với mọi
  $i$ (luôn có thể không chọn phần tử nào).
• Công thức:
  • $d{p}_{i,j}=1$ khi:
    • $d{p}_{i-1,j}=1$ (đã tạo được tổng
      $j$ từ trước).
    • Hoặc
      $d{p}_{i-1,j-A_i}=1$ (đã tạo được tổng
      $j-a_i$ từ trước, sau đó thêm phần tử
      $a_i$ để tạo được tổng
      $j$).
  • $d{p}_{i,j}=0$ nếu không thỏa bất kỳ điều kiện nào ở trên.

Đáp án: Các số

$x$ thỏa

$d{p}_{n,x}=1$ là các tổng có thể tạo được.

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

$O(n\times \sum _{i=1}^n{a}_i)$

$\sum _{i=1}^n{A}_i$ là tổng

$a_i$ với

$i$ từ

$1$ đến

$n$.

Mã nguồn mẫu

Code

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

const int N = 100;
int n, A[N+1], sum, dp[N+1][N+1];

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

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

    cout << ans;

    return 0;
}