Marisa có $n$ tấm gỗ và sẽ sửa lại chúng để sử dụng, tấm gỗ thứ $i$ sẽ có độ đẹp là $A_i$ hoặc $B_i$ (tuỳ vào mục đích sử dụng mà Marisa sẽ sửa chúng khác nhau).
Marisa dự định chọn ra $k$ tấm gỗ để làm hàng rào bao quanh nhà. Trong đó, cô sẽ chọn ra $k - 1$ tấm để dựng hàng rào và 1 tấm để làm cửa. Khi đó, những tấm để làm hàng rào sẽ có độ đẹp là $A_i$ và tấm để làm cửa sẽ có độ đẹp là $B_i$.
Marisa đang cân nhắc số lượng tấm gỗ sử dụng để làm hàng rào, nên cô sẽ hỏi bạn $q$ câu hỏi, mỗi câu hỏi là một số nguyên $k$, hãy giúp cô tính độ đẹp lớn nhất có thể khi sử dụng $k$ tấm gỗ.
Dữ liệu vào từ tệp văn bảnxayhangrao.inp:
Dòng đầu tiên gồm hai số nguyên $n, q$.
Dòng thứ hai gồm $n$ số nguyên $A_i$.
Dòng thứ ba gồm $n$ số nguyên $B_i$.
Dòng thứ tư gồm $q$ số nguyên $k$ theo thứ tự, mô tả các truy vấn.
Kết quả ghi ra tệp văn bảnxayhangrao.out: In ra $q$ số nguyên, số nguyên thứ $i$ là đáp án truy vấn thứ $i$.
Giới hạn: Trong mọi test: $1 \le n, q \le 10^5$, $1 \le A_i, B_i \le 10^9$.
Subtask 1 (25% số điểm): Marisa chỉ hỏi bạn một câu hỏi duy nhất với $k = n$.
Subtask 2 (25% số điểm): $1 \le n, q \le 10$.
Subtask 3 (25% số điểm): $1 \le n, q \le 1000$.
Subtask 4 (25% số điểm): Không có giới hạn gì thêm.
Ví dụ: (khung trái là nội dung xayhangrao.inp, khung phải là nội dung xayhangrao.out)
Ví dụ 1 – input
3 1
3 5 4
5 8 5
3
Ví dụ 1 – output
15
Ví dụ 2 – input
3 2
3 5 4
5 8 5
3 2
Ví dụ 2 – output
15 12
Lưu ý về đọc/ghi file: các code bên dưới dùng mẹo if (fopen("xayhangrao.inp", "r")) { freopen(...); freopen(...); } (Python: if os.path.exists("xayhangrao.inp")): có file thì đọc/ghi file, không có thì đọc bàn phím và in ra màn hình. Nhờ vậy cùng 1 code nộp được cả lên hệ thống chấm đọc từ bàn phím lẫn khi thi chấm bằng file.
Lời mở đầu
Bài này mình được một em học viên hỏi và mình đã hướng dẫn chi tiết cách thức giải quyết cho em ấy. Tin rằng sẽ có giá trị với nhiều bạn nên mình chia sẻ đề bài để các bạn thử sức làm, kèm thêm đó là toàn bộ những gì mình đã trao đổi với em ấy để bạn nào không giải quyết được thì có thể tham khảo nhen. Hi vọng mang đến được giá trị cho các bạn. Các bạn bấm vào link này để vào nộp bài nhé:
Dành cho học viên · Ưu tiênNộp bài trên hệ thống CLUE OJ
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Chưa có tài khoản thì tạo tài khoản rồi đăng nhập nộp bài thử hen.
Đầu tiên giải thích đề bài nhé, sợ em chưa hiểu rõ. Bài đó tóm lại là thế này: $(A_i, B_i)$ là 1 thằng nhé, thì hãy chọn ra 1 thằng ở mảng $B$ và $k - 1$ thằng ở mảng $A$ sao cho tổng tụi nó là lớn nhất và các chỉ số index phân biệt nhau.
Ví dụ test 1 đề cho thì giải thích như sau (tính index từ 1 cho dễ nhé): khi $k = 3$, chọn thằng $B_2$ và $A_1$, $A_3$. Nên là: $8 + 3 + 4 = 15$.
1
2
3
A (rào)
3
5
4
B (cửa)
5
8
5
k = 3: cửa B2 = 8, rào A1 = 3, A3 = 4 → 15. Cột 2 đã làm cửa nên A2 = 5 bị gạch.
Có bạn lại thắc mắc là:
HV
“Sao không chọn 8 + 5 + 4 mà lại chọn 8 + 3 + 4 ạ?”
Trả lời: Nếu chọn thằng 5 ở mảng $A$ thì đó là index 2, trong khi ta đã chọn index 2 ở mảng $B$ rồi mà em, không được trùng. Số 8 đã chọn là index 2 ở mảng $B$ rồi. Em hiểu không? Nếu đã chọn $B_2$ thì sẽ không được chọn $A_2$ và ngược lại.
HV
“e đọc e chỉ hiểu là ngta chọn ra k-1 tấm a và 1 tấm b chứ e không thấy nó phải né vị trí nhau”
Trả lời: Em đọc kỹ đề bài khúc đầu tiên nó có nói câu này: "tấm gỗ thứ $i$ sẽ có độ đẹp là $A_i$ hoặc $B_i$". Có nghĩa là $(A_i, B_i)$ là 1 lựa chọn. Ví dụ nếu chọn index 1 thì nó chỉ có thể là $A_1$ hoặc $B_1$ chứ không thể cùng cả 2, vì tụi nó chỉ là 1 tấm gỗ thôi.
Tương tự ví dụ 2: với $k = 2$ thì chọn cửa $B_2 = 8$ và 1 tấm rào lớn nhất còn lại là $A_3 = 4$ ⇒ $12$.
Ý tưởngTham lam + vét cạn trước
Bài này dùng tư tưởng tham lam (Greedy) để giải quyết. Kể cả bạn nào không biết về tư tưởng tham lam thì thực ra đôi khi các bạn đang giải quyết vấn đề theo chính tư tưởng của tham lam mà các bạn không biết.
Tham lam là gì?
Ta sẽ cố gắng chọn ra cách giải quyết tốt nhất trong tất cả các cách ở hiện tại rồi đi theo cách đó; nếu lại đứng trước nhiều lựa chọn khác nhau nữa thì ta lại cố gắng chọn cách tốt nhất trong số đó, tóm lại cứ tốt nhất mà triển, vì thế tên gọi nó là tham lam. Quy luật nó là như vậy thôi chứ không có công thức từng bước cụ thể như mấy thuật toán khác.
Anh nói em thế này: mọi bài nếu chưa nhìn ra thuật ăn full 100% của nó thì trước tiên hãy làm theo cách VÉT CẠN để ăn thử trước 1 số subtask và cũng để kiểm chứng ý tưởng đó có đúng không. Rồi khi thấy nó đúng rồi (tức là ăn hết được 1 số subtask nhỏ và bị TLE với các subtask lớn, tuyệt đối không có bị WA mà chỉ bị TLE) thì lúc này nhìn vào code vét cạn đó mà cải tiến lên để ăn full. Tất nhiên nói là vét cạn nhưng tư tưởng của nó cũng vẫn phải THAM LAM nha.
Gợi ý mấu chốt: chọn 1 phần tử ở mảng $B$ và $k - 1$ phần tử ở mảng $A$, thì $k$ có thể lớn lắm ($k \le n \le 10^5$), nhưng hãy nhìn lại mảng $B$ thì chỉ cần chọn 1 thằng thôi, chú ý kỹ nhé chỉ 1 thằng thôi. Đó là mấu chốt để nhìn ra ý tưởng vét cạn: mảng $B$ cần chọn 1 phần tử thì cứ giả sử chọn lần lượt từ $B_1$ đến $B_n$ thôi, rồi với mỗi lựa chọn đó sẽ chọn $k - 1$ phần tử lớn nhất còn lại trong mảng $A$ (khác index phần tử đã chọn của mảng $B$). Kết quả lớn nhất trong tất cả các cách chọn đó chính là đáp án.
Cách 1Sắp xếp + duyệt mỗi truy vấn – O(Q·N)
Đọc cặp số $(A_i, B_i)$ tương ứng là (first, second) em nhé, tức là ta có mảng pair hen. Sau đó sort tăng dần theo first. Ta sẽ bám theo yếu tố là ở second thì chỉ chọn duy nhất 1 tấm gỗ làm cửa, còn ở first thì chọn $k - 1$ tấm làm rào.
Tưởng tượng giờ nó đang tăng dần theo first, thì $k - 1$ thằng first cuối cùng sẽ có tổng lớn nhất tại vì tụi nó đang mang giá trị lớn nhất. Vậy:
Trường hợp cửa nằm ngoài nhóm cuối: chọn $k - 1$ tấm first cuối cùng, thì để tham lam các thằng second từ đầu đến vị trí còn lại sẽ chọn thằng lớn nhất.
Trường hợp cửa nằm trong nhóm cuối: lần lượt cho cửa là 1 trong các tấm cuối, khi đó tấm first ở vị trí đó bị bỏ ra và ta lấy thêm tấm first ngay phía trước nhóm.
Ví dụ nếu $n = 10$, $k = 3$ (số thứ tự tính từ 1 nhé), thì đầu tiên ta có: Max = a[10].first + a[9].first + max(a[1].second → a[8].second). Rồi giả sử chọn cửa là a[9].second thì để lớn nhất sẽ chọn a[10].first, a[8].first: Max = max(Max, a[9].second + a[10].first + a[8].first). Rồi chọn cửa là a[10].second thì chọn a[9].first, a[8].first: Max = max(Max, a[10].second + a[9].first + a[8].first). Lúc này đã xong, giá trị Max sau cùng là đáp án ứng với $k = 3$.
Anh liệt kê ra vài trường hợp $k = 2, 3, 4$ với $n = 10$ cho em xem, mỗi $k$ chọn Max của tất cả các dòng:
Em nhập 2 dãy $A$, $B$ và số $k$ rồi bấm Tiếp: widget sẽ sắp xếp theo first, tô vàng các tấm làm rào, xanh tấm làm cửa (hoặc vùng lấy max second), rồi so sánh tất cả các trường hợp:
Ví dụ nhanh:
Với tư tưởng tham lam này dễ thấy với mỗi trường hợp $k$ ta sẽ xét qua hết $N$ phần tử là ra đáp án, và sẽ có $Q$ câu hỏi như vậy. Vậy cách làm vét cạn trước mắt sẽ có độ phức tạp $O(Q \cdot N)$, mà $Q, N$ tối đa $10^5$ nên $Q \cdot N = 10^{10}$, chắc chắn TLE vì đã vượt quá ngưỡng giới hạn 1 giây là $10^8$ rồi (vượt quá cả 100 lần). Nên chỉ ăn được 3 subtask đầu tiên, tức là 75% điểm:
Tất cả đều thỏa nhỏ hơn $10^8$ nên yên tâm cách làm có độ phức tạp $O(Q \cdot N)$ sẽ AC được 3 subtask đầu tiên. Đây là code theo cách này cho em tham khảo (trong code chỉ số tính từ 0, biến k được đổi thành n - k = vị trí tấm first "dự bị" ngay trước nhóm $k - 1$ tấm cuối):
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
if (fopen("xayhangrao.inp", "r")) {
freopen("xayhangrao.inp", "r", stdin);
freopen("xayhangrao.out", "w", stdout);
}
long long n, q;
cin >> n >> q;
vector<pair<long long, long long>> a(n);
for(int i = 0; i < n; ++i){
cin >> a[i].first;
}
for(int i = 0; i < n; ++i){
cin >> a[i].second;
}
sort(a.begin(), a.end());
while(q--){
long long k;
cin >> k;
k = n - k;
long long sum = 0;
for(int i = k + 1; i < n; ++i){
sum += a[i].first;
}
long long Max = a[0].second;
for(int i = 1; i <= k; ++i){
Max = max(Max, a[i].second);
}
long long res = sum + Max;
sum += a[k].first;
for(int i = k + 1; i < n; ++i){
res = max(res, sum + a[i].second - a[i].first);
}
cout << res << " ";
}
return 0;
}
import sys, os
if os.path.exists("xayhangrao.inp"):
sys.stdin = open("xayhangrao.inp", "r")
sys.stdout = open("xayhangrao.out", "w")
n, q = map(int, input().split())
a = []
first = list(map(int, input().split()))
second = list(map(int, input().split()))
for i in range(n):
a.append((first[i], second[i]))
a.sort()
ks = list(map(int, input().split()))
for k in ks:
k = n - k
sum_ = 0
for i in range(k + 1, n):
sum_ += a[i][0]
Max = a[0][1]
for i in range(1, k + 1):
Max = max(Max, a[i][1])
res = sum_ + Max
sum_ += a[k][0]
for i in range(k + 1, n):
res = max(res, sum_ + a[i][1] - a[i][0])
print(res, end=' ')
C++▶ Chạy tay từng dòng codeCách 1: sort theo first, mỗi truy vấn duyệt N phần tử (TH1 + thử cửa trong nhóm cuối), O(Q·N).
Dữ liệu mẫu:
1#include <bits/stdc++.h>
2usingnamespace std;
3
4int main(){
5ios::sync_with_stdio(0);
6cin.tie(0);
7if (fopen("xayhangrao.inp", "r")) {
8 freopen("xayhangrao.inp", "r", stdin);
9 freopen("xayhangrao.out", "w", stdout);
10 }
11longlong n, q;
12cin >> n >> q;
13vector<pair<longlong, longlong>> a(n);
14for(int i = 0; i < n; ++i){
15cin >> a[i].first;
16 }
17for(int i = 0; i < n; ++i){
18cin >> a[i].second;
19 }
20sort(a.begin(), a.end());
21while(q--){
22longlong k;
23cin >> k;
24 k = n - k;
25longlong sum = 0;
26for(int i = k + 1; i < n; ++i){
27 sum += a[i].first;
28 }
29longlong Max = a[0].second;
30for(int i = 1; i <= k; ++i){
31 Max = max(Max, a[i].second);
32 }
33longlong res = sum + Max;
34 sum += a[k].first;
35for(int i = k + 1; i < n; ++i){
36 res = max(res, sum + a[i].second - a[i].first);
37 }
38cout << res << " ";
39 }
40return0;
41}
Không gian$O(N)$
Thời gian$O(N \log N + Q \cdot N)$
Cách 2Tính sẵn đáp án mọi k – O(N log N + Q)
Còn để ăn được subtask cuối cùng thì em phải tìm cách tối ưu hơn. Nhận thấy rằng $N$ tối đa $10^5$ thì ta sẽ tính hết các trường hợp $k$ từ 1 đến $n$ trước. Vấn đề là chỗ này hãy nhìn kỹ nhé: không cần phải 2 vòng lặp lồng nhau vì nếu làm thế độ phức tạp sẽ là $O(N^2)$, mà chỗ này chỉ cần 1 vòng lặp duy nhất chạy từ 1 đến $n$ là tính ra được hết các đáp án. Để làm được điều đó em phải nhìn vào bản chất của các công thức. Anh viết lại công thức với $k = 2, 3, 4$ và $n = 10$ dưới dạng tổng sum, đánh dấu 3 màu: đỏ, cam, vàng:
Ở $k = 2$ thì chỉ có đỏ, cam, không có vàng; còn từ $k = 3$ trở lên là có đủ 3 màu. Em hãy nhìn những khối cùng màu trong các trường hợp $k$: ví dụ từ khối màu cam của $k = 2$ đi qua khối màu cam của $k = 3$ rồi đi qua khối màu cam của $k = 4$; từ khối màu vàng của $k = 3$ đi qua khối màu vàng của $k = 4$. Anh nghĩ em sẽ nhìn ra thứ gì đó 😉
Nhìn bằng hình: n = 10, k = 5
Khi $k = 5$ nghĩa là cần lấy 1 cái từ second và 4 cái từ first:
Hình 2 · k = 5, n = 10, first đang tăng dần
1
2
3
4
5
6
7
8
9
10
TH1
first
second
max các second tô xanh
TH2
first
second
TH3
first
second
TH4
first
second
TH5
first
second
TH1: lấy 4 cái first to nhất (vì đang sắp tăng dần nên 4 thằng cuối cùng là 4 thằng to nhất), anh tô vàng đó; còn lại các thằng second được tô xanh thì lấy thằng có giá trị lớn nhất trong đó.
TH2 → TH5:second lần lượt lấy vào các vị trí của 4 thằng tô vàng ở TH1. Khi second lấy vào vị trí thằng tô vàng nào thì thằng tô vàng đó sẽ dịch xuống 1 vị trí: TH2 second lấy vị trí 7 thì first ở vị trí 7 bỏ đi và ta lấy first ở vị trí 6; TH3 second lấy vị trí 8 thì bỏ first vị trí 8, lấy vị trí 6, 7…
Như thế em thấy từ TH2 trở đi, first luôn lấy tổng từ vị trí 6 đến 10, rồi trừ đi first ở vị trí cửa:
Mảng MaxSecond: MaxSecond[i] = giá trị second lớn nhất của a[1], a[2], …, a[i] (lớn nhất từ đầu đến vị trí $i$) ⇒ chỉ cần $O(N)$ là tạo ra được.
Mảng SumFirst: SumFirst[i] = tổng các giá trị first từ vị trí $i$ đến cuối mảng: a[i] + a[i+1] + … + a[n] ⇒ cũng chỉ $O(N)$.
Giờ nhìn lại "Hình 1":
Màu đỏ: $k = 2$ là MaxSecond[9] + SumFirst[10]; $k = 3$ là MaxSecond[8] + SumFirst[9]; $k = 4$ là MaxSecond[7] + SumFirst[8]. Em có thấy cứ mỗi $k$ tăng lên 1 thì index của 2 thằng MaxSecond, SumFirst bị giảm đi 1 so với trước đó không? ⇒ tính trực tiếp $O(1)$.
Màu cam: $k = 2$ là SumFirst[9] − a[10].first + a[10].second; $k = 3$ là SumFirst[8] − a[10].first + a[10].second, tức là chính trường hợp $k = 2$ nhưng cộng thêma[8].first; $k = 4$ là trường hợp $k = 3$ cộng thêm a[7].first. Vậy max của cả khối cam chỉ cần lấy max cũ + first mới.
Màu vàng: $k = 2$ không có, từ $k = 3$: SumFirst[8] − a[9].first + a[9].second; qua $k = 4$ thì là SumFirst[7] − a[8].first + a[8].second: nó chỉ lùi lại 1 index. Và khối vàng của $k$ này sẽ nhập vào khối cam của $k + 1$.
Đó, em nhìn ra những điểm tương đồng thì ở mỗi $k$ em tính ra Max của màu đỏ (Max1) và Max của màu cam + vàng (Max2). Khi đi qua $k$ tiếp theo thì dựa trên các biến Max của trường hợp trước đó mà sinh ra thêm cái mới rồi so sánh cập nhật lại ⇒ 1 vòng for chạy từ 1 đến N là đủ:
Rồi thì lưu các đáp án ứng với $k$ từ 1 đến $n$ đó lại (lúc hướng dẫn anh gợi ý dùng map hay unordered_map, nhưng vì key chính là $k$ từ 1 đến $n$ nên dùng luôn mảng vectorump là gọn và nhanh nhất), mỗi truy vấn chỉ việc in ump[k] trong $O(1)$:
Bước input: $O(N)$.
Bước sort: $O(N \log N)$.
Bước xử lý: $O(\max(N, Q))$.
⇒ Tổng độ phức tạp của bài: $O(N \log N + Q)$. Đây là code của anh theo đúng ý tưởng đã nói, đã nộp AC trên web:
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
if (fopen("xayhangrao.inp", "r")) {
freopen("xayhangrao.inp", "r", stdin);
freopen("xayhangrao.out", "w", stdout);
}
long long n, q;
cin >> n >> q;
vector<pair<long long, long long>> a(n);
for(int i = 0; i < n; ++i){
cin >> a[i].first;
}
for(int i = 0; i < n; ++i){
cin >> a[i].second;
}
sort(a.begin(), a.end());
vector<long long> MaxSecond(n);
MaxSecond[0] = a[0].second;
for(int i = 1; i < n; ++i){
MaxSecond[i] = max(MaxSecond[i - 1], a[i].second);
}
vector<long long> sumFirst(n);
sumFirst[n - 1] = a[n - 1].first;
for(int i = n - 2; i >= 0; --i){
sumFirst[i] = sumFirst[i + 1] + a[i].first;
}
vector<long long> ump(n + 1);
ump[1] = MaxSecond[n - 1];
if(n >= 2){
long long Max1 = MaxSecond[n - 2] + sumFirst[n - 1];
long long Max2 = sumFirst[n - 2] - a[n - 1].first + a[n - 1].second;
ump[2] = max(Max1, Max2);
int j = 0;
for(int k = 3; k <= n; ++k){
j++;
Max1 = MaxSecond[n - 2 - j] + sumFirst[n - 1 - j];
Max2 = max(Max2 + a[n - k].first, sumFirst[n - k] - a[n - k + 1].first + a[n - k + 1].second);
ump[k] = max(Max1, Max2);
}
}
while(q--){
long long x;
cin >> x;
cout << ump[x] << " ";
}
return 0;
}
import sys, os
if os.path.exists("xayhangrao.inp"):
sys.stdin = open("xayhangrao.inp", "r")
sys.stdout = open("xayhangrao.out", "w")
n, q = map(int, input().split())
first = list(map(int, input().split()))
second = list(map(int, input().split()))
a = [(first[i], second[i]) for i in range(n)]
a.sort()
MaxSecond = [0] * n
MaxSecond[0] = a[0][1]
for i in range(1, n):
MaxSecond[i] = max(MaxSecond[i - 1], a[i][1])
sumFirst = [0] * n
sumFirst[-1] = a[-1][0]
for i in range(n - 2, -1, -1):
sumFirst[i] = sumFirst[i + 1] + a[i][0]
ump = [0] * (n + 1)
ump[1] = MaxSecond[n - 1]
if n >= 2:
Max1 = MaxSecond[n - 2] + sumFirst[n - 1]
Max2 = sumFirst[n - 2] - a[n - 1][0] + a[n - 1][1]
ump[2] = max(Max1, Max2)
j = 0
for k in range(3, n + 1):
j += 1
Max1 = MaxSecond[n - 2 - j] + sumFirst[n - 1 - j]
Max2 = max(Max2 + a[n - k][0], sumFirst[n - k] - a[n - k + 1][0] + a[n - k + 1][1])
ump[k] = max(Max1, Max2)
queries = list(map(int, input().split()))
for x in queries:
print(ump[x], end=' ')
C++▶ Chạy tay từng dòng codeCách 2: tính sẵn MaxSecond, sumFirst rồi 1 vòng for ra ump[k] cho mọi k, mỗi truy vấn O(1).
Ghi chú của mình: code C++ và Python của cả 2 cách là của anh, mình chỉ thêm mẹo fopen / os.path.exists để đọc/ghi file. Cả 4 bản đã được kiểm tra với 300 bộ test ngẫu nhiên ($n, q \le 8$, giá trị nhỏ nhiều số trùng lẫn giá trị tới $10^9$) so với code vét cạn thử mọi tấm làm cửa rồi lấy $k - 1$ tấm rào lớn nhất còn lại: khớp 100%. Với $n = q = 10^5$: cách 2 bản C++ chạy khoảng 0.06 giây, bản Python khoảng 0.9 giây; cách 1 bản C++ chạy hơn 10 giây ⇒ TLE subtask 4 đúng như phân tích (với $n = q = 1000$ chỉ mất vài mili giây).
Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇
Nguồn: HSG Duyên Hải 2021 – Tin 10Độ khó: Trung bìnhSàng nguyên tốMảng cộng dồn
Đề bài
Bài 1. Bài dễ (Kỳ thi học sinh giỏi các trường THPT chuyên khu vực Duyên Hải và Đồng Bằng Bắc Bộ năm học 2020 – 2021, môn Tin học 10)
Trong một kỳ thi, việc sáng tạo bài dễ nhất trong đề thi nhiều khi cũng mất không ít thời gian. Trong đề thi Duyên Hải năm 2021, Ban giám khảo muốn tạo một bài dễ thao tác trên dãy số cho các học sinh khối 10. Bài toán dưới đây đã được sáng tạo và chọn vào đề thi, bài toán này có thể giải được bằng nhiều thuật toán khác nhau.
Cho dãy số nguyên $a_1, a_2, \ldots, a_n$, một đoạn $a_L, a_{L+1}, \ldots, a_R$ $(1 \le L \le R \le n)$ được gọi là đoạn đẹp nếu $L, R$ đều là số nguyên tố. Hãy tìm đoạn đẹp có tổng lớn nhất.
Dữ liệu: Vào từ thiết bị vào chuẩn theo khuôn dạng:
Dòng đầu chứa số nguyên dương $n$ $(n \ge 2)$;
Dòng thứ hai chứa $n$ số nguyên $a_1, a_2, \ldots, a_n$ $(|a_i| \le 10^6)$.
Kết quả: Ghi ra thiết bị ra chuẩn một số nguyên là tổng lớn nhất của đoạn đẹp tìm được.
Ràng buộc:
Có 40% số lượng test ứng với 40% số điểm thỏa mãn điều kiện: $n \le 100$;
Có 30% số lượng test khác ứng với 30% số điểm thỏa mãn điều kiện: $n \le 3000$;
Có 30% số lượng test còn lại ứng với 30% số điểm thỏa mãn điều kiện: $n \le 10^6$.
Ví dụ – input
6
9 5 -2 6 -1 1
Ví dụ – output
8
Lời mở đầu
Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇. Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì link bài đây nhé:
Dành cho học viên · Ưu tiênNộp bài trên hệ thống CLUE OJ
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Chưa có tài khoản thì tạo tài khoản rồi đăng nhập nộp bài thử hen.
Bài này mình sẽ đi 9 cách làm, tối ưu dần từ vét cạn $O(N^3)$ (cần 317 năm với $N = 10^6$) xuống $O(N \log \log N)$ (chỉ 0.05 giây). Đi từng bước như vậy các bạn sẽ thấy rõ mỗi lần tối ưu là bỏ đi được chỗ "dư thừa" nào.
Trước khi đi vào vấn đề chính của bài thì mình muốn các bạn phải đảm bảo biết qua điều này để về sau các bạn xem mới hiểu:
Với các hệ thống web chấm bài giới hạn thời gian chạy tối đa chỉ được 1 giây thì các bạn sẽ rất dễ bị rơi vào lỗi Time Limit Exceeded (TLE: chạy quá giới hạn thời gian cho phép). Thì như mình đã nói rất nhiều lần, nếu không muốn bị TLE thì tối đa số phép toán trên toàn bài chỉ nên ở ngưỡng $(3 \text{ đến } 5) \cdot 10^7$ là ngưỡng an toàn với phần lớn hệ thống chấm bài, hoặc với một số hệ thống chấm server mạnh hơn thì có thể nâng ngưỡng lên $10^8$ nhưng cũng hên xui nhé.
Và thực ra ta không phải đếm chi tiết từng phép toán mà ta dựa theo số lần vòng lặp chạy, bởi bên trong vòng lặp là nó xử lý lặp đi lặp lại nhiều phép toán nên cứ canh theo đó: tối đa toàn bài chỉ nên lặp $(3 \text{ đến } 5) \cdot 10^7$ lần là an toàn, hoặc tệ nhất là $10^8$ (lúc này thì hên xui), còn vượt ngưỡng này là khả năng TLE rất cao nhe.
Lưu ý
Ngưỡng trên là với ngôn ngữ C/C++ thôi nhé. Với những ngôn ngữ chạy chậm hơn như Python, C# hay Java thì ngưỡng đó phải thấp hơn, hoặc người ra đề sẽ chủ động cho giới hạn khác nhau (C/C++ 1 giây, ngôn ngữ khác 2 giây). Đề cho 2 giây thì các bạn cứ nhân 2 ngưỡng lên, 3 giây thì nhân 3, nếu 100 ms tức là 1/10 giây thì chia 10, cứ thế thôi.
Bài này giới hạn thời gian 1 giây (còn bộ nhớ thì cho dư dả cả 1 GB), nên các bạn rất cần quan tâm đến giới hạn $N$ tối đa là $10^6$, vì độ phức tạp thuật toán phụ thuộc theo $N$.
Làm rõ đềĐoạn đẹp là gì?
Mình sẽ nói rõ hơn đề bài cho bạn nào chưa hiểu: một đoạn đẹp là đoạn bắt đầu từ vị trí $L$ và kết thúc ở vị trí $R$ với $L$ và $R$ đều phải là số nguyên tố và $L \le R$. Quy ước vị trí bắt đầu tính từ 1 (chứ không phải tính từ 0 nha các bạn lưu ý kỹ chỗ này). Tổng đoạn đẹp là $a_L + a_{L+1} + \ldots + a_R$. Yêu cầu tìm tổng lớn nhất của các đoạn đẹp và in ra.
Như ví dụ đề cho $N = 6$ số: 9 5 -2 6 -1 1 thì các vị trí là số nguyên tố là 2, 3, 5. Vậy ta có các đoạn đẹp:
Đoạn
Dãy (ô tô màu = trong đoạn)
Tổng
L = 2, R = 2
95-26-11
5
L = 2, R = 3
95-26-11
3
L = 2, R = 5
95-26-11
8
L = 3, R = 3
95-26-11
-2
L = 3, R = 5
95-26-11
3
L = 5, R = 5
95-26-11
-1
Đoạn đẹp có tổng lớn nhất là 8 với $L = 2, R = 5$. Đề không yêu cầu in $L, R$ mà chỉ cần tổng lớn nhất nên ta in ra 8.
Nếu giả sử mảng chỉ toàn số dương thì quá đơn giản: đoạn đẹp lớn nhất sẽ là đoạn dài nhất với $L$ bé nhất và $R$ lớn nhất là số nguyên tố. Tuy nhiên mọi thứ đâu dễ dàng vậy hihi, mảng có cả số âm vì thế quy luật đó không áp dụng được.
Bảng tổng kết 9 cách
Cách
Ý chính
Thời gian
Subtask qua được
1
Vét cạn mọi cặp L, R, tính tổng lại
$O(N^3)$
40% ($N \le 100$)
2
Chỉ xét R khi L nguyên tố
$O(N^3)$, nhanh hơn
40%
3
Cộng dồn sum khi đi R, bỏ vòng tính tổng
$O(N^2 \sqrt N)$
40% (+ một phần)
4, 5
Mảng đánh dấu b, kiểm tra nguyên tố 1 lần
$O(N^2)$
70% ($N \le 3000$)
6
Sàng Eratosthenes
$O(N^2)$
70%
7
Prefix sum
$O(N^2)$
70%
8
Prefix sum + Min của P[L−1]
$O(N \log \log N)$
100%
9
Như 8 nhưng không cần mảng a
$O(N \log \log N)$
100%
Cách 1Vét cạn mọi cặp L, R – O(N³)
Một cách cơ bản nhất mà nhiều bạn sẽ nghĩ ra đó là vét cạn xét tất cả mọi trường hợp có thể: xét hết các cặp $L, R$ là số nguyên tố thỏa $1 \le L \le R \le N$. Max ban đầu khởi tạo là a[2] vì đề đã ràng buộc $N \ge 2$ nên a[2] chắc chắn tồn tại và hợp lệ (lúc này hiểu $L = R = 2$). Rồi cứ với mỗi cặp $L, R$ ta duyệt tính tổng các phần tử từ $L$ đến $R$ sau đó so sánh với Max và cập nhật lại. Sau cùng in ra Max.
Source code để các bạn tham khảo nếu làm theo hướng này:
#include <bits/stdc++.h>
using namespace std;
bool isPrime(long long x){
for(long long i = 2; i * i <= x; ++i){
if(x % i == 0){
return false;
}
}
return x >= 2;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector<long long> a(n + 1);
for(int i = 1; i <= n; ++i){
cin >> a[i];
}
long long Max = a[2];
for(int L = 2; L <= n; ++L){
for(int R = L; R <= n; ++R){
if(isPrime(L) && isPrime(R)){
long long sum = 0;
for(int i = L; i <= R; ++i){
sum += a[i];
}
Max = max(Max, sum);
}
}
}
cout << Max;
return 0;
}
import sys
input = sys.stdin.readline
def is_prime(x):
if x < 2:
return False
i = 2
while i * i <= x:
if x % i == 0:
return False
i += 1
return True
n = int(input())
a = [0] + list(map(int, input().split()))
Max = a[2]
for L in range(2, n + 1):
for R in range(L, n + 1):
if is_prime(L) and is_prime(R):
total = sum(a[L:R + 1])
Max = max(Max, total)
print(Max)
C++▶ Chạy tay từng dòng codeCách 1: vét cạn mọi cặp (L, R), mỗi cặp đẹp thì tính lại tổng từ L đến R – O(N³).
Dữ liệu mẫu:
1#include <bits/stdc++.h>
2usingnamespace std;
3
4bool isPrime(longlong x){
5for(longlong i = 2; i * i <= x; ++i){
6if(x % i == 0){
7returnfalse;
8 }
9 }
10return x >= 2;
11}
12
13int main(){
14ios::sync_with_stdio(0);
15cin.tie(0);
16int n;
17cin >> n;
18vector<longlong> a(n + 1);
19for(int i = 1; i <= n; ++i){
20cin >> a[i];
21 }
22longlong Max = a[2];
23for(int L = 2; L <= n; ++L){
24for(int R = L; R <= n; ++R){
25if(isPrime(L) && isPrime(R)){
26longlong sum = 0;
27for(int i = L; i <= R; ++i){
28 sum += a[i];
29 }
30 Max = max(Max, sum);
31 }
32 }
33 }
34cout << Max;
35return0;
36}
Giải thích một số chỗ trong code ở trên:
2 dòng đầu tiên của hàm main ios::sync_with_stdio(0); cin.tie(0); giúp đẩy nhanh tốc độ nhập xuất dữ liệu trong C++. Bài này input có thể lên đến 1 triệu số nên ta nên thêm 2 dòng này vào đầu để chương trình chạy nhanh hơn (code C thì không cần).
Vì mảng có thể lên đến 1 triệu số nên mình dùng vector thay vì mảng tĩnh. Các bạn cứ nhớ kinh nghiệm: mảng tĩnh khai báo trong hàm chỉ nên lưu tối đa ở mức $3 \cdot 10^5$ phần tử, vượt quá thì nên dùng mảng động để tránh bị tràn bộ nhớ.
Hàm isPrime(x) trả về true nếu $x$ là số nguyên tố. Số nguyên tố là số $\ge 2$ và chỉ có đúng 2 ước là 1 và chính nó. Không cần xét từ 2 đến $x - 1$ mà chỉ cần đến $\sqrt{x}$ là đủ, độ phức tạp $O(\sqrt{X})$ thay vì $O(X)$. Điều kiện i * i <= x ⇔ i <= sqrt(x) nhưng nên dùng i * i <= x vì hàm sqrt có thể bị sai số và gọi hàm cũng không bao giờ tốt bằng 1 phép tính.
Sau cùng return x >= 2;: nếu chạy được xuống dòng đó tức là vòng lặp không return false. Có 2 lý do: hoặc vòng lặp đã chạy mà không tìm thấy ước nào (lúc này $x$ là số nguyên tố), hoặc vòng lặp không chạy lần nào vì $2 \cdot 2 > x$ tức $x \le 3$: khi đó 3, 2 là số nguyên tố còn từ 1 trở xuống thì không. Vậy nên return x >= 2 xử lý gọn cả 2 trường hợp.
Vòng for L bắt đầu từ 2 (vị trí hợp lệ đầu tiên). Vòng for R bắt đầu từ $L$ vì đề cho $L \le R$, tức là có cả trường hợp $L = R$.
Đánh giá độ phức tạp: không gian $O(N)$. Thời gian: 2 vòng lặp for L, for R lồng nhau là $O(N^2)$; bên trong còn gọi kiểm tra nguyên tố $O(2\sqrt{N})$ và vòng tính tổng $O(N)$. Tổng lại $O(N^2 \cdot (2\sqrt{N} + N)) = O(N^3)$ (theo quy tắc cộng Big-O lấy thành phần lớn nhất).
Với $N = 10^6$ thì $N^3 = 10^{18}$, chia cho ngưỡng $10^8$ phép/giây là $10^{10}$ giây ⇔ 317 năm mới ra kết quả 😱. TLE là cái chắc, nên ta cần tìm ra cách tối ưu hơn.
Không gian$O(N)$
Thời gian$O(N^3)$
Cách 2Chỉ xét R khi L là số nguyên tố
Một cái dở của cách làm ở trên là với mọi giá trị $L$ đều xét qua mọi giá trị $R \ge L$ rồi mới kiểm tra cả $L$ và $R$ có là số nguyên tố không. Rõ ràng nếu $L$ không phải là số nguyên tố thì vẫn lặp xét toàn bộ $R$ là dư thừa, vì đằng nào cũng không tính được. Nên sẽ tối ưu hơn khi ta chỉ xét những $L$ là số nguyên tố rồi lúc đó mới xét những $R \ge L$:
#include <bits/stdc++.h>
using namespace std;
bool isPrime(long long x){
for(long long i = 2; i * i <= x; ++i){
if(x % i == 0){
return false;
}
}
return x >= 2;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector<long long> a(n + 1);
for(int i = 1; i <= n; ++i){
cin >> a[i];
}
long long Max = a[2];
for(int L = 2; L <= n; ++L){
if(isPrime(L)){
for(int R = L; R <= n; ++R){
if(isPrime(R)){
long long sum = 0;
for(int i = L; i <= R; ++i){
sum += a[i];
}
Max = max(Max, sum);
}
}
}
}
cout << Max;
return 0;
}
import sys
input = sys.stdin.readline
def is_prime(x):
if x < 2:
return False
i = 2
while i * i <= x:
if x % i == 0:
return False
i += 1
return True
n = int(input())
a = [0] + list(map(int, input().split())) # 1-based index
Max = a[2]
for L in range(2, n + 1):
if is_prime(L):
for R in range(L, n + 1):
if is_prime(R):
total = 0
for i in range(L, R + 1):
total += a[i]
Max = max(Max, total)
print(Max)
C++▶ Chạy tay từng dòng codeCách 2: chỉ khi L là số nguyên tố mới duyệt R – vẫn O(N³) nhưng bớt việc thừa.
Dữ liệu mẫu:
1#include <bits/stdc++.h>
2usingnamespace std;
3
4bool isPrime(longlong x){
5for(longlong i = 2; i * i <= x; ++i){
6if(x % i == 0){
7returnfalse;
8 }
9 }
10return x >= 2;
11}
12
13int main(){
14ios::sync_with_stdio(0);
15cin.tie(0);
16int n;
17cin >> n;
18vector<longlong> a(n + 1);
19for(int i = 1; i <= n; ++i){
20cin >> a[i];
21 }
22longlong Max = a[2];
23for(int L = 2; L <= n; ++L){
24if(isPrime(L)){
25for(int R = L; R <= n; ++R){
26if(isPrime(R)){
27longlong sum = 0;
28for(int i = L; i <= R; ++i){
29 sum += a[i];
30 }
31 Max = max(Max, sum);
32 }
33 }
34 }
35 }
36cout << Max;
37return0;
38}
Về mặt lý thuyết độ phức tạp thì nó cũng ngang với code trước đó thôi. Nhưng thực tế chắc chắn nó sẽ tối ưu hơn: các bạn thử đem code này và code trước đó cùng nộp sẽ thấy tuy cùng Accepted 14 test và bị TLE 6 test như nhau, nhưng thời gian chạy của 14 test Accepted thì code hiện tại luôn nhanh hơn code trước đó ở tất cả các test.
Cách 3Cộng dồn sum khi đi R – O(N²√N)
Bây giờ mình sẽ trình bày cũng một cách làm theo kiểu vét cạn nhưng tối ưu hơn: xét lần lượt các vị trí $L$, với vị trí $L$ nào là số nguyên tố thì ta gán vào biến tổng rồi so sánh với Max, rồi từ $L$ đó ta duyệt tiếp $R$: vị trí nào chưa phải là số nguyên tố thì ta cứ cộng vào biến tổng rồi chưa so sánh gì cả, đến khi gặp vị trí $R$ là số nguyên tố thì sau khi cộng phần tử đó vào biến tổng xong ta mới so sánh với Max. Như ví dụ $N = 6$, khởi tạo Max = a[2]:
L = 2 (nguyên tố) ⇒ Sum = a[2] = 5, Max = max(Max, Sum)
R = 3 nguyên tố ⇒ Sum += a[3] → 3, cập nhật Max
R = 4 không nguyên tố ⇒ Sum += a[4] → 9
R = 5 nguyên tố ⇒ Sum += a[5] → 8, cập nhật Max
R = 6 không nguyên tố ⇒ Sum += a[6] → 9. Hết mảng ⇒ dừng.
L = 3 (nguyên tố tiếp theo) ⇒ Sum = a[3] = −2, cập nhật Max
R = 4 ⇒ Sum += a[4] → 4; R = 5 nguyên tố ⇒ Sum += a[5] → 3, cập nhật Max; R = 6 ⇒ Sum += a[6]. Dừng.
L = 5 ⇒ Sum = a[5] = −1, cập nhật Max; R = 6 ⇒ Sum += a[6]. Dừng.
Không còn $L$ nguyên tố nào (5 là số nguyên tố lớn nhất $\le 6$) ⇒ in ra Max = 8.
#include <bits/stdc++.h>
using namespace std;
bool isPrime(long long x){
for(long long i = 2; i * i <= x; ++i){
if(x % i == 0){
return false;
}
}
return x >= 2;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector<long long> a(n + 1);
for(int i = 1; i <= n; ++i){
cin >> a[i];
}
long long Max = a[2];
for(int L = 2; L <= n; ++L){
if(isPrime(L)){
long long sum = a[L];
Max = max(Max, sum);
for(int R = L + 1; R <= n; ++R){
sum += a[R];
if(isPrime(R)){
Max = max(Max, sum);
}
}
}
}
cout << Max;
return 0;
}
import sys
input = sys.stdin.readline
def is_prime(x):
if x < 2:
return False
i = 2
while i * i <= x:
if x % i == 0:
return False
i += 1
return True
n = int(input())
a = [0] + list(map(int, input().split())) # 1-based indexing
Max = a[2]
for L in range(2, n + 1):
if is_prime(L):
total = a[L]
Max = max(Max, total)
for R in range(L + 1, n + 1):
total += a[R]
if is_prime(R):
Max = max(Max, total)
print(Max)
C++▶ Chạy tay từng dòng codeCách 3: từ mỗi L nguyên tố đi sang phải, cộng dồn sum, gặp R nguyên tố thì so Max – O(N²√N).
Dữ liệu mẫu:
1#include <bits/stdc++.h>
2usingnamespace std;
3
4bool isPrime(longlong x){
5for(longlong i = 2; i * i <= x; ++i){
6if(x % i == 0){
7returnfalse;
8 }
9 }
10return x >= 2;
11}
12
13int main(){
14ios::sync_with_stdio(0);
15cin.tie(0);
16int n;
17cin >> n;
18vector<longlong> a(n + 1);
19for(int i = 1; i <= n; ++i){
20cin >> a[i];
21 }
22longlong Max = a[2];
23for(int L = 2; L <= n; ++L){
24if(isPrime(L)){
25longlong sum = a[L];
26 Max = max(Max, sum);
27for(int R = L + 1; R <= n; ++R){
28 sum += a[R];
29if(isPrime(R)){
30 Max = max(Max, sum);
31 }
32 }
33 }
34 }
35cout << Max;
36return0;
37}
Mấu chốt của code này tối ưu hơn ở chỗ: khi xác định được $L, R$ hợp lệ nó không cần vòng lặp từ $L$ đến $R$ nữa, vì biến tổng đã liên tục cộng dồn trong quá trình di chuyển rồi. Nó giống như kiểu bạn đi từ căn nhà ở điểm $L$, trên đường sẽ có những điểm $R$ mà tại đó bạn phải khai báo đã đi qua bao nhiêu căn nhà. Cách trước là tới $R$ lại quay về $L$ đi đếm lại, còn cách này là đếm sẵn trên đường đi, gặp $R$ là báo luôn.
Độ phức tạp không gian vẫn $O(N)$, thời gian giờ chỉ còn $O(N^2 \sqrt{N})$ vì không còn vòng lặp từ $L$ đến $R$. Với $N = 10^6$: $10^{12} \cdot 10^3 = 10^{15}$, gấp $10^7$ lần ngưỡng 1 giây ⇔ khoảng 115 ngày. Từ 317 năm xuống 4 tháng, rõ là tối ưu hơn rất nhiều 😊 nhưng vẫn chưa đủ vì bài chỉ cho 1 giây thôi :)) Ta phải suy nghĩ tối ưu tiếp hehe.
Không gian$O(N)$
Thời gian$O(N^2 \sqrt{N})$
Cách 4Mảng đánh dấu nguyên tố – O(N²)
Muốn cải tiến thì phải nhìn ra điểm chưa tốt: ta phải đi kiểm tra số nguyên tố của rất nhiều giá trị bị trùng nhau. Như $N = 6$: khi $L = 2$ ta gọi kiểm tra 2, 3, 4, 5, 6; khi $L = 3$ lại gọi kiểm tra 3, 4, 5, 6, đã bị trùng rồi nè; và cứ thế…
Vậy ta cải tiến như sau: lúc $L = 2$ (số nguyên tố đầu tiên), khi kiểm tra các giá trị $R$ từ 3 đến $N$ ta hãy lưu kết quả lại vào mảng đánh dấu b có $N + 1$ phần tử: b[i] = true nghĩa là $i$ là số nguyên tố, false là không. Từ $L = 3$ trở đi, chỉ cần gọi b[L], b[R] là biết ngay trong $O(1)$, thay vì $O(\sqrt{X})$. Ví dụ với giá trị $10^6$ thì trước đó phải chạy vòng lặp 1000 lần, giờ chỉ 1 phép tính. Đây gọi là code số 4:
#include <bits/stdc++.h>
using namespace std;
bool isPrime(long long x){
for(long long i = 2; i * i <= x; ++i){
if(x % i == 0){
return false;
}
}
return x >= 2;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector<long long> a(n + 1);
for(int i = 1; i <= n; ++i){
cin >> a[i];
}
vector<bool> b(n + 1);
long long Max = a[2];
int L = 2;
if(isPrime(L)){
b[L] = true;
long long sum = a[L];
Max = max(Max, sum);
for(int R = L + 1; R <= n; ++R){
sum += a[R];
if(isPrime(R)){
Max = max(Max, sum);
b[R] = true;
}
else{
b[R] = false;
}
}
}
for(L++; L <= n; ++L){
if(b[L] == true){
long long sum = a[L];
Max = max(Max, sum);
for(int R = L + 1; R <= n; ++R){
sum += a[R];
if(b[R] == true){
Max = max(Max, sum);
}
}
}
}
cout << Max;
return 0;
}
import sys
input = sys.stdin.readline
def is_prime(x):
if x < 2:
return False
i = 2
while i * i <= x:
if x % i == 0:
return False
i += 1
return True
n = int(input())
a = [0] + list(map(int, input().split()))
b = [False] * (n + 1)
Max = a[2]
L = 2
if is_prime(L):
b[L] = True
total = a[L]
Max = max(Max, total)
for R in range(L + 1, n + 1):
total += a[R]
if is_prime(R):
Max = max(Max, total)
b[R] = True
else:
b[R] = False
for L in range(3, n + 1):
if b[L]:
total = a[L]
Max = max(Max, total)
for R in range(L + 1, n + 1):
total += a[R]
if b[R]:
Max = max(Max, total)
print(Max)
C++▶ Chạy tay từng dòng codeCách 4: xử lý riêng L = 2 và ghi nhớ kết quả nguyên tố vào mảng b, các L sau chỉ tra b – O(N²).
Dữ liệu mẫu:
1#include <bits/stdc++.h>
2usingnamespace std;
3
4bool isPrime(longlong x){
5for(longlong i = 2; i * i <= x; ++i){
6if(x % i == 0){
7returnfalse;
8 }
9 }
10return x >= 2;
11}
12
13int main(){
14ios::sync_with_stdio(0);
15cin.tie(0);
16int n;
17cin >> n;
18vector<longlong> a(n + 1);
19for(int i = 1; i <= n; ++i){
20cin >> a[i];
21 }
22vector<bool> b(n + 1);
23longlong Max = a[2];
24int L = 2;
25if(isPrime(L)){
26 b[L] = true;
27longlong sum = a[L];
28 Max = max(Max, sum);
29for(int R = L + 1; R <= n; ++R){
30 sum += a[R];
31if(isPrime(R)){
32 Max = max(Max, sum);
33 b[R] = true;
34 }
35else{
36 b[R] = false;
37 }
38 }
39 }
40for(L++; L <= n; ++L){
41if(b[L] == true){
42longlong sum = a[L];
43 Max = max(Max, sum);
44for(int R = L + 1; R <= n; ++R){
45 sum += a[R];
46if(b[R] == true){
47 Max = max(Max, sum);
48 }
49 }
50 }
51 }
52cout << Max;
53return0;
54}
Đánh giá độ phức tạp: không gian $O(2N) = O(N)$ (mảng $a$ và $b$). Thời gian: $O(N)$ đọc mảng + $O(N\sqrt{N})$ dựng mảng $b$ + $O(N^2)$ cho 2 vòng lặp lồng nhau ⇒ $O(N^2)$. Với $N = 10^6$: $10^{12} / 10^8 = 10^4$ giây ⇔ gần 3 giờ. Từ 115 ngày xuống gần 3 giờ hehe. Khi nộp lên thì code số 3 chỉ Accepted 14 test đầu, code số 4 Accepted thêm test 15.
Không gian$O(N)$
Thời gian$O(N^2)$
Cách 5Gọn code: dựng b ngay khi đọc input
Code số 4 nếu các bạn thấy dài dòng thì có thể rút gọn: bản chất ta chỉ cần lặp các giá trị từ 1 đến $N$ rồi cập nhật kết quả vào mảng b, rồi xử lý chính lặp từ $L = 2$ như code số 3. Gọn hơn nữa: vòng lặp đọc input for i từ 1 đến $N$ có sẵn rồi, tận dụng nó làm luôn bước kiểm tra nguyên tố. Đây gọi là code số 5:
#include <bits/stdc++.h>
using namespace std;
bool isPrime(long long x){
for(long long i = 2; i * i <= x; ++i){
if(x % i == 0){
return false;
}
}
return x >= 2;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector<long long> a(n + 1);
vector<bool> b(n + 1);
for(int i = 1; i <= n; ++i){
cin >> a[i];
b[i] = isPrime(i);
}
long long Max = a[2];
for(int L = 2; L <= n; ++L){
if(b[L] == true){
long long sum = a[L];
Max = max(Max, sum);
for(int R = L + 1; R <= n; ++R){
sum += a[R];
if(b[R] == true){
Max = max(Max, sum);
}
}
}
}
cout << Max;
return 0;
}
import sys
input = sys.stdin.readline
def is_prime(x):
if x < 2:
return False
i = 2
while i * i <= x:
if x % i == 0:
return False
i += 1
return True
n = int(input())
a = [0] + list(map(int, input().split())) # 1-based indexing
b = [False] * (n + 1)
for i in range(1, n + 1):
b[i] = is_prime(i)
Max = a[2]
for L in range(2, n + 1):
if b[L]:
total = a[L]
Max = max(Max, total)
for R in range(L + 1, n + 1):
total += a[R]
if b[R]:
Max = max(Max, total)
print(Max)
C++▶ Chạy tay từng dòng codeCách 5: dựng mảng b ngay trong vòng đọc input (b[i] = isPrime(i)), rồi lặp như cách 3 nhưng tra b – O(N²).
Dữ liệu mẫu:
1#include <bits/stdc++.h>
2usingnamespace std;
3
4bool isPrime(longlong x){
5for(longlong i = 2; i * i <= x; ++i){
6if(x % i == 0){
7returnfalse;
8 }
9 }
10return x >= 2;
11}
12
13int main(){
14ios::sync_with_stdio(0);
15cin.tie(0);
16int n;
17cin >> n;
18vector<longlong> a(n + 1);
19vector<bool> b(n + 1);
20for(int i = 1; i <= n; ++i){
21cin >> a[i];
22 b[i] = isPrime(i);
23 }
24longlong Max = a[2];
25for(int L = 2; L <= n; ++L){
26if(b[L] == true){
27longlong sum = a[L];
28 Max = max(Max, sum);
29for(int R = L + 1; R <= n; ++R){
30 sum += a[R];
31if(b[R] == true){
32 Max = max(Max, sum);
33 }
34 }
35 }
36 }
37cout << Max;
38return0;
39}
Dòng b[i] = isPrime(i); là gán trực tiếp kết quả true/false trả về từ hàm vào b[i]. Lúc này không chỉ gọn code hơn mà nếu so thời gian chạy ở 15 test Accepted với code số 4 sẽ thấy nhanh hơn hẳn. Tuy nhiên độ phức tạp vẫn y như code số 4.
Cách 6Sàng nguyên tố Eratosthenes
Để dựng mảng b mà gọi hàm kiểm tra cho từng giá trị thì tốn $O(N\sqrt{N})$. Có cách tốt hơn là dùng thuật toán Sàng Nguyên Tố Eratosthenes (Sieve of Eratosthenes), độ phức tạp chỉ $O(N \log \log N)$. Bạn nào chưa biết có thể đọc bài trên GeeksforGeeks hoặc tiếng Việt trên VNOI Wiki. Ý tưởng: ban đầu coi mọi số là nguyên tố; với mỗi $p$ còn đánh dấu nguyên tố mà $p \cdot p \le N$, gạch hết các bội $p^2, p^2 + p, p^2 + 2p, \ldots$ Áp dụng vào ta có code số 6:
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector<long long> a(n + 1);
for(int i = 1; i <= n; ++i){
cin >> a[i];
}
vector<bool> b(n + 1, true);
for (int p = 2; p * p <= n; ++p) {
if (b[p] == true) {
for (int i = p * p; i <= n; i += p)
b[i] = false;
}
}
long long Max = a[2];
for(int L = 2; L <= n; ++L){
if(b[L] == true){
long long sum = a[L];
Max = max(Max, sum);
for(int R = L + 1; R <= n; ++R){
sum += a[R];
if(b[R] == true){
Max = max(Max, sum);
}
}
}
}
cout << Max;
return 0;
}
import sys
input = sys.stdin.readline
n = int(input())
a = [0] + list(map(int, input().split()))
b = [True] * (n + 1)
b[0] = b[1] = False
p = 2
while p * p <= n:
if b[p]:
for i in range(p * p, n + 1, p):
b[i] = False
p += 1
Max = a[2]
for L in range(2, n + 1):
if b[L]:
total = a[L]
Max = max(Max, total)
for R in range(L + 1, n + 1):
total += a[R]
if b[R]:
Max = max(Max, total)
print(Max)
C++▶ Chạy tay từng dòng codeCách 6: dựng mảng b bằng sàng Eratosthenes O(N log log N), phần chính vẫn O(N²).
Dữ liệu mẫu:
1#include <bits/stdc++.h>
2usingnamespace std;
3
4int main(){
5ios::sync_with_stdio(0);
6cin.tie(0);
7int n;
8cin >> n;
9vector<longlong> a(n + 1);
10for(int i = 1; i <= n; ++i){
11cin >> a[i];
12 }
13vector<bool> b(n + 1, true);
14for (int p = 2; p * p <= n; ++p) {
15if (b[p] == true) {
16for (int i = p * p; i <= n; i += p)
17 b[i] = false;
18 }
19 }
20longlong Max = a[2];
21for(int L = 2; L <= n; ++L){
22if(b[L] == true){
23longlong sum = a[L];
24 Max = max(Max, sum);
25for(int R = L + 1; R <= n; ++R){
26 sum += a[R];
27if(b[R] == true){
28 Max = max(Max, sum);
29 }
30 }
31 }
32 }
33cout << Max;
34return0;
35}
vector<bool> b(n + 1, true): khởi tạo mảng $b$ có $n + 1$ phần tử mặc định đều là true. (Code C++ không gạch b[0], b[1] nhưng cũng không sao, vì $L$ bắt đầu từ 2 và $R$ từ $L + 1$ nên không bao giờ đụng tới 2 ô này.)
Độ phức tạp: không gian $O(N)$; thời gian $O(N) + O(N \log \log N) + O(N^2)$ $= O(N^2)$, không đổi so với code số 5 nhưng rõ là có tối ưu hơn nếu nộp rồi xem cột thời gian chạy.
Chia sẻ thêm về sàng
Với giới hạn 1 giây thì sàng nguyên tố chỉ áp dụng được nếu phạm vi cần sàng cỡ $10^7$ trở xuống. Nếu cần sàng đến $10^8$ thì nội bước khởi tạo mảng toàn true đã tốn $10^8$ lần lặp, chạm ngưỡng rồi, chưa kể bước sàng chính còn $O(N \log \log N)$ nữa, bảo đảm TLE. Bài này $N \le 10^6$ nên rất hợp lý để áp dụng.
Cách 7Prefix Sum (mảng cộng dồn)
Ở code số 6, phần xử lý chính vẫn còn rườm rà khi biến sum cứ phải cộng dồn lặp đi lặp lại nhiều giá trị trùng nhau: khi $L = 2$ cộng các giá trị từ 2 đến 6, khi $L = 3$ lại cộng từ 3 đến 6, cứ thế. Ta áp dụng kỹ thuật Prefix Sum (mảng cộng dồn), đây chính là hướng mở đường để tìm ra cách tối ưu nhất. Dạng kinh điển nhất của Prefix Sum chính là tính tổng đoạn liên tục từ $L$ đến $R$.
Với dãy ví dụ 9 5 -2 6 -1 1 (vị trí tính từ 1), mảng cộng dồn $P$:
Tổng các phần tử từ $L$ đến $R$ giờ chỉ cần 1 phép tính: $\boxed{P[R] - P[L-1]}$. Ví dụ $L = 2, R = 5$: $P[5] - P[1] = 17 - 9 = 8$, đúng bằng $5 + (-2) + 6 + (-1) = 8$.
a19253-2465-161
P0019214312418517618
Tổng đoạn L = 2 … R = 5 = P[5] = 17 − P[1] = 9 = 8 = 5 + (−2) + 6 + (−1)
Tại sao? Kẻ trục số ra sẽ thấy: $P[R]$ là tổng từ vị trí 1 đến $R$; nếu lấy $P[R] - P[L]$ thì được tổng từ $L + 1$ đến $R$. Ta cần từ $L$ đến $R$ nên phải trừ cho $P[L - 1]$. Quy luật đơn giản vậy thôi. Mình phát triển lên từ code số 6 thành code số 7:
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector<bool> b(n + 1, true);
for (int p = 2; p * p <= n; ++p) {
if (b[p] == true) {
for (int i = p * p; i <= n; i += p)
b[i] = false;
}
}
vector<long long> a(n + 1);
a[0] = 0;
for(int i = 1; i <= n; ++i){
cin >> a[i];
a[i] += a[i - 1];
}
long long Max = a[2] - a[1];
for(int L = 2; L <= n; ++L){
if(b[L] == true){
for(int R = L; R <= n; ++R){
if(b[R] == true){
Max = max(Max, a[R] - a[L - 1]);
}
}
}
}
cout << Max;
return 0;
}
import sys
input = sys.stdin.readline
n = int(input())
b = [True] * (n + 1)
b[0] = b[1] = False
p = 2
while p * p <= n:
if b[p]:
for i in range(p * p, n + 1, p):
b[i] = False
p += 1
a = [0] * (n + 1)
nums = list(map(int, input().split()))
for i in range(1, n + 1):
a[i] = a[i - 1] + nums[i - 1]
Max = a[2] - a[1]
for L in range(2, n + 1):
if b[L]:
for R in range(L, n + 1):
if b[R]:
Max = max(Max, a[R] - a[L - 1])
print(Max)
C++▶ Chạy tay từng dòng codeCách 7: sàng + biến a thành mảng cộng dồn, tổng đoạn = a[R] − a[L−1] trong O(1); vẫn 2 vòng lặp O(N²).
Dữ liệu mẫu:
1#include <bits/stdc++.h>
2usingnamespace std;
3
4int main(){
5ios::sync_with_stdio(0);
6cin.tie(0);
7int n;
8cin >> n;
9vector<bool> b(n + 1, true);
10for (int p = 2; p * p <= n; ++p) {
11if (b[p] == true) {
12for (int i = p * p; i <= n; i += p)
13 b[i] = false;
14 }
15 }
16vector<longlong> a(n + 1);
17 a[0] = 0;
18for(int i = 1; i <= n; ++i){
19cin >> a[i];
20 a[i] += a[i - 1];
21 }
22longlong Max = a[2] - a[1];
23for(int L = 2; L <= n; ++L){
24if(b[L] == true){
25for(int R = L; R <= n; ++R){
26if(b[R] == true){
27 Max = max(Max, a[R] - a[L - 1]);
28 }
29 }
30 }
31 }
32cout << Max;
33return0;
34}
Giải thích: mảng $P$ là để các bạn dễ hình dung, thực tế mình biến luôn mảng a thành mảng cộng dồn: khởi tạo a[0] = 0, mỗi a[i] đọc vào xong thì cộng thêm a[i - 1]. Nhớ phải có a[0] = 0 vì khi $i = 1$ thì a[1] += a[0]. Còn Max ban đầu là đoạn $L = R = 2$ nên giờ là a[2] - a[1]. Sau khi xác định $L, R$ là số nguyên tố chỉ cần so sánh Max với a[R] - a[L - 1], ngắn gọn hơn hẳn.
Độ phức tạp vẫn y như code số 6: không gian $O(N)$, thời gian $O(N^2)$. Prefix Sum chỉ gọn code thêm một chút nhưng nó mở đường cho cách làm tối ưu nhất.
Cách 8Prefix Sum + Min – O(N log log N) – AC
Rồi thì giờ sẽ là cách làm tối ưu nhất để giải quyết trọn vẹn bài này đây các bạn. Hãy nhìn kỹ vấn đề: ta đang cần tìm 2 vị trí $L \le R$ đều nguyên tố sao cho $a[R] - a[L - 1]$ là lớn nhất (với $a$ là mảng cộng dồn). Code số 7 dùng 2 vòng lặp lồng nhau nên $O(N^2)$, trong khi bản chất chỉ cần 1 vòng lặp $O(N)$ là được.
Nếu bí ý tưởng thì mình gợi ý: mình đã từng hướng dẫn giải bài tìm 2 vị trí $i < j$ sao cho $a[j] - a[i]$ lớn nhất. Tư tưởng đơn giản là: để $a[R] - a[L - 1]$ lớn nhất thì phải làm sao để $a[L - 1]$ nhỏ nhất. Vậy nên cứ với mỗi vị trí $R$ hợp lệ (là số nguyên tố), ta lấy giá trị nhỏ nhất của $a[L - 1]$ trong tất cả các $L \le R$ hợp lệ, rồi $a[R]$ trừ cho giá trị nhỏ nhất đó, so sánh với Max và cập nhật lại.
Em nhập dãy rồi bấm Tiếp để xem Min và Max được cập nhật thế nào khi $R$ chạy:
Ví dụ nhanh:
Source code để các bạn tham khảo, đây gọi là code số 8:
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector<bool> b(n + 1, true);
for (int p = 2; p * p <= n; ++p) {
if (b[p] == true) {
for (int i = p * p; i <= n; i += p)
b[i] = false;
}
}
vector<long long> a(n + 1);
a[0] = 0;
for(int i = 1; i <= n; ++i){
cin >> a[i];
a[i] += a[i - 1];
}
long long Max = a[2] - a[1];
long long Min = a[1];
for(int R = 3; R <= n; ++R){
if(b[R] == true){
Min = min(Min, a[R - 1]);
Max = max(Max, a[R] - Min);
}
}
cout << Max;
return 0;
}
import sys
input = sys.stdin.readline
n = int(input())
b = [True] * (n + 1)
b[0] = b[1] = False
for p in range(2, int(n ** 0.5) + 1):
if b[p]:
for i in range(p * p, n + 1, p):
b[i] = False
a = [0] * (n + 1)
nums = list(map(int, input().split()))
for i in range(1, n + 1):
a[i] = a[i - 1] + nums[i - 1]
Max = a[2] - a[1]
Min = a[1]
for R in range(3, n + 1):
if b[R]:
Min = min(Min, a[R - 1])
Max = max(Max, a[R] - Min)
print(Max)
C++▶ Chạy tay từng dòng codeCách 8: với mỗi R nguyên tố, lấy a[R] trừ Min của các a[L−1] – chỉ 1 vòng lặp, O(N log log N).
Dữ liệu mẫu:
1#include <bits/stdc++.h>
2usingnamespace std;
3
4int main(){
5ios::sync_with_stdio(0);
6cin.tie(0);
7int n;
8cin >> n;
9vector<bool> b(n + 1, true);
10for (int p = 2; p * p <= n; ++p) {
11if (b[p] == true) {
12for (int i = p * p; i <= n; i += p)
13 b[i] = false;
14 }
15 }
16vector<longlong> a(n + 1);
17 a[0] = 0;
18for(int i = 1; i <= n; ++i){
19cin >> a[i];
20 a[i] += a[i - 1];
21 }
22longlong Max = a[2] - a[1];
23longlong Min = a[1];
24for(int R = 3; R <= n; ++R){
25if(b[R] == true){
26 Min = min(Min, a[R - 1]);
27 Max = max(Max, a[R] - Min);
28 }
29 }
30cout << Max;
31return0;
32}
Giải thích:Max như code số 7. Min lưu giá trị a[L - 1] nhỏ nhất trong tất cả các vị trí $L \le R$ hợp lệ. Ban đầu Min = a[1] vì $L$ hợp lệ đầu tiên là 2 nên $a[L-1] = a[1]$. Rồi $R$ chạy từ 3 đến $N$; với mỗi $R$ nguyên tố thì $R$ đó cũng chính là một $L$ hợp lệ mới (vì cho phép $L = R$), nên ta cập nhật Min với a[R - 1] trước, rồi tính a[R] - Min để cập nhật Max.
Đánh giá độ phức tạp: không gian $O(N)$; thời gian $O(N \log \log N)$ của bước sàng + $O(N)$ đọc dữ liệu + $O(N)$ tìm Max ⇒ $O(N \log \log N)$. Với $N = 10^6$ chỉ lặp cỡ $5 \cdot 10^6$ lần, ít hơn ngưỡng cả 20 lần, khoảng 0.05 giây là ra kết quả và nộp bài sẽ Accepted. Chỉ sửa một chút mà từ gần 3 tiếng xuống còn chớp mắt cái là xong hehe.
Không gian$O(N)$
Thời gian$O(N \log \log N)$
Cách 9Không cần mảng a – gộp đọc và xử lý
Đến đây thì cũng được rồi nhưng mình nói thêm luôn: ở code số 8 ta có thể không cần mảng a để chứa input, chỉ cần mảng b của sàng nguyên tố, và gộp quá trình đọc input với quá trình tìm Max vào 1 vòng lặp duy nhất:
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector<bool> b(n + 1, true);
for (int p = 2; p * p <= n; ++p) {
if (b[p] == true) {
for (int i = p * p; i <= n; i += p)
b[i] = false;
}
}
long long x, sum, Min, Max;
cin >> x;
Min = x;
sum = x;
cin >> x;
Max = x;
sum += x;
for(int R = 3; R <= n; ++R){
cin >> x;
sum += x;
if(b[R] == true){
Min = min(Min, sum - x);
Max = max(Max, sum - Min);
}
}
cout << Max;
return 0;
}
import sys
data = sys.stdin.buffer.read().split()
n = int(data[0])
b = [True] * (n + 1)
b[0] = b[1] = False
for p in range(2, int(n ** 0.5) + 1):
if b[p]:
for i in range(p * p, n + 1, p):
b[i] = False
# n số nằm trên cùng 1 dòng nên đọc hết rồi lấy lần lượt từng số
it = iter(data[1:])
x = int(next(it))
Min = x
sum_ = x
x = int(next(it))
Max = x
sum_ += x
for R in range(3, n + 1):
x = int(next(it))
sum_ += x
if b[R]:
Min = min(Min, sum_ - x)
Max = max(Max, sum_ - Min)
print(Max)
C++▶ Chạy tay từng dòng codeCách 9: như cách 8 nhưng không cần mảng a – sum đóng vai a[R], sum − x đóng vai a[R−1].
Dữ liệu mẫu:
1#include <bits/stdc++.h>
2usingnamespace std;
3
4int main(){
5ios::sync_with_stdio(0);
6cin.tie(0);
7int n;
8cin >> n;
9vector<bool> b(n + 1, true);
10for (int p = 2; p * p <= n; ++p) {
11if (b[p] == true) {
12for (int i = p * p; i <= n; i += p)
13 b[i] = false;
14 }
15 }
16longlong x, sum, Min, Max;
17cin >> x;
18 Min = x;
19 sum = x;
20cin >> x;
21 Max = x;
22 sum += x;
23for(int R = 3; R <= n; ++R){
24cin >> x;
25 sum += x;
26if(b[R] == true){
27 Min = min(Min, sum - x);
28 Max = max(Max, sum - Min);
29 }
30 }
31cout << Max;
32return0;
33}
Đọc giá trị đầu tiên vào x thì gán luôn cho Min (tương đương Min = a[1] ở code số 8) và cho sum.
Đọc giá trị thứ 2 vào x thì gán qua Max (tương đương a[2] - a[1]) và cộng vào sum.
sum liên tục cộng các giá trị đọc vào nên tại vị trí $R$ thì sum chính là a[R] của code số 8; còn sum - x (trừ đi giá trị vừa đọc) chính là a[R - 1]. Vậy Min = min(Min, sum - x) và Max = max(Max, sum - Min).
Mọi thứ cứ như vậy thôi các bạn dễ hình dung hen. Bớt được 1 mảng $N$ phần tử và 1 vòng lặp.
Không gian$O(N)$ (chỉ mảng b)
Thời gian$O(N \log \log N)$
Tổng kếtTừ 317 năm xuống 0.05 giây
Đến đây các bạn thấy việc luyện tư duy giải thuật quan trọng chứ? Trong trường hợp xấu nhất $N = 10^6$: từ $O(N^3)$ cần 317 năm, xuống $O(N^2\sqrt{N})$ còn 115 ngày, xuống $O(N^2)$ còn gần 3 giờ, rồi cuối cùng $O(N \log \log N)$ chỉ cần 0.05 giây. Vậy là chúng ta chính thức kết thúc bài này với tổng cộng 9 cách làm tối ưu từ thấp nhất lên cao nhất nha các bạn 😊
Ghi chú của mình: code C++ và Python của cả 9 cách là của anh. Riêng bản Python của cách 9, anh đọc mỗi số bằng int(input()) nhưng đề cho cả $n$ số trên cùng 1 dòng nên sẽ bị lỗi, mình sửa lại thành đọc hết dữ liệu rồi lấy lần lượt từng số. Tất cả 18 bản đã được kiểm tra với 250 bộ test ngẫu nhiên ($2 \le n \le 40$, có toàn số âm, giá trị đến $10^6$) so với code vét cạn trực tiếp: khớp 100%. Thời gian đo trên máy mình: các cách 1–3 với $n = 100$ dưới 0.07 giây; các cách 4–7 với $n = 3000$ dưới 0.03 giây (C++), khoảng 0.2–0.35 giây (Python); cách 8, 9 với $n = 10^6$ khoảng 0.15–0.22 giây (C++, phần lớn là đọc input), Python khoảng 1.5–2 giây.
Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇
