POJ2402+模拟

题意:找出第index 个回文数。
这题是有规律的，即list[]数组。
其次，对于某个 index 可以先精确到位数 pos，然后在进行分析。
  1 #include<stdio.h>
  2 #include<string.h>
  3 #include<math.h>
  4 typedef __int64 int64;
  5 int64 list[ 24 ];
  6 int ans[ 240 ];
  7 
  8 void init(){
  9     list[0] = 0;
 10     list[1] = 9;
 11     list[2] = 9;
 12     list[3] = 90;
 13     list[4] = 90;
 14     list[5] = 900;
 15     list[6] = 900;
 16     list[7] = 9000;
 17     list[8] = 9000;
 18     list[9] = 90000;
 19     list[10] = 90000;
 20     list[11] = 900000;
 21     list[12] = 900000;
 22     list[13] = 9000000;
 23     list[14] = 9000000;
 24     list[15] = 90000000;
 25     list[16] = 90000000;
 26     list[17] = 900000000;
 27     list[18] = 900000000;
 28     list[19] = 9000000000;
 29     list[20] = 9000000000;
 30     //printf("list20=%I64d
",list[20]);
 31 }
 32 int main(){
 33     int64 index;
 34     init();
 35     while( scanf("%I64d",&index),index ){
 36         int pos;
 37         for( int num=0;num<=20;num++ ){
 38             if( index>=list[ num ] ){
 39                 index -= list[ num ];
 40                 pos = num;
 41             }
 42             else
 43                 break;
 44         }
 45         if( index>0 ) pos ++;
 46         //printf("pos=%d
",pos);
 47         if( index==0 ){
 48             for( int i=0;i<pos;i++ )
 49                 printf("9");
 50             printf("
");
 51             continue;
 52         }
 53         int64 cur = list[ pos ]/9;
 54         if( index>=cur ){
 55             index += cur;
 56             index --;
 57             int tt=0;
 58             while( index!=0 ){
 59                 ans[ tt++ ] = index%10;
 60                 index /= 10;
 61             }
 62             if( pos%2==0 ){
 63                 for( int i=tt-1;i>=0;i-- )
 64                     printf("%d",ans[i]);
 65                 for( int i=0;i<tt;i++ )
 66                     printf("%d",ans[i]);
 67                 printf("
");
 68             }//偶数位
 69             else{
 70                 for( int i=tt-1;i>=0;i-- )
 71                     printf("%d",ans[i]);
 72                 for( int i=1;i<tt;i++ )
 73                     printf("%d",ans[i]);
 74                 printf("
");
 75             }//奇数位
 76         }
 77         else{
 78             index--;
 79             int num1 = 0;
 80             int num2 = 0;
 81             while( cur!=0 ){
 82                 num1++;
 83                 cur /= 10;
 84             }
 85             int tt = index;
 86             while( tt!=0 ){
 87                 num2++;
 88                 tt /= 10;
 89             }
 90             tt = 0;
 91             while( index!=0 ){
 92                 ans[tt++] = index%10;
 93                 index/=10;
 94             }
 95             for( int i=1;i<=num1-num2;i++ )
 96                 if( i==num1-num2 )
 97                     ans[tt++] = 1;
 98                 else
 99                     ans[tt++] = 0;
100             if( pos%2==0 ){
101                 for( int i=tt-1;i>=0;i-- )
102                     printf("%d",ans[i]);
103                 for( int i=0;i<tt;i++ )
104                     printf("%d",ans[i]);
105                 printf("
");
106             }
107             else{
108                 for( int i=tt-1;i>=0;i-- )
109                     printf("%d",ans[i]);
110                 for( int i=1;i<tt;i++ )
111                     printf("%d",ans[i]);
112                 printf("
");
113             }
114         }
115     }
116     return 0;
117 }
View Code
keep moving...