AT_abc363_d 题解

ikunTLE · 2024-07-22 10:43:53 · 题解

题目传送门

思路

本题要求的是第 n 个回文数，暴力无法通过。但是我们可以先用暴力求出从 1 位到 8 位数各有多少个，见下表格（暂且忽略 0）：

总结一下，当位数为 k 时，有 9\times10^{\lfloor{\frac{k-1}{2}}\rfloor} 个回文数。解释一下原因，这是因为一个回文数可以转化为该数左半边与右半边相等，即左 \lfloor{\frac{k}{2}}\rfloor 位与右 \lfloor{\frac{k}{2}}\rfloor 位相等。

我们可以用上述规律逐步逼近我们的答案，最后将回文数拼接起来，就是我们最终的答案。

注意事项

• 如果该数的位数是奇数，那么就只需要计算左半边。

• long long 也见祖宗了，需要开 __int128。

AC CODE

#include<bits/stdc++.h>
using namespace std;
__int128 read(){__int128 x=0;char f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
void write(__int128 x){if(x<0)putchar('-'),x=-x;if(x>9)write(x/10);putchar(x%10+'0');return;}
int main(){
    __int128 n=read()-2,sum=0,p1=9,wei=0;
    while(true){
        if(wei>0&&wei%2==0)
            p1*=10;
        ++wei;
        if(sum+p1>n)
            break;
        sum+=p1;
    }
    n-=sum;
    __int128 p2=1;
    for(int i=1;i<=(wei-1)/2;++i)
        p2*=10;
    __int128 res=n+p2,temp=res;
    if(wei&1)
        temp/=10;
    while(temp)
        res=res*10+temp%10,temp/=10;
    write(res);
    return 0;
}