Hướng dẫn giải của [2627 KS1] DUONGDEP
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 liên tiếp dài nhất có trung bình cộng bằng ~K~ (nhiều đáp án thì lấy ~u~ nhỏ nhất), hay tổng các ~a_i - K~ trên đoạn bằng 0.
Sub 1: Vét cạn — ~O(N^2)~, dùng khi ~N \le 5000~
Thử mọi đoạn ~[u, v]~ với tổng tiền tố, đoạn thỏa nếu tổng bằng ~K \cdot (v-u+1)~ (so sánh nguyên, không chia). Duyệt ~u~ tăng dần và chỉ cập nhật khi dài hơn hẳn nên được ~u~ nhỏ nhất. Nếu chỉ nộp sub này: đúng 32/40 test.
Sub 2: Tổng tiền tố + bảng băm/map — ~O(N \log N)~
Đặt ~S_j = \sum (a_i - K)~. Đoạn ~(i, j]~ thỏa khi ~S_i = S_j~. Với mỗi giá trị ghi lại vị trí xuất hiện đầu tiên; tại ~j~ lấy độ dài ~j - i~ nếu đã gặp. Lưu ý dùng ~long long~ (tổng tới ~10^{14}~), cập nhật khi dài hơn hoặc bằng nhưng ~u~ nhỏ hơn, và in 0 nếu không có đoạn nào. Nếu chỉ nộp sub này: đúng 40/40 test.
Chương trình hoàn chỉnh
main đọc dữ liệu; ~N \le 5000~ gọi sub1, lớn hơn gọi sub2. Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước.
#include <bits/stdc++.h>
using namespace std;
int n;
long long K, a[100005];
// Sub 1: thử mọi đoạn [u, u+len-1], tính tổng cộng dồn — O(n^2), dùng khi n <= 5000
void sub1() {
vector<long long> p(n + 1, 0);
for (int i = 1; i <= n; i++) p[i] = p[i - 1] + a[i];
int bu = 0, bl = 0;
for (int u = 1; u <= n; u++)
for (int v = u; v <= n; v++)
// trung bình = K <=> tổng = K * độ dài
if (p[v] - p[u - 1] == K * (v - u + 1) && v - u + 1 > bl) { bl = v - u + 1; bu = u; }
if (bl == 0) cout << 0 << "\n";
else cout << bu << " " << bl << "\n";
}
// Sub 2: đặt b_i = a_i - K, cần đoạn có tổng b = 0, tức hai tổng tiền tố bằng nhau — O(n log n)
void sub2() {
map<long long, int> first;
long long s = 0;
first[0] = 0;
int bu = 0, bl = 0;
for (int j = 1; j <= n; j++) {
s += a[j] - K;
auto it = first.find(s);
if (it == first.end()) first[s] = j;
else {
int u = it->second + 1, len = j - it->second;
if (len > bl || (len == bl && u < bu)) { bl = len; bu = u; }
}
}
if (bl == 0) cout << 0 << "\n";
else cout << bu << " " << bl << "\n";
}
int main() {
freopen("DUONGDEP.INP", "r", stdin);
freopen("DUONGDEP.OUT", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> K;
for (int i = 1; i <= n; i++) cin >> a[i];
if (n <= 5000) sub1();
else sub2();
return 0;
}
Bình luận