Hướng dẫn giải của [TKNP] ESEQ
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
Đếm cặp chỉ số i < j sao cho tổng tiền tố a1 + ... + ai bằng tổng hậu tố aj + ... + an. Gọi Pi là tổng tiền tố và S = Pn là tổng cả dãy, thì aj + ... + an = S - P_{j-1}.
Sub 1: Vét cạn — ~O(n^2)~, dùng khi ~n \le 5000~
Duyệt mọi cặp (i, j) với i < j, kiểm tra Pi = S - P{j-1}. Nếu chỉ nộp sub này: đúng 13/20 test (7 test còn lại có n lớn, chạy quá giờ).
Sub 2 (đầy đủ): Dùng bảng đếm — ~O(n \log n)~
Điều kiện Pi = S - P{j-1} tương đương Pi + Pk = S với k = j - 1, và i \le k. Duyệt k tăng dần: trước khi hỏi, thêm Pk vào bảng đếm (để tính cả trường hợp i = k), rồi cộng số lần xuất hiện của S - Pk trong bảng.
Bẫy: đáp số có thể lên tới khoảng n^2 / 2 \approx 5 \cdot 10^9, dùng long long. Các a_i có thể âm nên tổng tiền tố dùng long long.
Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Hàm main đọc dãy và tính tiền tố. Nếu n \le 5000 gọi sub1, ngược lại 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 a[100005]; // a[1..n]
long long P[100005]; // P[i] = a1 + ... + ai
long long S; // tong ca day = P[n]
// Sub 1: vet can O(n^2) - thu moi cap (i, j), kiem tra a1+...+ai = aj+...+an. Dung khi n <= 5000.
void sub1() {
long long cnt = 0;
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++) {
long long left = P[i]; // a1 + ... + ai
long long right = S - P[j - 1]; // aj + ... + an
if (left == right) cnt++;
}
cout << cnt << "\n";
}
// Sub 2: day du O(n log n).
// Dieu kien: P[i] = S - P[j-1] <=> P[i] + P[k] = S voi k = j-1, va i <= k.
// Duyet k tang dan, them P[k] vao map truoc, roi dem so i da them ma P[i] = S - P[k].
void sub2() {
map<long long, long long> freq;
long long cnt = 0;
for (int k = 1; k <= n - 1; k++) {
freq[P[k]]++; // them i = k (i <= k)
auto it = freq.find(S - P[k]);
if (it != freq.end()) cnt += it->second;
}
cout << cnt << "\n";
}
int main() {
freopen("eseq.inp", "r", stdin);
freopen("eseq.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
P[0] = 0;
for (int i = 1; i <= n; i++) {
cin >> a[i];
P[i] = P[i - 1] + a[i];
}
S = P[n];
if (n <= 5000) sub1(); // n nho: vet can cho chac
else sub2();
return 0;
}
Bình luận