Hướng dẫn giải của [VTT Q4 Contest 10] Bài 4: Tổng k [SUMK]
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ổng các ô của hình chữ nhật hàng ~i..j~, cột ~u..v~ là ~(a_i + \dots + a_j) \cdot (a_u + \dots + a_v)~, tức tích của hai tổng đoạn. Vậy bài toán là đếm cặp đoạn (đoạn hàng, đoạn cột) có tích tổng bằng ~k~.
Sub 1: Vét cạn — ~O(n^4)~, dùng khi ~n \le 100~
Duyệt mọi bộ bốn ~(i, j, u, v)~, tính hai tổng đoạn bằng tổng tiền tố và kiểm tra tích bằng ~k~. Nếu chỉ nộp sub này: đúng 11/20 test.
Sub 2: Đếm tổng đoạn rồi ghép ước — ~O(n^2 + k)~
Với mỗi đoạn, tính tổng ~s~; vì ~a_i \ge 0~ nên khi ~s > k~ có thể dừng. Gọi ~cnt_s~ là số đoạn có tổng ~s~ (chỉ cần ~s \le k~; tổng bằng 0 không cho tích bằng ~k~ vì ~k \ge 1~). Đáp án là tổng của ~cnt_d \cdot cnt_{k/d}~ trên các ước ~d~ của ~k~. Dùng ~long long~ cho đáp án. Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Main đọc dữ liệu và tính tổng tiền tố, ~n \le 100~ gọi sub1, ngược lại sub2. Khi đi thi nên viết như vậy: sub sau 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;
int a[8005];
long long pre[8005];
// Tổng các ô của hình chữ nhật (hàng i..j, cột u..v) = (a_i+..+a_j) * (a_u+..+a_v)
// Sub 1: duyệt mọi hình chữ nhật — O(n^4), dùng khi n <= 100
void sub1() {
long long ans = 0;
for (int i = 1; i <= n; i++)
for (int j = i; j <= n; j++)
for (int u = 1; u <= n; u++)
for (int v = u; v <= n; v++)
if ((pre[j] - pre[i - 1]) * (pre[v] - pre[u - 1]) == k) ans++;
cout << ans << "\n";
}
// Sub 2: đếm số đoạn có tổng s (s <= k), rồi ghép ước d với k/d — O(n^2 + k)
void sub2() {
vector<long long> cnt(k + 1, 0);
for (int i = 1; i <= n; i++)
for (int j = i; j <= n; j++) {
long long s = pre[j] - pre[i - 1];
if (s > k) break; // a không âm nên tổng chỉ tăng
cnt[s]++;
}
long long ans = 0;
for (long long d = 1; d <= k; d++)
if (k % d == 0) ans += cnt[d] * cnt[k / d];
cout << ans << "\n";
}
int main() {
freopen("SUMK.INP", "r", stdin);
freopen("SUMK.OUT", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> k;
for (int i = 1; i <= n; i++) { cin >> a[i]; pre[i] = pre[i - 1] + a[i]; }
if (n <= 100) sub1();
else sub2();
}
Bình luận