bzoj1833 digit

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

这道题其实挺水，只是写的时候需要想清楚。我的方法是：

1.将[a,b]转化为[0,b+1)-[0,a)

2.预处理出非0的v在区间[0,10^p)出现次数以及0在区间[0,10^p)出现数

3.将一个区间再拆分为几段，如：

12345拆分为[0,10000),[10000,12000),[12000,12300),[12300,12340),[12340,12346)

下面是代码:

 #include<cstdio>

 using namespace std ; 

 static class digit {

     long long pow10 [  ] ;

     long long cnt [  ] ;

     long long cnt0 [  ] ;

 public :

     digit () {

         long long k =  ;

         for ( int i =  ; i <=  ; ++ i ) {

             pow10 [ i ] = k ;

             k *=  ;

         }

         cnt0 [  ] =  ;

         for ( int i =  ; i <=  ; ++ i ) {

             cnt [ i ] = pow10 [ i -  ] + cnt [ i -  ] *  ;

             //printf ( "%lld\n" , cnt [ i ] ) ;

             cnt0 [ i ] = cnt [ i -  ] *  + cnt0 [ i -  ] ;

             //printf ( "%lld\n" , cnt0 [ i ] ) ;

         }

     }

     long long operator () ( long long x , const int v ) {

         x +=  ;

         int w = - ; while ( pow10 [ ++ w ] < x ) ;

         int c =  ; long long ans =  ;

         if ( v ==  ) {

             ans += cnt [ w ] * ( x / pow10 [ w ] -  ) + cnt0 [ w ] ;

             x %= pow10 [ w -- ] ;

         }

         while ( x ) {

             ans += c * ( x / pow10 [ w ] * pow10 [ w ] ) + cnt [ w ] * ( x / pow10 [ w ] ) + ( x / pow10 [ w ] > v ? pow10 [ w ] :  ) ;

             c += ( x / pow10 [ w ] == v ) ;

             x %= pow10 [ w -- ] ;

         }

         return ans ;

     }

 } DIGIT ;

 long long a , b ;

 int main () {

     scanf ( "%lld%lld" , & a , & b ) ;

     printf ( "%lld" , DIGIT ( b ,  ) - DIGIT ( a -  ,  ) ) ;

     for ( int i =  ; i <  ; ++ i ) printf ( " %lld" , DIGIT ( b , i ) - DIGIT ( a -  , i ) ) ;

     putchar ( '\n' ) ;

     return  ;

 }