Hướng dẫn cho Baroibeo Number

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: SPyofgame

Spoiler Alert

Hint 1

Duyệt và thử qua các số. Tăng biến đếm khi thỏa mãn

Hint 2

Thay vì duyệt các số và tăng giá trị số đó dần. Ta thử duyệt qua từng chữ số và ráp nó lại thành một số hoàn chỉnh để kiểm tra

Hint 3

Thử xây từng chữ số với các độ sâu.

Gọi cnt là số lượng chữ số khác 0

Gọi isLess để kiểm tra nếu số đó đã nhỏ hơn Ri

Gọi isGreater để kiểm tra nếu số đó đã lớn hơn Li

Hint 4

Gọi f(x) là số số không âm thỏa mãn bé hơn x

Có result = f(r) - f(l - 1)

Lúc này ta chỉ cần kiểm tra hai lần việc isLess với Ri và Li - 1.

Bỏ biến isGreater vì số đang được xây từng chữ số luôn không âm

Reference AC code | \(O(n * 3 * 2)\) time | \(O(n)\) auxiliary space | DP_digit, DP_count

C++
int n;
vector<int> a;
vector<vector<vector<ll> > > f;
ll magic(int i = 0, int cnt = 0, bool isLess = false) /// Đệ quy có nhớ
{
    if (cnt > 3) return false;   /// Nếu số không thỏa mãn
    if (i >= n) return cnt <= 3; /// Nếu đã xây hết số, kiểm tra nếu số thỏa mãn

    ll &res = f[i][cnt][iln];  /// Dùng con trỏ &res để tiện mắt
    if (res != -1) return res; /// Nếu đã tính toán thì xuất
    res = 0;                   /// Ngược lại reset giá trị

    /// Cận dưới (lim) = 9 khi số đã bé hơn n, ngược lại là a[i]
    int lim = isLess ? 9 : a[i];
    for (int d = 0; d <= lim; ++d) /// Duyệt qua từng chữ số
        res += magic(i + 1, cnt + (d != 0), isLess || (d < lim)); /// Đệ quy độ sâu tiếp theo

    return res;
}

vi convert(ll n) /// Chuyển đổi số thành vector chữ số
{
    vector<int> a;
    /// Đẩy từng chữ số cuối cùng của n vào vị trí cuối mảng a
    do a.pb(n % 10); while (n /= 10);
    return reverse(a.begin(), a.end()), a;
}

int query() /// Với mỗi truy vấn
{
    /// Nhận phần tử
    ll l = readLong();
    ll r = readLong();

    /// Tính f(r)
    a = convert(r);
    n = a.size();
    f.assign(n + 1, vector<vector<ll> >(5, vector<ll>(2, -1)));
    ll fr = magic();

    /// Tính f(l - 1)
    a = convert(l - 1);
    n = a.size();
    f.assign(n + 1, vector<vector<ll> >(5, vector<ll>(2, -1)));
    ll fl = magic();

    /// Xuất ra
    cout << fr - fl << '\n';
    return 0;
}

Bình luận

Không có bình luận nào.