Hướng dẫn giải của Đếm cặp (Đề HSG 12 Phú Thọ 2021-2022)
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
Gọi $S$ là tổng cả dãy. Nếu ba đoạn có tổng bằng nhau thì mỗi đoạn có tổng $T = S / 3$, nên $S$ phải chia hết cho 3 (nếu không thì đáp số là $0$). Gọi $Pk = a1 + \dots + ak$. Khi đó đoạn đầu có tổng $P{i-1} = T$ và đoạn giữa có tổng $Pj - P{i-1} = T$, tức $Pj = 2T$. Đoạn cuối tự động có tổng $S - Pj = T$. Bài toán trở thành đếm cặp $p < j$ với $Pp = T$, $Pj = 2T$ (với $p = i - 1$).
Sub 1: Vét cạn — ~O(n^3)~, dùng khi ~n \le 100~
Thử mọi cặp $(i, j)$ với $2 \le i \le j \le n - 1$, tính trực tiếp tổng ba đoạn rồi kiểm tra có bằng nhau không.
Nếu chỉ nộp sub này: đúng 35/50 test (15 test lớn quá giờ).
Sub 2: Tổng tiền tố — ~O(n^2)~, dùng khi ~n \le 1000~
Dùng mảng tiền tố $P$ để tính tổng mỗi đoạn trong $O(1)$, nên chỉ còn hai vòng lặp lồng nhau.
Nếu chỉ nộp sub này: đúng 40/50 test (10 test lớn quá giờ).
Sub 3: Đếm một lượt — ~O(n)~
Duyệt $j$ tăng dần, giữ cnt là số $p < j$ có $Pp = T$. Nếu $Pj = 2T$ thì cộng cnt vào đáp số. Bẫy: $S$ không chia hết cho 3 thì in $0$. Khi $T = 0$ vẫn đúng vì ta đếm cặp $p < j$.
Nếu chỉ nộp sub này: đúng 50/50 test.
Chương trình hoàn chỉnh
main đọc dữ liệu từ file count.inp, ghi ra count.out. Nếu $n \le 100$ thì gọi sub 1, nếu $n \le 1000$ thì gọi sub 2, còn lại gọi sub 3.
#include <bits/stdc++.h>
using namespace std;
int n;
vector<long long> a; // a[1..n]
vector<long long> P; // P[k] = a_1 + ... + a_k
// Sub 1: vet can O(n^3), dung khi n <= 100.
// Thu moi cap (i, j), tinh truc tiep tong ba doan roi kiem tra bang nhau.
void sub1() {
long long cnt = 0;
for (int i = 2; i <= n - 1; i++)
for (int j = i; j <= n - 1; j++) {
long long s1 = 0, s2 = 0, s3 = 0;
for (int k = 1; k <= i - 1; k++) s1 += a[k];
for (int k = i; k <= j; k++) s2 += a[k];
for (int k = j + 1; k <= n; k++) s3 += a[k];
if (s1 == s2 && s2 == s3) cnt++;
}
cout << cnt << "\n";
}
// Sub 2: O(n^2) dung tong tien to P, dung khi n <= 1000.
void sub2() {
long long S = P[n];
long long cnt = 0;
for (int i = 2; i <= n - 1; i++)
for (int j = i; j <= n - 1; j++) {
long long s1 = P[i - 1];
long long s2 = P[j] - P[i - 1];
long long s3 = S - P[j];
if (s1 == s2 && s2 == s3) cnt++;
}
cout << cnt << "\n";
}
// Sub 3: O(n) day du.
// Goi T = S / 3. Doan 1 co tong P[i-1] = T, va P[j] = 2T de doan 3 co tong T.
// Dem cap (p, j) voi p = i - 1 < j, P[p] = T, P[j] = 2T.
void sub3() {
long long S = P[n];
if (S % 3 != 0) { // khong chia deu duoc
cout << 0 << "\n";
return;
}
long long T = S / 3;
long long cnt = 0, ans = 0;
for (int j = 2; j <= n - 1; j++) {
if (P[j - 1] == T) cnt++; // them p = j - 1 (chi so cat thu nhat)
if (P[j] == 2 * T) ans += cnt; // moi p truoc j deu tao duoc mot cap
}
cout << ans << "\n";
}
int main() {
freopen("count.inp", "r", stdin);
freopen("count.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
a.assign(n + 1, 0);
P.assign(n + 1, 0);
for (int i = 1; i <= n; i++) {
cin >> a[i];
P[i] = P[i - 1] + a[i];
}
if (n <= 100) sub1();
else if (n <= 1000) sub2();
else sub3();
return 0;
}
Bình luận