Hướng dẫn giải của [VTT Q4 Contest 15] Bài 3: Đếm số [COUNT]
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
Với mỗi ~k~, đếm số nguyên dương nhỏ hơn ~k~ không có trong dãy. Số cần tìm bằng ~(k - 1)~ trừ đi số giá trị phân biệt của dãy nằm trong khoảng ~[1, k-1]~.
Sub 1: Đánh dấu — dùng khi ~m = 1, a_i \le 10^5~
Dùng mảng đánh dấu các giá trị có mặt, rồi đếm các số vắng mặt từ 1 đến ~\min(k-1, 10^5)~; các số lớn hơn ~10^5~ chắc chắn vắng mặt nên cộng thẳng phần còn lại. Chú ý ~k~ có thể tới ~10^9~ nên không được duyệt mảng quá ~10^5~. Nếu chỉ nộp sub này: đúng 30/75 test (các test có nhiều truy vấn hoặc giá trị lớn bị sai).
Sub 2: Sắp xếp, loại trùng — dùng khi ~m = 1~
Sắp xếp dãy, loại phần tử trùng (trùng không làm giảm thêm số vắng mặt), đếm số giá trị phân biệt thuộc ~[1, k-1]~ bằng một lần duyệt. Nếu chỉ nộp sub này: đúng 60/75 test (sai ở các test ~m > 1~ vì chỉ xử lý truy vấn đầu).
Sub 3: Chặt nhị phân cho mọi truy vấn — ~O(n \log n + m \log n)~
Sau khi sắp xếp và loại trùng một lần, mỗi truy vấn dùng lower_bound để biết có bao nhiêu giá trị phân biệt nhỏ hơn ~k~ (trừ đi các giá trị không dương nếu có). Đầu vào lên tới ~10^6~ số nên nhớ dùng đọc/ghi nhanh. Nếu chỉ nộp sub này: đúng 75/75 test.
Chương trình hoàn chỉnh
main đọc dữ liệu; nếu ~m = 1~ và mọi ~a_i \le 10^5~ gọi sub1, nếu chỉ ~m = 1~ gọi sub2, còn lại gọi sub3. 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, m;
int a[100005];
int K[1000005];
bool has[100005];
// Sub 1: m = 1, a_i <= 10^5 — đánh dấu các giá trị có mặt rồi đếm số vắng mặt trong [1, k-1]
void sub1() {
for (int i = 0; i < n; i++) if (a[i] <= 100000) has[a[i]] = true;
long long k = K[0], cnt = 0;
for (long long v = 1; v < k && v <= 100000; v++) if (!has[v]) cnt++;
if (k - 1 > 100000) cnt += k - 1 - 100000; // các số > 10^5 chắc chắn vắng mặt
cout << cnt << "\n";
}
// Sub 2: m = 1 — số cần đếm = (k-1) - (số giá trị phân biệt thuộc [1, k-1]); sắp xếp để loại trùng
void sub2() {
sort(a, a + n);
int sz = unique(a, a + n) - a;
long long k = K[0], present = 0;
for (int i = 0; i < sz; i++) if (a[i] >= 1 && a[i] < k) present++;
cout << (k - 1) - present << "\n";
}
// Sub 3: sắp xếp, loại trùng một lần, mỗi truy vấn dùng chặt nhị phân: ~O(n \log n + m \log n)~
void sub3() {
sort(a, a + n);
int sz = unique(a, a + n) - a;
int lo = lower_bound(a, a + sz, 1) - a; // bỏ qua giá trị không dương (nếu có)
for (int i = 0; i < m; i++) {
long long k = K[i];
long long present = (lower_bound(a, a + sz, (int)k) - a) - lo;
if (present < 0) present = 0;
cout << (k - 1) - present << "\n";
}
}
int main() {
freopen("COUNT.INP", "r", stdin);
freopen("COUNT.OUT", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> m;
int mxa = 0;
for (int i = 0; i < n; i++) { cin >> a[i]; mxa = max(mxa, a[i]); }
for (int i = 0; i < m; i++) cin >> K[i];
if (m == 1 && mxa <= 100000) sub1();
else if (m == 1) sub2();
else sub3();
}
Bình luận