题解 P1609 【最小回文数】
Tomone
2018-03-18 00:23:43
C++代码
因为范围是10^100,所以int 只能拿到60分。
只能用字符串。
```cpp
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<sstream>
#define MAXN 3000001
using namespace std;
char str[MAXN],temp[MAXN];
int b[MAXN],len;
int main(){
cin>>str;
len=strlen(str);
for(int i=0;i<len;++i)
b[i]=str[i]-'0';
if(len==1){ //一位数和两位数特判一下
if(str[0]=='9'){
cout<<11;
return 0;
}
if(str[0]<'9'){
cout<<str[0]-'0'+1;
return 0;
}
}
if(len==2){
if(str[0]>str[1]) cout<<str[0]<<str[0];
if(str[0]<=str[1]) cout<<str[0]-'0'+1<<str[0]-'0'+1;
return 0;
}
if(len%2==0){ //偶数
for(int i=0;i<len;++i)
temp[i]=str[i];
temp[len/2]=0;
if (str[len/2-1]==str[len/2]){ //有可能是回文数
int i,j;
for(i = len/2-1,j=len/2;j<len;++j,--i){
if (str[i] != str[j]) break;
}
if(j==len||str[i]<str[j]){ //n为回文数 or 不是回文数且其前半部分小
int num;
sscanf(temp,"%d",&num);
++num;
sprintf(temp,"%d",num);
cout<<num;
for(int i=len/2-1;i>=0;--i){
cout<<temp[i];
}
}else{ ////不是回文数但其前半部分大
cout<<temp;
for(int i =len/2-1;i>= 0;--i)
cout<<temp[i];
}
}else if(str[len/2-1]<str[len/2]){ //中间靠前的数比后面的小
temp[len/2 - 1] = char(temp[len/2 - 1] + 1);
cout<<temp;
for(int i=len/2-1;i>=0;--i){
cout<<temp[i];
}
}else{ //中间靠前的数比后面的大
cout<<temp;
for(int i=len/2-1;i>=0;--i){
cout<<temp[i];
}
}
}
if(len%2==1){ //奇数
for(int i=0;i<len/2+1;++i)
temp[i]=str[i];
temp[len/2+1]='\0';
int i,j;
for(i=len/2-1,j=len/2+1;j<len;--i,++j)
if (str[i]!=str[j]) break;
if(j==len||str[i]<str[j]){ //n是回文数 或不是回文数但其前半部分小
int num;
sscanf(temp,"%d",&num);
++num;
sprintf(temp,"%d",num);
cout<<num;
for(int i=len/2-1;i>=0;--i)
cout<<temp[i];
}else{ //不是回文数 但前半部分大
cout<<temp;
for(int i=len/2-1;i>=0;--i)
cout<<temp[i];
}
}
return 0;
}
```
参考自:https://www.cnblogs.com/itachi7/archive/2012/07/03/2574481.html
洛谷没itoa所以把itoa和atoi都换成ssprintf和sscanf了
蒟蒻博客:aptx.xin