# 14054: 【原4054】伪回文数

### 题目描述

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

## Sample Input

``````2 47
``````

## Sample Output

``````12
``````

## Sample Input

``````47 1024
``````

## Sample Output

``````98
``````

## 数据范围

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

``````

## 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;
}
``````