poj 2282 The Counting Problem & 3286 How many 0's?-白红宇

poj 2282 The Counting Problem & 3286 How many 0's?

阅读量：7228 次

发布时间：2019-06-29

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

这是一个组合数学题：

我就拿3124来做例子：我们要举出2的个数；

我们是从地位向高位列举：当我们拿个位时，我们就把个位变成2，那么前面有多少个数，那么就有多少个2,前面有0~312共有313个数；

我们在列举十位：2前面有0~30个数可取，个位就可以取0~10，所以共有31*10个，当前面是31时，2可以为0,1,2,3，共有4个数；总共有31*10 + 4；

我们在列举百位：1前面可以去0~2共有3个数，这是百位可以取2，（总是比3124小）后面可以去任意的数前面可以取3*100个，当取3时，那么后面不要算了，总共为3*100，因为1小于2；

有些人就会问一个为题就是2122是当取个位时有这个数，取十位，百位也有这个数，2122有3个2那么我们也是计算3次呀，因此，就没重复计算；

这里要注意就是取0是，前面不能全部为0；

How many 0's?：

View Code

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             #include
              
               #include
               
                #include
                
                 #define LL long longusing namespace std;__int64 num[12] = {1LL,10LL,100LL,1000LL,10000LL,100000LL,1000000LL,10000000LL,100000000LL,1000000000LL,10000000000LL,100000000000LL};LL Solve( LL n ){ LL sum = 0,left,a; for( int i = 1 ; i < 12 ; i ++ ) { left = n / num[i] - 1; sum += left * num[i-1]; a = ( n % num[i] - n % num[i-1] )/num[i-1]; if( a > 0 ) sum += num[i-1]; else if( a == 0 ) sum += n%num[i-1] + 1; if( n < num[i] ) break; } return sum;}int main( ){ LL n,m; while( scanf( "%I64d %I64d",&m,&n ),n!=-1||m!=-1 ) { printf( "%I64d\n",Solve( n ) - Solve( m - 1 ) ); } //system( "pause" ); return 0;}

The Counting Problem：

View Code

View Code #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             #include
              
               #include
               
                #include
                
                 #define LL long longusing namespace std;LL num[12]={1LL,10LL,100LL,1000LL,10000LL,100000LL,1000000LL,10000000LL,100000000LL,1000000000LL,10000000000LL,100000000000LL};LL Solve( LL n , int d ){ LL sum = 0,left,a; for( int i = 1 ; i < 12 ; i ++ ) { left = n / num[i] - ( d == 0 ); sum += left*num[i-1]; a = ( n % num[i] - n%num[i-1] )/num[i-1]; if( a > d ) sum += num[i-1]; else if( a == d ) sum += n%num[i-1] +1; if( n < num[i] ) break; } return sum;}int main( ){ LL n,m; while( scanf( "%I64d %I64d",&n,&m ),n||m ) { if( m > n ) swap( n ,m ); for( int i = 0; i <= 9 ; i ++ ) printf( "%I64d ",Solve( n , i ) - Solve( m - 1 ,i ) ); puts( "" ); } //system( "pause" ); return 0;}

转载于:https://www.cnblogs.com/bo-tao/archive/2012/08/09/2629794.html

你可能感兴趣的文章