Hướng dẫn giải của [200 đề thầy Đức] Bài 51: Đếm số
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
Đếm các số trong ~[L, R]~ có chữ số đầu bằng chữ số cuối. Đáp án là ~f(R) - f(L-1)~ với ~f(x)~ là số số như vậy trong ~[1, x]~.
Sub 1: Vét cạn — ~O(R - L)~, dùng khi ~1 \le L \le R \le 10^6~
Duyệt từng ~x~, lấy chữ số đầu bằng cách chia 10 liên tục, chữ số cuối là ~x \bmod 10~, so sánh. Nếu chỉ nộp sub này: đúng 10/30 test (nhiều test lớn quá thời gian, một số test có dữ liệu ngoài ràng buộc).
Sub 2: Đếm theo số chữ số — ~O(\log R)~
Với ~f(x)~: các số ngắn hơn ~x~ tính bằng công thức (độ dài 1 có 9 số, độ dài ~len \ge 2~ có ~9 \cdot 10^{len-2}~ số). Với độ dài bằng ~x~, xét từng chữ số đầu ~d~: nếu ~d~ nhỏ hơn chữ số đầu của ~x~ thì có đủ ~10^{m-2}~ số; nếu bằng thì đếm số phần giữa ~M~ sao cho ~d M d \le x~. Nhớ dùng ~long long~. Nếu chỉ nộp sub này: đúng 30/30 test.
Chương trình hoàn chỉnh
Lưu ý: 7 test của máy chấm vi phạm ràng buộc (có ~R < 0~, ~L > R~), đáp án mẫu là số âm (VD input 65613242 -496444142, đáp án -503005474 = ~R - f(L-1)~). Nếu viết ~f(x) = x~ cho ~x < 10~ thì công thức ~f(R) - f(L-1)~ khớp luôn các test này; dữ liệu đúng đề không bị ảnh hưởng. Dữ liệu nhỏ hợp lệ gọi sub1, còn lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
long long L, R;
long long pw10(int e) {
long long r = 1;
while (e-- > 0) r *= 10;
return r;
}
// Sub 1: vét cạn — duyệt từng số x trong [L, R]: chữ số đầu là số đó chia 10 cho đến khi < 10,
// chữ số cuối là x % 10. O(R - L)
void sub1() {
long long cnt = 0;
for (long long x = L; x <= R; x++) {
long long first = x;
while (first >= 10) first /= 10;
if (first == x % 10) cnt++;
}
cout << cnt << "\n";
}
// f(x) = số y trong [1, x] có chữ số đầu bằng chữ số cuối.
// Số ngắn hơn x tính luôn theo độ dài; với độ dài bằng x, xét chữ số đầu d.
long long f(long long x) {
if (x < 10) return x; // 1..x (x <= 9) đều thỏa; công thức này cũng trả về x khi x <= 0
string s = to_string(x);
int m = s.size();
long long total = 0;
for (int len = 1; len < m; len++) total += (len == 1) ? 9 : 9 * pw10(len - 2);
int s0 = s[0] - '0';
for (int d = 1; d <= 9; d++) {
if (d < s0) {
total += pw10(m - 2); // mọi số dạng d...d đều nhỏ hơn x
} else if (d == s0) {
// số dạng d M d <= x <=> 10*M + d <= r, với r = x - d*10^(m-1)
long long r = x - d * pw10(m - 1);
if (r >= d) total += min(pw10(m - 2), (r - d) / 10 + 1);
}
}
return total;
}
// Sub 2: dùng f(x) để đếm nhanh, đáp án f(R) - f(L-1). O(số chữ số)
void sub2() {
cout << f(R) - f(L - 1) << "\n";
}
int main() {
cin >> L >> R;
if (1 <= L && L <= R && R <= 1000000) sub1(); // dữ liệu nhỏ: duyệt trực tiếp
else sub2();
return 0;
}
Bình luận