Hướng dẫn giải của [Beginner Free Contest 07] COUNT
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
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.
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
Yêu cầu: đếm cách chia dãy thành ba đoạn liên tiếp có tổng bằng nhau.
Sub 1: Thử mọi cặp cắt — ~O(N^2)~, dùng khi ~N \le 5000~
Thử mọi cặp ~(i, j)~ với ~2 \le i \le j \le N-1~, tính ba tổng bằng tổng tiền tố và kiểm tra bằng nhau.
Nếu chỉ nộp sub này: đúng 11/20 test.
Sub 2: Đếm một lượt — ~O(N)~
Nếu tổng ~T~ không chia hết cho 3 thì đáp án bằng 0. Ngược lại, cần ~P_{i-1} = T/3~ và ~P_j = 2T/3~. Duyệt ~j~ tăng dần, đếm số vị trí cắt thứ nhất đã gặp.
Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Với ~N \le 5000~ gọi sub 1, còn lại gọi sub 2. 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;
vector<long long> W; // W[1..N]
vector<long long> P; // P[i] = W[1] + ... + W[i], P[0] = 0
// Sub 1: thử mọi cặp (i, j) O(N^2) — dùng khi N <= 5000
// Đoạn 1: 1..i-1, đoạn 2: i..j, đoạn 3: j+1..N.
void sub1() {
long long ans = 0;
for (int i = 2; i <= N - 1; i++)
for (int j = i; j <= N - 1; j++) {
long long a1 = P[i - 1];
long long a2 = P[j] - P[i - 1];
long long a3 = P[N] - P[j];
if (a1 == a2 && a2 == a3) ans++;
}
cout << ans << "\n";
}
// Sub 2: đếm một lượt O(N) — lời giải đầy đủ
// Ba đoạn bằng nhau khi P[i-1] = T/3 và P[j] = 2T/3 với T = tổng.
void sub2() {
long long T = P[N];
if (T % 3 != 0) {
cout << 0 << "\n";
return;
}
long long X = T / 3;
long long ans = 0, cnt = 0;
for (int q = 2; q <= N - 1; q++) {
// p = q-1 là vị trí cắt thứ nhất khả dĩ (p >= 1), đếm các p <= q-1 có P[p] = X
if (P[q - 1] == X) cnt++;
if (P[q] == 2 * X) ans += cnt;
}
cout << ans << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N;
W.assign(N + 1, 0);
P.assign(N + 1, 0);
for (int i = 1; i <= N; i++) {
cin >> W[i];
P[i] = P[i - 1] + W[i];
}
if (N <= 5000) sub1();
else sub2();
return 0;
}
Bình luận