Đề TS10 - BRVT - 2024: 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 2024 - 2025.

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

Bài 1

Tóm tắt đề bài

Cho số nguyên dương

N

Yêu cầu: Hãy đếm số lượng các ước số dương của

N

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

10 \leq N \leq 10^{12}

Ràng buộc:

$50 %$ số điểm tương ứng với
$1 \leq N \leq 10^{6}$
$50 %$ số điểm không có ràng buộc gì thêm.

Subtask 1

Duyệt

i

từ

1

đến

n

và đếm các số

i

mà

n

chia hết cho

i

Tức là
$n mod i = 0$ .

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

O (n)

Code

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

long long n, kq;

int main() {
    cin >> n;

    for (long long i = 1; i <= n ;++i) {
        if (n % i == 0) {
            kq++;
        }
    }
    
    cout << kq;
    
    return 0;
}

Subtask 2

Nhận xét

Giả sử

n

có một ước là

x

y = \frac{n}{x}

cũng là một ước của

n

Quan sát thấy, luôn luôn có ít nhất một trong hai số nhỏ hơn hoặc bằng

\sqrt{n}

Do đó, ta duyệt

i

từ

1

đến

⌊ \sqrt{n} ⌋

, nếu tìm thấy số

i

mà

n mod i = 0

, ngoài đếm ước

i

, ta đếm thêm cả ước

\frac{n}{i}

của

n

Lưu ý: Trong trường hợp

i \times i = n

, số

i

có thể bị đếm

2

lần.

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

O (\sqrt{n})

Code

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

long long n, kq;

int main() {
    cin >> n;

    //i <= sqrt(n) tương đương i*i <= n
    for (long long i = 1; i*i <= n; ++i) {
        if (n % i == 0) {
            kq += 2;
            if (i*i == n) {
                kq--;
            }
        }
    }

    cout << kq;
    
    return 0;
}

Bài 2

Tóm tắt đề bài

Cho một số nguyên dương

N

có số lượng chữ số không vượt quá

10^{5}

Yêu cầu: Hoán vị các chữ số của

N

, sao cho sau khi hoán vị ta thu được một số nguyên dương lớn nhất là bội của số

30

Ràng buộc:

$50 %$ số điểm tương ứng với số lượng chữ số của
$N$ không vượt quá
$10$
$50 %$ số điểm không có ràng buộc gì thêm.

Về bội số của 30

Một số chia hết cho

30

khi và chỉ khỉ số đó thỏa mãn:

Số đó chia hết cho
$3$ , nghĩa là tổng các chữ số chia hết cho
$3$ .
Số đó chia hết cho
$10$ , nghĩa là có số
$0$ ở cuối.

Subtask 1

Ta thử tất cả các cách hoán vị các chữ số của

N

và tìm số lớn nhất thỏa mãn tất cả điều kiện ở trên.

Để dễ thao tác, ta sử dụng hàm next_permutation() có sẵn trong thư viện STL của C++.

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

O (n!)

Subtask 2

Ta sắp xếp lại các chữ số theo thứ tự giảm dần để số đạt giá trị lớn nhất.

Trùng hợp, khi đó số

0

(nếu có) của

N

cũng sẽ được dồn về cuối số, giúp ta thỏa mãn điều kiện thứ

2

Khi ta sắp xếp lại như vậy, tổng các chữ số không bị thay đổi, nên ta kiểm tra xem tổng này có chia hết cho

3

hay không.

Tip

Để dễ thao tác, ta nên sử dụng kiểu dữ liệu string để lưu số

N

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

O (n \log n)

với

n

là số lượng chữ số của

N

Code

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

int sumDig(string s) {
	int ret = 0;
	for (char x : s) {
		ret += (x - '0');
    }

	return ret;
}

int main() {
	string s;
	cin >> s;
	sort(all(s), greater<char>());

	if (s.back() != '0' || sumDig(s) % 3) cout << -1;
	else cout << s;

	return 0;
}

Bài 3

Tóm tắt đề bài

Cho dãy

A

gồm

N

số nguyên dương. Bằng cách ghi dãy

A

lặp lại vô hạn lần ta thu được dãy

B

Yêu cầu: Cho số nguyên dương

K, P

. Tính tổng

K

phần tử liên tiếp trong dãy

B

bắt đầu từ phần tử có chỉ số

P

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

$1 \leq N \leq 10^{5}$ ;
$1 \leq K, P \leq 10^{9}$ ;
$1 \leq A_{i} \leq 10^{3}$ .

Ràng buộc:

$50 %$ số điểm tương ứng với
$1 \leq K \leq 10^{4}, 1 \leq P \leq 10^{5}$
$50 %$ số điểm không có ràng buộc gì thêm.

Subtask 1

Thực hiện mô phỏng theo đề bài, ta duy trì một biến vị trí để di chuyển tăng dần, nếu vị trí lớn hơn

n

, ta cập nhật lại biến về

1

Mẹo

Sử dụng phép toán

mod

để cập nhật lại vị trí.

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

O (P)

Code

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

long long n, kq, l, r, a[1000009], k ,p;

int main() {
    cin >> n >> k >> p;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    
    a[0] = a[n];
    
    for (int i = p; i <= k + p - 1; ++i) {
        kq += a[i % n];
    }
    
    cout << kq;
    
    return 0;
}

Subtask 2

Nhận xét

Dãy

B

là dãy

A

lặp đi lặp lại vô tận.

Do đó, tổng của

K

phần tử liên tiếp mà đề bài yêu cầu ta tính cũng được tạo thành từ nhiều tổng của cả dãy

A

cộng lại và một ít số bị lẻ ra.

Ta chỉ cần duyệt để tính các số bị lẻ ra, còn nhóm tổng của

A

có thể tính nhanh.

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

O (n)

Code

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

const int N = 1e5;
long long n, k, p, sum, A[N+1];

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

	p %= n;
	if (!p) p = n;
    
    //Số lượng nhóm có tổng = A
	long long cycle = k / n;
    
    //Phần bị lẻ ra
	long long rem = k % n;

	long long res = cycle * sum;
	for (int i = p; i <= p + rem - 1; i++) {
		res += A[i % n];
	}

	cout << res;

	return 0;
}

Bài 4

Tóm tắt đề bài

Cho dãy

B

gồm các số nguyên

B_{1}, B_{2}, B_{3}, \dots, B_{N}

được gọi là dãy lõm nếu tồn tại chỉ số

i

(1 < i < N)

sao cho

B_{1} > B_{2} > \dots > B_{i} < B_{i + 1} < \dots < B_{N}

Yêu cầu: Cho trước dãy

A

gồm

N

số nguyên dương

A_{1}, A_{2}, \dots, A_{N}

. Hãy tìm dãy con lõm có độ dài lớn nhất.

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

2 < N \leq 10^{5}

và

1 \leq A_{i} \leq 10^{9}

Ràng buộc:

$20 %$ số điểm tương ứng với
$2 \leq N \leq 20$ .
$30 %$ số điểm tương ứng với
$20 < N \leq 5000$ .
$50 %$ số điểm không có ràng buộc gì thêm.

Subtask 1

Sinh tất cả dãy con của

A

, kiểm tra tính hợp lệ, và lấy độ dài dãy con dài nhất.

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

O (2^{n})

Subtask 2

Nhận xét

Một dãy con lõm là hợp bởi một dãy con giảm và một dãy con tăng (mỗi dãy gồm ít nhất hai phần tử).

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

Định nghĩa:
- $F_{i}$ là dãy con giảm dài nhất kết thúc tại
  $i$ .
- $G_{i}$ là dãy con tăng dài nhất bắt đầu tại
  $i$ .
Khởi gán:
$F_{i} = G_{i} = 1 \forall i$ (dãy con một phần tử).
Công thức:
- $F_{i} = max (F_{j} + 1)$ với
  $j < i$ và
  $A_{j} > A_{i}$ (thêm
  $A_{i}$ vào một dãy kết thúc ở
  $A_{j}$ ).
- $G_{i} = max (F_{j} + 1)$ với
  $j > i$ và
  $A_{j} > A_{i}$ (thêm
  $A_{i}$ vào một dãy kết thúc ở
  $A_{j}$ ).

Khi đó, ở mỗi vị trí

i

từ

1

đến

n

, nếu

F_{i} \geq 2

và

G_{i} \geq 2

thì có một dãy con lõm nhận

i

làm điểm thấp nhất (điểm lõm) có độ dài là:

F_{i} + G_{i} - 1

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

O (n^{2})

Code

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

long long n, a[1000009], F[1000009], G[1000009], kq;

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

    cout << kq;
    
    return 0;
}

Subtask 3

Tư tưởng kế thừa từ subtask trước, tuy nhiên cần cải tính việc tính

F

và

G

Bạn đọc tham khảo bài viết về giải thuật dãy con tăng dài nhất nâng cao sau đây.

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

O (n \log n)

Code

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

const int N = 1e5;
int n, A[N+1], F[N+1], G[N+1];
vector<int> V;

int findPos(int x) {
    int l = 0, r = V.size() - 1, ret = 0;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (V[mid] <= x) {
            ret = mid;
            r = mid - 1;
        } else
            l = mid + 1;
    }

    return ret;
}

void initLtoR() {
    V.clear();
    for (int i = 1; i <= n; i++) {
        if (V.empty() || V.back() > A[i]) {
            V.pb(A[i]);
            F[i] = V.size();
        } else {
            int pos = findPos(A[i]);
            V[pos] = A[i];
            F[i] = pos + 1;
        }
    }
}

void initRtoL() {
    V.clear();
    for (int i = n; i >= 1; i--) {
        if (V.empty() || V.back() > A[i]) {
            V.pb(A[i]);
            G[i] = V.size();
        } else {
            int pos = findPos(A[i]);
            V[pos] = A[i];
            G[i] = pos + 1;
        }
    }
}

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

    initLtoR();
    initRtoL();

    int res = 0;
    for (int i = 1; i <= n; i++) {
        if (F[i] >= 2 && G[i] >= 2) {
            res = max(res, F[i] + G[i] - 1);
        }
    }

    cout << res;

    return 0;
}

Đề TS10 - BRVT - 2024: Editorial

Bài 1

Tóm tắt đề bài

Subtask 1

Subtask 2

Bài 2

Tóm tắt đề bài

Về bội số của 30

Subtask 1

Subtask 2

Bài 3

Tóm tắt đề bài

Subtask 1

Subtask 2

Bài 4

Tóm tắt đề bài

Subtask 1

Subtask 2

Subtask 3

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