UVALive 2889（回文数字）-白红宇

UVALive 2889（回文数字）

阅读量：4654 次

发布时间：2019-06-09

本文共 2540 字，大约阅读时间需要 8 分钟。

题意：给定i，输出第i个回文数字。

分析：1,2,3,4，……，9------------------------------------------------------------------------------------------9个

　　　11,12,13,14，……，19-------------------------------------------------------------------------------------9个

　　　101,111,121,131,141,151,161,171,181,191,202,212,222,232，……，979,989,999-------------------------------90个

　　　1001,1111,1221,1331,1441，……，9889,9999----------------------------------------------------------------90个

　　　10001,10101,10201,10301，……，99899,99999--------------------------------------------------------------900个

　　　规律是把回文串一分为二看，例如第四行，前两个数字是从10到99，共90个数字。而第三行也是从10到99，区别在于，需要去掉最后一位再反转，才是另一半（后两个数字）。

思路：先确定i所对应的回文数字的位数，再确定具体值。

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 #include
            
              9 #include
             
              10 #include
              
               11 #include
               
                12 #include
                
                 13 #include
                 14 #include
                  
                   15 #include
                   
                    16 #include
                    
                     17 #include
                     
                      18 #define fin freopen("in.txt", "r", stdin)19 #define fout freopen("out.txt", "w", stdout)20 #define pr(x) cout << #x << " : " << x << " "21 #define prln(x) cout << #x << " : " << x << endl22 typedef long long ll;23 typedef unsigned long long llu;24 const int INT_INF = 0x3f3f3f3f;25 const int INT_M_INF = 0x7f7f7f7f;26 const ll LL_INF = 0x3f3f3f3f3f3f3f3f;27 const ll LL_M_INF = 0x7f7f7f7f7f7f7f7f;28 const double pi = acos(-1.0);29 const double EPS = 1e-6;30 const int dx[] = { 0, 0, -1, 1};31 const int dy[] = {-1, 1, 0, 0};32 const ll MOD = 1e9 + 7;33 const int MAXN = 1000000 + 10;34 const int MAXT = 10000 + 10;35 using namespace std;36 ll a[25];37 void init()38 {39 ll tmp = ll(9);40 for(int i = 1; i < 20; i += 2)41 {42 a[i] = a[i - 1] = tmp;43 tmp *= ll(10);44 }45 }46 ll POW(ll x)47 {48 ll w = 1;49 for(ll i = 1; i <= x; ++i)50 w *= ll(10);51 return w;52 }53 int main()54 {55 init();56 int n;57 while(scanf("%d", &n) == 1 && n)58 {59 int cnt = 0;60 while(n > a[cnt])61 {62 n -= a[cnt];63 ++cnt;64 }65 if(cnt == 0)66 {67 printf("%d\n", n);68 continue;69 }70 else if(cnt == 1)71 {72 printf("%d%d\n", n, n);73 continue;74 }75 else76 {77 int tmp = cnt / 2;78 char str[50];79 memset(str, 0, sizeof str);80 ll ans = POW(ll(cnt / 2)) + ll(n - 1);81 sprintf(str, "%lld", ans);//把数字变为指定格式的字符串82 printf("%s", str);83 string s = string(str);84 int len = s.size();85 if(cnt % 2 == 0) s.resize(len - 1);86 reverse(s.begin(), s.end());87 printf("%s\n", s.c_str());88 }89 }90 return 0;91 }