Hướng dẫn giải của [200 đề thầy Đức] Bài 169: Dãy con tăng liền kề dài nhất và có tổng nguyên tố lớn nhất
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Tìm đoạn con liên tiếp tăng nghiêm ngặt dài nhất. Nếu có nhiều đoạn dài nhất thì chọn đoạn có tổng các số nguyên tố lớn nhất. In độ dài và tổng số nguyên tố của đoạn đó.
Sub 1: Vét cạn — ~O(n^3)~, dùng khi ~n \le 200~
Thử mọi đoạn ~[L, R]~. Nếu đoạn không tăng nghiêm ngặt thì các đoạn dài hơn cũng không tăng, nên dừng sớm. Với đoạn hợp lệ, cộng các số nguyên tố trong đoạn, giữ đoạn có độ dài lớn nhất, hòa thì giữ tổng lớn hơn. Nếu chỉ nộp sub này: đúng 21/21 test.
Sub 2: Quét một lần — ~O(n)~
Duyệt dãy một lần. Mỗi khi ~a_i \le a_{i-1}~ thì bắt đầu một đoạn mới. Giữ độ dài và tổng số nguyên tố của đoạn hiện tại rồi cập nhật đáp án. Bẫy: tổng số nguyên tố có thể lên tới ~10^{11}~ nên dùng kiểu long long; cần sàng số nguyên tố đến ~10^6~. Nếu chỉ nộp sub này: đúng 21/21 test.
Chương trình hoàn chỉnh
main đọc ~T~ bộ dữ liệu. Với mỗi bộ, nếu ~n \le 200~ thì gọi sub1, ngược lại gọi sub2. Sub 2 đúng với mọi ~n~ nên sub 1 chỉ là phương án dự phòng cho dữ liệu nhỏ.
#include <bits/stdc++.h>
using namespace std;
const int MAXV = 1000000;
bool isPrime[MAXV + 1]; // sàng số nguyên tố đến 10^6
int n;
long long a[100005]; // dãy A (đánh số từ 1)
// Sub 1: vét cạn. Thử mọi đoạn [L, R], kiểm tra tăng liền kề rồi tính tổng số nguyên tố.
void sub1() {
int best = 0;
long long bestSum = 0;
for (int L = 1; L <= n; L++)
for (int R = L; R <= n; R++) {
bool inc = true;
for (int i = L + 1; i <= R && inc; i++)
if (a[i] <= a[i - 1]) inc = false;
if (!inc) break; // đoạn dài hơn cũng không tăng được nữa
long long s = 0;
for (int i = L; i <= R; i++)
if (isPrime[a[i]]) s += a[i];
int len = R - L + 1;
if (len > best || (len == best && s > bestSum)) {
best = len;
bestSum = s;
}
}
printf("%d %lld\n", best, bestSum);
}
// Sub 2: quét một lần O(n). Mỗi dãy tăng liền kề là một đoạn; giữ độ dài và tổng số nguyên tố.
void sub2() {
int best = 0, len = 0;
long long bestSum = 0, s = 0;
for (int i = 1; i <= n; i++) {
if (i == 1 || a[i] <= a[i - 1]) { // bắt đầu một dãy tăng mới
len = 0;
s = 0;
}
len++;
if (isPrime[a[i]]) s += a[i];
if (len > best || (len == best && s > bestSum)) {
best = len;
bestSum = s;
}
}
printf("%d %lld\n", best, bestSum);
}
int main() {
fill(isPrime, isPrime + MAXV + 1, true);
isPrime[0] = isPrime[1] = false;
for (long long i = 2; i * i <= MAXV; i++)
if (isPrime[i])
for (long long j = i * i; j <= MAXV; j += i) isPrime[j] = false;
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
if (n <= 200) sub1(); // dữ liệu nhỏ: vét cạn
else sub2();
}
return 0;
}
Bình luận