题目回顾

我们需要找到第 i 个回文数。回文数是指正读和反读都相同的数字，例如 1, 2, ..., 9, 11, 22, ..., 99, 101, 111, ..., 121, ...。需要注意的是，前导零不被允许，因此像 010 这样的数字不被视为回文数。

解题思路

回文数的构造可以按照数字的位数来分类：

1. 一位数回文：1 到 9，共 9 个。
2. 两位数回文：11 到 99，共 9 个。
3. 三位数回文：101 到 999，共 90 个。
4. 四位数回文：1001 到 9999，共 90 个。
5. 五位数回文：10001 到 99999，共 900 个。
6. 六位数回文：100001 到 999999，共 900 个。
7. 以此类推。

可以发现，对于 n 位数的回文数：

• 如果 n 是奇数，回文数的数量为 9 × 10^{(n-1)/2}。
• 如果 n 是偶数，回文数的数量为 9 × 10^{(n/2 - 1)}。

解决步骤

1. 确定回文数的位数 m：

   • 初始化 m = 1，count = 9（一位数的回文数数量）。
   • 如果 i > count，则 i -= count，m += 1，并更新 count 为 m 位数回文数的数量。
   • 重复此过程，直到 i <= count，此时 m 即为第 i 个回文数的位数。

2. 构造回文数：

   • 计算基数 base = 10^{(m - 1)/2}（如果 m 是奇数）或 10^{(m/2 - 1)}（如果 m 是偶数）。
   • 前半部分 half = base + (i - 1)。
   • 将 half 转换为字符串，然后根据 m 的奇偶性构造回文数：
     • 如果 m 是奇数，回文数为 half + half[:-1][::-1]。
     • 如果 m 是偶数，回文数为 half + half[::-1]。

代码解析

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL __int64
const int inf = 0x3f3f3f3f;
const int N = 2010;
LL f[30]={0,1,1};
LL n;

void solve()
{
    int i,j;
    int k = 1;//k表示回文串数字的位数
    while(n > f[k]*9)
    {
        n -= 9*f[k++];
    }//n要减去小于k位的所有回文数
    int mid = (k+1)>>1;
    LL ans = 1;
    for(i  = 1, j = 0; i <= mid; i ++)//第一位到中间那一位
    {
        if(i == 1) j = 1;//i为1，因为首位不能为0，所以要从1开始
        else j = 0;//j表示第i位要填的数字
        while(n > f[k])
        {
            n -= f[k];//减去基数
            j ++;
        }
        k -= 2;//除了第i位和i相对称的那一位，中间还有几位
        if(i == 1) ans = j;
        else ans = ans*10 + j;
    }
    printf("%I64d",ans);
    if(k&1) ans /= 10;//位数为奇数，最中间的数只输出一次
    while(ans)
    {
        printf("%I64d",ans%10);
        ans /= 10;
    }
    printf("\n");
}

int main()
{
    int i;
    for(i = 3; i < 30; i ++)
    {
        if(i&1) f[i] = f[i-1]*10;
        else f[i] = f[i-1];
    }
    while(scanf("%I64d",&n),n)
    {
        solve();
    }
    return 0;
}

代码解释

1. 预处理数组 f：

   • f[i] 表示 i 位回文数的基数。
   • 对于奇数位，f[i] = f[i-1]*10。
   • 对于偶数位，f[i] = f[i-1]。

2. solve 函数：

   • 确定回文数的位数 k。
   • 计算中间位置 mid。
   • 构造前半部分数字 ans。
   • 根据位数 k 的奇偶性，输出前半部分和其反向部分。

3. 主函数 main：

   • 预处理 f 数组。
   • 读取输入 n，调用 solve 函数处理每个 n，直到输入 0 结束。

示例验证

以题目中的示例为例：

1. 输入 n = 1：

   • k = 1，mid = 1。
   • ans = 1。
   • 输出 1。

2. 输入 n = 12：

   • k = 2，mid = 1。
   • ans = 3。
   • 输出 33。

3. 输入 n = 24：

   • k = 3，mid = 2。
   • ans = 15。
   • 输出 151。

复杂度分析

• 时间复杂度：预处理 O(1)，solve 函数 O(log n)。
• 空间复杂度：O(1)。

总结

通过分析回文数的构造规律，可以高效地找到第 i 个回文数。关键在于确定回文数的位数，然后通过数字的前半部分构造完整的回文数。这种方法避免了逐个检查每个数字是否为回文数的低效做法，适用于大范围的输入。