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

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 - 2017: Editorial
  • Bài 1
    • Tóm tắt đề bài
    • Tính A
    • Tính 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

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

$N$.

Yêu cầu: Tính kết quả các biểu thức sau:

• $A=\frac{1}{2}+\frac{2}{2^2}+\frac{3}{2^3}+\cdots +\frac{N}{2^N}$
• $B=\frac{1\times 2}{3\times 4}+\frac{3\times 4}{5\times 6}+\frac{5\times 6}{7\times 8}+\cdots +\frac{(2N-3)(2N-2)}{(2N-1)2N}$

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

$2\le N\le 100$.

Tính A

Cho biến

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

$1$ đến

$n$, cộng

$\frac{i}{2^i}$ vào kết quả.

Lưu ý

Để tránh số quá lớn, ta nên lấy

$i$ và chia liên tục cho

$2$ thay vì tính

$2^i$

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

$O\left(n\right)$.

Tính B

Cho biến

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

$2$ đến

$n$, cộng

$\frac{(2i-3)\times (2i-2)}{2i}$ vào kết quả.

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

	cin >> n;
	for (int i = 1; i <= n; i++) {
		double ret = i;
		for (int j = 1; j <= i; j++) {
			ret /= 2;
        }

		A += ret;

		if (i >= 2) {
            B += (double)(2*i - 3)*(2*i - 2) / (2*i - 1) / (2*i);
        }
	}

	cout << fixed << setprecision(3) << A << "\n" << B;

	return 0;
}

Bài 2:

Tóm tắt đề bài

Nhập vào

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

$a,b$ và

$N$.

Yêu cầu:

• Tìm các số nguyên tố nằm trong đoạn
  $[a,b]$.
• Tìm chữ số chẵn lớn nhất của
  $N$.

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

$2\le a<b\le 2\times {10}^5$ và

$1\le N\le {10}^{18}$

Yêu cầu 1

Duyệt qua các số từ

$a$ đến

$b$, kiểm tra tính nguyên tố của mỗi số bằng cách duyệt đến căn bậc hai của số đó để tìm ước.

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

$O(\sqrt{a}+\sqrt{a+1}+\cdots +\sqrt{b})=O\left(\sum _{i=a}^b\sqrt{i}\right)$.

Yêu cầu 2

Duyệt qua các chữ số của

$n$ để tìm chữ số chẵn lớn nhất. Có thể thực hiện bằng cách không ngừng lấy chữ số tận cùng của

$n$ là

$nmod10$, sau đó ta chia

$n$ cho

$10$ để xóa chữ số đó đi và tìm chữ số tiếp theo.

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

$O({\log }_{10}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;

bool isPrime(int x) {
	if (x < 2) {
        return 0;
    }
    
	for (int i = 2; i * i <= x; i++) {
		if (x % i == 0) {
			return 0;
        }
    }

	return 1;
}

int main() {
	int a, b;
    long long n;
	cin >> a >> b >> n;

	for (int i = a; i <= b; i++) {
		if (isPrime(i)) {
			cout << i << " ";
        }
    }

	int res = -1;
	do {
        if ((n % 10) % 2 == 0) {
            res = max(res, n % 10);
        }
    } while (n /= 10);

	cout << "\n" << res;

	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$ và số nguyên

$X$.

Yêu cầu:

• Liệt kê các phần tử dương có dạng
  $5\times k$ (với
  $k$ là số nguyên bất kỳ) theo thứ tự ban đầu của dãy.
• Tìm tích lớn nhất của hai phần tử bất kỳ trong dãy (không trùng nhau).
• Sắp xếp dãy tăng dần và thực hiện chèn thêm một phần tử có giá trị
  $X$ vào dãy sao cho vẫn giữ nguyên tính chất tăng dần của dãy số.

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

• $2\le N\le {10}^5$.
• $|a_i|\le {10}^6$.
• $|X|\le 2\times {10}^6$

Yêu cầu 1

Nhận xét

$$A_i=5k\iff 5k=A_i\iff k=\frac{A_i}{5}$$
Mà

$k$ nguyên, do đó

$A_i$ chia hết cho

$5$, hay

$A_{i}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

Nhận xét

Dễ nhận thấy, hai số lớn nhất của dãy sẽ tạo ra tích lớn nhất.

Lưu ý: Hai số bé nhất (cùng âm), khi nhân vào sẽ tạo ra tích dương, và có thể lớn hơn tích của hai số lớn nhất.

Sắp xếp dãy tăng dần, ta có:

• Hai số lớn nhất là
  $A_N$ và
  $A_{N-1}$.
• Hai số nhỏ nhất là
  $A_1$ và
  $A_2$.

Đáp án:

$max(A_N\times A_{N-1},A_1\times A_2)$.

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

$O(n\log n)$ do thao tác sắp xếp mảng.

Yêu cầu 3

Để giữ nguyên tính chất tăng dần của dãy, ta cần chèn

$x$ vào giữa hai vị trí

$i$ và

$i+1$ sao cho

$A_i\le x\le A_{i+1}$.

Độ 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ố. Để dễ thao tác, ta không thực sự chèn số vào, mà ta sẽ duyệt qua dãy và in ra các số, nếu đúng vị trí của

$x$ ta sẽ in ra

$x$.

Lưu ý

Trường hợp

$x$ lớn hơn tất cả các số trong dãy, ta phải thêm

$x$ vào cuối.

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

$O(n)$ vì dãy đã được sắp xếp sẵn ở yêu cầu trướ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;

const int N = 1e5;
int n, X, A[N+1];

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

	cin >> X;

	for (int i = 1; i <= n; i++) {
		if (A[i] > 0 && A[i] % 5 == 0) {
			cout << A[i] << " ";
        }
    }

	sort(A+1, A+1+n);
	cout << "\n" << max(1LL * A[1] * A[2], 1LL * A[n-1] * A[n]) << "\n";

	bool used = 0;
	for (int i = 1; i <= n; i++) {
		if (X <= A[i] && !used) {
			used = 1;
			cout << X << " ";
		}

		cout << A[i] << " ";
	}

	if (!used) {
        cout << X << " ";
    }

	return 0;
}

Bài 4:

Tóm tắt đề bài

Có

$N$ cây xanh xếp thành một hàng thẳng, lần lượt cách cổng trường THPT chuyên Lê Quý Đôn

$a_1,a_2,\dots ,a_N$. Bóng của chúng cũng thẳng hàng và bóng của cây thứ

$i$ có chiều dài là

$d_i$.

Yêu cầu: Tính tổng chiều dài của các bóng cây phủ trên đường.

Lưu ý: Nếu có vùng bị phủ bóng bởi nhiều hơn một cây, chỉ xem vùng đó là một.

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

$1\le N\le {10}^5$,

$0<a_i\le {10}^6$ và

$0<d_i\le {10}^3$.

Lời giải

Mô hình hóa bài toán

Dễ thấy, cây thứ

$i$ cho ta vùng bóng

$[a_i,a_i+d_i-1]$.
Với mỗi vùng tương ứng của từng cây, ta cộng tất cả phần tử trong khoảng lên

$1$.

Để cộng nhanh từng đoạn, ta áp dụng mảng hiệu.

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

$O(n)$.

Mã nguồn mẫu

Code

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

const int N = 5e6;
int n, F[N+1];

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int x, y;
		cin >> x >> y;
		for (int j = x; j <= x+y-1; j++)
		    F[j]++;
	}

	int res = 0;
	for (int i = 1; i <= N; i++)
		if (F[i]) res++;

	cout << res;

	return 0;
}