洛谷 P1609 最小回文数 题解

2018-10-30 来源: ✐Van✎ 发布在  https://www.cnblogs.com/812-xiao-wen/p/9879208.html

这题其实并不难,重点在你对回文数的了解,根本就不需要高精度。

打个比方:

对于一个形如 ABCDEFGH 的整数

有且仅有一个比它大的最小回文数

有且仅有一个比它小的最大回文数

而整数 ABCDDCBA 一定是其中之一

~

如:99299是比99200大的最小回文数

10101 是比 10201 小的最大回文数

所以可以得出结论

~

输入一个整数 ABCD ,若整数ABBA 比 ABCD 大,则 ABBA 就是比它大的最小回文数,然后就可以直接输出这个答案了。

~

而如果 ABBA 比 ABCD 要小(或等于)那我们就要找到比 ABBA 大的下一个回文数。

不难发现它就是:ACCA 且 C=B+1。

注意:B=9时要进位,对于9999一类的数要特判!!!

~

原理:一个回文数是根据它前半部分来的,所以它的下一个回文数就是原回文数的最中间的一个(或两个)数加1得来的。(不懂的要好好想一想)

下面是代码:

#include<bits/stdc++.h>
using namespace std;
int l,i,f;  char s[201],k[201];
int main(){
    scanf("%s",s);
    l=strlen(s)-1;//下面是特判
    while(s[i++]=='9')if(i==l+1)for(s[0]='1',l++;i>0;i--)s[i]='0';
    for(i=0;i<=l-i;i++)k[i]=k[l-i]=s[i];
    if(strcmp(k,s)<=0){//小于原数的话中间要加1!
        while(k[--i]=='9');k[i]=k[l-i]=++k[i];
        for(i++;i<=l-i;i++)k[i]=k[l-i]='0';
    }cout<<k;
    return 0;
}
//对于特判的解释:
//像9999可以直接转换成10000来算。

最短代码,不接受质疑。

如有不懂可以私信我,如代码有漏洞请各位大佬及时指出,谢谢!

相关文章