Hướng dẫn giải của [200 đề thầy Đức] Bài 51: Đếm số


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.

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

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.