题目描述

输入一个t, 表示有t组样例，每组样例输入一个整数n，求区间 [1,n]内有多少个回文数。

解题思路

按照常规的从1枚举到n再依次判断每个数是否为回文数显然是行不通的，所以我们需要用数学方法。

首先考虑位数为偶数的时候，如1542，位数为4，将它对半分为15和42，则当前半部分为14的时候，后两位可以取00到99之间的任意数，所以前两位从10到14都可以找到对应的后两位(如01，41)来形成回文数。此时我们只需考虑前两位是15的情况。观察知道后两位至少得是51才能与15形成回文数，而42<51，显然不行，也就是说1542只可形成前两位10到14这样5个回文数(1001，1111，1221，1331，1441)。求出了1000以上的回文数有多少个，再加上小于1000的回文数个数，即是[1,1542]之间回文数的个数。

故：对于数abcd，大于1000时，我们只需比较cd与ba的大小，如果cd>=ba，则有(cd-10)+1个回文数，否则为cd-10个。对于任意有2*l位数，令t=a/(10^l)(t就是该数的前面一半)，则:

ans=f[2*l-1]+t-10^(l-1)或ans=f[2*l-1]+t-10^(l-1)+1;

同理,对于位数为奇数的数如25368，只需比较368与352的大小，答案情况同上，如abcde,比较cde与cba的大小。如果数很大的话，最好用long long,这里用的是int.

如果要是求区间[a, b]内的回文数，只需分别求出[1, b]和[1, a]内的回文数，两者相减即可得出答案。

#include <stdio.h>
int f[12] = {0, 9, 18, 108, 198, 1098, 1998, 10998, 19998, 109998, 199998, 1099998};
int find(int x)
{
    int l, i, ans, t, a, b, na, nx;
    if (x < 10)
        return x;
    l = 0;
    nx = x;
    while (nx)
    {
        l++;
        nx /= 10;
    }
    t = 1;
    ans = f[l - 1];
    for (int k = 1; k <= l / 2; k++)
        t *= 10;
    na = 0;
    a = x / t;
    if (l & 1)
        t *= 10;
    b = x % t;
    t /= 10;
    ans += a - t;
    while (a)
    {
        na = na * 10 + a % 10;
        a /= 10;
    }
    if (b >= na)
        ans++;
    return ans;
}
int main()
{
    int t, n;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d", &n);
        printf("%d\n", find(n));
    }
    return 0;
}