Hướng giải của Đếm Số Đối Xứng

Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.

Tác giả: kienadmin

Phân tích

Một số đối xứng độ dài \(n\) được xác định hoàn toàn bởi \(\lceil n/2 \rceil\) chữ số đầu tiên. Ta đếm:

  • Các số có ít chữ số hơn: công thức \(9 \times 10^{\lfloor (len-1)/2 \rfloor}\).
  • Các số cùng độ dài: xây dựng nửa đầu, tạo số đối xứng rồi so sánh với \(N\).
// Giải thuật dig cho bài toán dig-palindrome\n#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll pow10[19];

void initPow() {
    pow10[0] = 1;
    for (int i = 1; i <= 18; i++) pow10[i] = pow10[i - 1] * 10;
}

ll countPalindrome(ll N) {
    if (N < 0) return 0;
    if (N == 0) return 1;  // So 0 la doi xung
    string s = to_string(N);
    int n = s.size();

    ll ans = 1;  // So 0

    // Cac so co it chu so hon
    for (int len = 1; len < n; len++) {
        ans += 9 * pow10[(len - 1) / 2];
    }

    // Cac so co cung do dai n
    int half = (n + 1) / 2;
    string prefix = s.substr(0, half);
    ll prefixVal = stoll(prefix);
    ll minPref = pow10[half - 1];
    ans += prefixVal - minPref;  // Cac prefix nho hon

    // Kiem tra prefix hien tai
    string pal = prefix;
    int mirror_start = (n % 2 == 0) ? half - 1 : half - 2;
    for (int i = mirror_start; i >= 0; i--) {
        pal += prefix[i];
    }
    if (pal <= s) ans++;
    return ans;
}

int main() {
    // Doc du lieu dau vao
    initPow();
    ll L, R;
    cin >> L >> R;
    cout << countPalindrome(R) - countPalindrome(L - 1) << '\n';
    return 0;
}

Độ phức tạp: \(O(\log R)\).

Nhận xét

Không có ý kiến tại thời điểm này.