Hướng dẫn giải của [200 đề thầy Đức] Bài 66: Viết số trang
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
Đánh số $N$ trang liên tiếp từ $a$ đến $a + N - 1$, cần đếm số lần xuất hiện của mỗi chữ số $0, \dots, 9$ trong các số trang đó.
Sub 1: Vét cạn từng số trang — ~O(N \cdot \log A)~
Duyệt từng số trang, đổi số đó thành chuỗi và đếm từng ký tự. Với $N \le 10^5$ và mỗi số có tối đa 6 chữ số, cách này đủ nhanh. Đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long n, a;
cin >> n >> a;
long long cnt[10] = {0};
// Vét cạn: với mỗi số trang, đổi ra chuỗi rồi đếm từng ký tự.
for (long long p = a; p <= a + n - 1; p++) {
string s = to_string(p);
for (char ch : s) cnt[ch - '0']++;
}
for (int d = 0; d < 10; d++) {
if (d) cout << ' ';
cout << cnt[d];
}
cout << "\n";
return 0;
}
Sub 2: Đếm theo từng hàng số — ~O(\log A)~
Thay vì duyệt từng trang, ta đếm theo từng vị trí hàng $p = 1, 10, 100, \dots$. Với số $X$ và chữ số $d$, đặt:
- $high = \lfloor X / (10p) \rfloor$: phần bên trái vị trí $p$;
- $cur = \lfloor X / p \rfloor \bmod 10$: chữ số tại vị trí $p$;
- $low = X \bmod p$: phần bên phải vị trí $p$.
Với $d \ne 0$, số lần $d$ xuất hiện ở hàng $p$ trong các số từ $1$ đến $X$ là $high \cdot p$, cộng thêm $p$ nếu $cur > d$, hoặc $low + 1$ nếu $cur = d$.
Với $d = 0$ phải bỏ các số có chữ số $0$ đứng đầu: nếu $high = 0$ thì hàng đó không đóng góp; nếu không thì đóng góp $(high - 1) \cdot p$ cộng $p$ (khi $cur > 0$) hoặc $low + 1$ (khi $cur = 0$).
Số lần $d$ xuất hiện trong đoạn $[a, a+N-1]$ bằng hiệu của hàm đếm tại $a + N - 1$ và tại $a - 1$. Ví dụ $N = 18$, $a = 3$ (các trang $3..20$): kết quả $2\ 11\ 2\ 2\ 2\ 2\ 2\ 2\ 2\ 2$.
Bẫy cần chú ý: không tính chữ số $0$ đứng đầu của số (ví dụ số $10$ có một chữ số $0$, không phải hai), đó là lý do có nhánh riêng cho $d = 0$.
#include <bits/stdc++.h>
using namespace std;
// Đếm số lần chữ số d xuất hiện trong các số từ 1 đến X (không tính số 0 đứng đầu).
long long countDigit(long long X, int d) {
long long res = 0;
for (long long p = 1; p <= X; p *= 10) { // p là vị trí hàng: đơn vị, chục, trăm...
long long high = X / (p * 10); // các chữ số bên trái vị trí p
long long cur = (X / p) % 10; // chữ số đứng ở vị trí p
long long low = X % p; // các chữ số bên phải vị trí p
if (d == 0) {
if (high == 0) continue; // không có chữ số đầu, số 0 ở đây là số 0 đứng đầu
res += (high - 1) * p;
res += (cur > 0) ? p : low + 1;
} else {
res += high * p;
if (cur > d) res += p;
else if (cur == d) res += low + 1;
}
}
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long n, a;
cin >> n >> a;
long long R = a + n - 1; // trang cuối cùng
// Số lần chữ số d xuất hiện trong [a, R] = countDigit(R) - countDigit(a - 1).
for (int d = 0; d < 10; d++) {
if (d) cout << ' ';
cout << countDigit(R, d) - countDigit(a - 1, d);
}
cout << "\n";
return 0;
}
Bình luận