Hướng dẫn giải của [2526 KSCUM_PN] Câu 3: Năng lượng
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
Chọn một đoạn liên tiếp các viên đá sao cho tích năng lượng dương (không có số 0 và số lượng số âm là số chẵn), đoạn đó dài nhất.
Sub 1: Vét cạn từng đoạn — ~O(n^2)~, dùng khi ~n \le 5000~
Với mỗi điểm đầu ~l~, duyệt điểm cuối ~r~ tăng dần và đếm số số âm cùng việc có số 0 hay không. Nếu không có số 0 và số lượng số âm chẵn thì đoạn ~[l, r]~ có tích dương, cập nhật độ dài lớn nhất.
Nếu chỉ nộp sub này: đúng 10/20 test.
Sub 2: Quy hoạch động — ~O(n)~, dùng khi mọi trường hợp còn lại
Gọi ~pos~ là độ dài đoạn dài nhất kết thúc tại vị trí hiện tại có tích dương, ~neg~ là độ dài đoạn có tích âm (0 nghĩa là chưa có). Với số dương, ~pos~ tăng 1 và ~neg~ tăng 1 nếu đang có. Với số âm, tích đảo dấu: ~pos~ mới là ~neg + 1~ và ~neg~ mới là ~pos + 1~. Với số 0 cả hai về 0. Đáp án là giá trị ~pos~ lớn nhất trong quá trình duyệt.
Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Subtask 1 (tất cả số âm, 15%) và subtask 2 (~n \le 10^3~, 50%) đều được sub 1 xử lý đúng. Subtask 3 không ràng buộc thêm được sub 2 xử lý.
Chương trình đọc ~n~ và dãy. Nếu ~n \le 5000~ thì gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
int n;
vector<long long> a;
// Sub 1: vet can O(n^2). Voi moi doan [l, r] theo doi so luong so am va co so 0 hay khong.
// Doan co tich duong khi: khong co so 0 va so so am chan. Dung khi n <= 5000
void sub1() {
int best = 0;
for (int l = 0; l < n; l++) {
int negs = 0;
bool hasZero = false;
for (int r = l; r < n; r++) {
if (a[r] == 0) hasZero = true;
if (a[r] < 0) negs++;
if (!hasZero && negs % 2 == 0) best = max(best, r - l + 1);
}
}
cout << best << "\n";
}
// Sub 2: quy hoach dong O(n).
// pos = do dai doan lon nhat ket thuc tai i co tich duong (0 = khong co),
// neg = do dai doan lon nhat ket thuc tai i co tich am (0 = khong co).
void sub2() {
int best = 0, pos = 0, neg = 0;
for (int i = 0; i < n; i++) {
if (a[i] == 0) {
pos = neg = 0;
} else if (a[i] > 0) {
// so duong nhan vao: tich dau giu nguyen dau; doan moi bat dau tu a[i] neu pos = 0
pos = pos + 1;
neg = (neg > 0) ? neg + 1 : 0;
} else {
// so am nhan vao: dao dau tich
int newPos = (neg > 0) ? neg + 1 : 0;
int newNeg = pos + 1;
pos = newPos;
neg = newNeg;
}
best = max(best, pos);
}
cout << best << "\n";
}
int main() {
freopen("CAU3.INP", "r", stdin);
freopen("CAU3.OUT", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
a.resize(n);
for (int i = 0; i < n; i++) cin >> a[i];
if (n <= 5000) sub1();
else sub2();
return 0;
}
Bình luận