14054: 【原4054】伪回文数

题目描述

author: Will 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4054

Description

口口君特别喜欢回文数，由于已经考过回文数，口口君只好造出了伪回文数。定义如下：
对于一个十进制非负整数 X，如果他的第一位等于他的最后一位，则称 X 为伪回文数。
如，101, 477474 以及 9 都属于伪回文数。口口君很好奇对于一个给定区间 [L, R] ( L <= R 且 L, R 都是非负整数)究竟有多少个这样的伪回文数。

Input Format

一行，包含非负整数 L 和 R (1 <= L <= R <= 10^18)。

Output Format

一行，区间 [L, R] 内伪回文数的个数。

Sample Input

2 47

Sample Output

Sample Input

47 1024

Sample Output

数据范围

对于 50% 的数据 (0 <= R - L <= 10^5)  
对于 100% 的数据 (1 <= L <= R <= 10^18)

BugenZhao's solution

//
// Created by BugenZhao on 2019/3/23.
//

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

using ll=long long;

ll tmpe[20] = {0, 1};
ll *e = tmpe + 1;

int getLength(ll num) {
    int ans = 1;
    while (num /= 10) {
        ++ans;
    }
    return ans;
}

int getFront(ll num) {
    while (true) {
        if (num <= 9) break;
        num /= 10;
    }
    return (int) num;
}

int main() {
    for (int i = 1; i < 19; ++i) {
        e[i] = e[i - 1] * 10;
    }
    ll l, r;
    cin >> l >> r;
    ll ans = 0;

    int lLength = getLength(l), rLength = getLength(r);
    int lFront = getFront(l), rFront = getFront(r);

    if (lLength == rLength) {
        ll N = e[lLength - 1] * lFront + 9 * e[lLength - 2] + lFront;
        ll n = e[lLength - 1] * rFront + rFront;
        if (lFront == rFront) {
            if (l <= n) {
                if (r < n) ans += 0;
                else ans += (r - n) / 10 + 1;
            } else {
                if (r < n) ans += (r - l) / 10;
                else ans += (n - l) / 10;
            }
        } else {
            ans += (N - l > 0) ? (N - l) / 10 : 0;
            ans += (l - n > 0) ? (l - n) / 10 : 0;
            ans += (rFront - lFront - 1) * (lLength == 1 ? 1 : e[lLength - 2]);
        }
        cout << ans << endl;
        return 0;
    }
    for (int i = lLength + 1; i < rLength; ++i) {
        ans += 9 * e[i - 2];
    }


    for (int i = lFront; i < 10; ++i) {
        if (i != lFront) {
            ans += e[lLength - 2];
            continue;
        }
        ll N = e[lLength - 1] * i + 9 * e[lLength - 2] + i;
        ll tmp = N - l;
        ans += (tmp > 0) ? tmp / 10 : 0;
    }

    for (int i = 1; i <= rFront; ++i) {
        if (i != rFront) {
            ans += e[lLength - 2];
            continue;
        }
        ll n = e[lLength - 1] * i + i;
        ll tmp = l - n;
        ans += (tmp > 0) ? tmp / 10 : 0;
    }

    cout << ans << endl;
    return 0;
}

FineArtz's solution

/* 伪回文数 */
#include <iostream>
#include <cmath>
using namespace std;

inline int firstDigit(long long r){
    while (r >= 10) r /= 10;
    return r;
}

long long f(long long x){
    if (x < 10) return x + 1;
    return (9 + x / 10 + (int)(x % 10 >= firstDigit(x)));
}

int main(){
    long long l, r;
    cin >> l >> r;
    long long ans = f(r) - f(l - 1);
    cout << ans << endl;
    return 0;
}

ligongzzz's solution

#include "iostream"
#include "cstdio"
#include "cstring"
#include "cmath"
using namespace std;

long long poww(int i) {
    long long ans = 1;
    for (int j = 0; j < i; ++j)
        ans *= 10;
    return ans;
}

long long cal(char* ch) {
    int len = strlen(ch);
    if (len == 1)
        return ch[0] - '0';
    if (len == 2) {
        if (ch[0] > ch[1])
            return ch[0] - '1' + 9;
        else
            return ch[0] - '0' + 9;
    }
    int temp = ch[0] > ch[len - 1] ? ch[len - 1] - '0' : ch[0] - '0';

    long long ans = 9;
    for (int i = 0; i < len - 2; ++i)
        ans += (long long)9 * poww(i);
    long long p = 1;
    char ch1[100];
    strcpy(ch1, ch + 1);
    ch1[strlen(ch1) - 1] = 0;
    sscanf(ch1, "%lld", &p);
    if (ch[0] <= ch[len - 1])
        ans += p + 1;
    else
        ans += p;
    ans += (long long)(ch[0] - '1') * poww(len - 2);
    return ans;
}

int main() {

    char L[100], R[100];
    cin >> L >> R;

    long long Lans, Rans;
    Lans = cal(L);
    Rans = cal(R);

    if (L[0] == L[strlen(L) - 1])
        ++Rans;

    cout << Rans - Lans;

    return 0;
}

skyzh's solution

#include <iostream>
using namespace std;

long long get_sum(long long R) {
    long long F = 1, D = 1, K = 0;
    long long SUM = 0;
    for (int i = 1; i <= 19; i++) {
        for (int j = 1; j <= 9; j++) {
            long long LOWER_BOUND = j * D;
            long long UPPER_BOUND = j * D + K * 10;
            if (R < LOWER_BOUND) return SUM;
            if (R < UPPER_BOUND) {
                long long T = R / 10, B = 1;
                while (T > 0) { T /= 10; B *= 10; }
                SUM += (R - B * j) / 10;
                if (R % 10 >= j) ++SUM;
            } else SUM += K + 1;
        }
        F *= 10;
        D = F + 1;
        if (i >= 2) K = K * 10 + 9;
    }
    return SUM;
}
int main() {
    long long L, R;
    cin >> L >> R;
    cout << get_sum(R) - get_sum(L - 1) << endl;
    return 0;
}