Đoạn Đẹp (Duyên Hải 2021)
Đề 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$.
6
9 5 -2 6 -1 18Lờ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é:
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.
Nộp bài trên CLUE OJBạ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.
Nộp bài trên CodeforcesBà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.
Lộ trình lời giải, bấm vào từng phần để nhảy tới:
Trước tiênNgưỡng 1 giây là bao nhiêu phép toán?
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.
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.
| 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)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
vectorthay 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ềtruenế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ệni * i <= x⇔i <= sqrt(x)nhưng nên dùngi * i <= xvì hàmsqrtcó 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ôngreturn 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ênreturn x >= 2xử lý gọn cả 2 trường hợp. - Vòng
for Lbắt đầu từ 2 (vị trí hợp lệ đầu tiên). Vòngfor Rbắ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.
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)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)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.
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)Đá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.
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)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)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.
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$.
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)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:
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)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.
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 giá trị đầu tiên vào
xthì gán luôn choMin(tương đươngMin = a[1]ở code số 8) và chosum. - Đọc giá trị thứ 2 vào
xthì gán quaMax(tương đươnga[2] - a[1]) và cộng vàosum. sumliên tục cộng các giá trị đọc vào nên tại vị trí $R$ thìsumchính làa[R]của code số 8; cònsum - x(trừ đi giá trị vừa đọc) chính làa[R - 1]. VậyMin = 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.
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 😊
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.
Nhận xét
Đăng nhận xét