Hướng dẫn giải của Đếm số 9
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
Cho dãy n số nguyên và Q truy vấn (n, Q ≤ 10^5, |Ai| ≤ 10^6). Mỗi truy vấn (L, R) cần đếm số phần tử có giá trị bằng 9 trong đoạn từ AL đến A_R.
Ví dụ: dãy 1 9 3 9 5 9 9 8, truy vấn (1, 3) cho 1, (8, 8) cho 0, (2, 8) cho 4.
Sub 1: Vét cạn — ~O(n · Q)~
Mỗi truy vấn duyệt từ L đến R và đếm các phần tử bằng 9. Đúng nhưng chậm khi có nhiều truy vấn: đạt 13/20 test (7 test quá giờ).
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
vector<long long> a(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
// Vét cạn: mỗi truy vấn đếm trực tiếp số phần tử bằng 9 trong đoạn [L, R]
while (q--) {
int l, r;
cin >> l >> r;
int cnt = 0;
for (int i = l; i <= r; i++)
if (a[i] == 9) cnt++;
cout << cnt << '\n';
}
return 0;
}
Sub 2: Mảng đếm dồn — ~O(n + Q)~
Tính mảng pre[i] = số phần tử bằng 9 trong A1..Ai. Số phần tử bằng 9 trong [L, R] là pre[R] − pre[L−1], mỗi truy vấn O(1). Đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
// pre[i] = số phần tử bằng 9 trong A[1..i]; số lượng trong [L, R] = pre[R] - pre[L-1]
vector<int> pre(n + 1, 0);
for (int i = 1; i <= n; i++) {
long long x;
cin >> x;
pre[i] = pre[i - 1] + (x == 9 ? 1 : 0);
}
while (q--) {
int l, r;
cin >> l >> r;
cout << pre[r] - pre[l - 1] << '\n';
}
return 0;
}
Bình luận