hoj 1384 Palindrome Number

   首先做一题之前做了,hoj1004那题,然后就给了自己一个误区,我的一次的想法和写1004时是一样!后来老是出现错误,所以我就改了下思路,算的上是灵光一现吧,因为人很容走入思维的定式,而且走进了就不容易出来!
   废话不说了!这一题说的是寻找2*1e9个范围内的回文数!time:3s,通过推算我们知道最大的那个回文数是19位1000000001000000001,第一次的思路就不说了,呵呵!第二次我是这么想的,从输入的数可以很快的判断是多少位的回文数,那么也能判断是这个位的回文数的第多少个,这个就需要自己算一算了!显然
1: 9  
2:9
3:90
4:90
。。。。。
我们能很容易的找到n位回文数中的第ith个回文数!
n位回文数最多有9*e((n+1/2)-1) 个,我把一个回文数拆成一半,因为是对称的!只要知道一半就够了(如果是奇数位的话,记住是加上中间的那个数),从左半部分看是从10e((n+1)/2-1)到9..9(共有( n+1)/2 个 9 ),那么你想知道的第ith个回文数是多少呢,就是
10e((n+1)/2-1) + (ith-1) ,然后输出一下就行了!记得还要反着输出一次啊!
 






#include
<stdio.h>
#include
<sstream>
#include
<string>
#include
<iostream>
using namespace std ;

string itos(int x)
{
    stringstream str ;
    str 
<< x ;
    
return str.str() ;
}


int num[20= 1 , 1 , 10 , 100 , 1000 , 10000 , 100000 , 1000000 , 10000000 , 100000000 , 1000000000 } ;
void solve( int ith , int  n )
{
    
int tem = n ;
    
if( n % 2 == 0 )
        tem 
= n/2 ;
    
else
    
{
        tem 
=  n/2 + 1 ;
    }

    
    
int ans = num[tem] + ith - 1 ;

    
string str = itos(ans) ;

    
int i ;
    
if( n % 2 == 0 )
    
{
        printf(
"%d" , ans) ;
    }

    
else
    
{
        
if( ans/10 != 0 )
            printf(
"%d" , ans /10 ) ;
    }

    
    
for( i = str.length() -1 ; i>= 0 ; i-- )
    
{
        cout
<<str[i];
    }

    cout
<<endl ;
    
return ;
}


int jud[] = {    0 ,// 0 位 假设 0 这个回文数 是 0 位 (呵呵)
                9 , 18 , // 1 and 2 位
                108 , 198 , // 3 and 4
                1098 , 1998 , // 5 and 6
                10998 , 19998 , // 7 and 8 
                109998 , 199998// 9 and 10
                1099998 , 1999998 , // 11 and 12 
                10999998 , 19999998 , // 13 and 14 
                109999998 , 199999998 , // 15 and 16
                1099999998 , 1999999998 }
 ;// 17 and 18
int main()
{
    
//int ntc ;
    
//scanf( "%d" , & ntc ) ;
    int n , ith ;
    
int i , tem ;
    
while( scanf( "%d" , & n ) != EOF)
    
{
        
if( n == 1999999999 )
        
{
            printf(
"1000000000000000001\n") ;
        }

        
else if( n == 2000000000)
        
{
            printf(
"1000000001000000001\n") ;
        }

        
else
        
{
            
for( i = 18 ; i> 0 ; i-- )
            
{
                
if( n > jud[i-1&& n <= jud[i] )
                
{
                    tem 
= i ;
                    ith 
= n - jud[i-1] ;
                    break ;
                }

            }

            solve( ith , tem ) ;
        }

    }

    
return 0 ;
}




第一次写,不好请见谅,我会努力的!

 

posted on 2009-07-12 07:15 xunil 阅读(339) 评论(5)  编辑 收藏 引用 所属分类: ACM

评论

# re: hoj 1384 Palindrome Number 2009-10-20 11:58 sum

能给下1004ac的代码么?
我提交的总是wa...可是自己测试又没有事情  回复  更多评论   

# re: hoj 1384 Palindrome Number 2009-10-20 16:39 xunil

你的邮箱 是多少?我发给我你!  回复  更多评论   

# re: hoj 1384 Palindrome Number 2009-10-23 23:09 sum

谢了...我的邮箱..
marchtea213@yahoo.com.cn  回复  更多评论   

# re: hoj 1384 Palindrome Number 2009-10-24 17:42 sum

˳���������...���õ�������Ȼ�����ж��Ƿ������������⣬����ÿ�����е�5.xx���WA�ˣ�Ҳ��֪��Ϊʲô������C���....  回复  更多评论   

# re: hoj 1384 Palindrome Number 2009-10-25 16:03 xunil

已发到你的邮箱里了!呵呵  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2024年11月>
272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567

导航

统计

常用链接

留言簿

随笔档案

文章分类

文章档案

相册

收藏夹

搜索

最新评论

阅读排行榜

评论排行榜