ZROI#1000-白红宇

ZROI#1000

阅读量：5288 次

发布时间：2019-06-14

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

第一印象:啊,数位\(DP\),第一题这么清爽吗(内心\(:mmp\)).不过,这应该可以数位\(DP\)吧...不知道不知道,没想.

冷静思考\(\times 1\):对于线性的好像可以前缀和,因为这玩意儿非常稀疏,判定合法的\(log\)完全可以不管.

冷静思考\(\times 2\):抛弃什么数位\(DP\),这题是不是枚举位数+枚举与其他位不相同的数是啥+枚举它在哪+枚举其他位是啥就行了?

算一算复杂度\(:\Theta(17^2\times 9^2)\).哎呀,过了啊.写写写:

\(Code:\)

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #include 
               
                #define MEM(x,y) memset ( x , y , sizeof ( x ) )#define rep(i,a,b) for (int i = (a) ; i <= (b) ; ++ i)#define per(i,a,b) for (int i = (a) ; i >= (b) ; -- i)#define pii pair < int , int >#define X first#define Y second#define rint read
                
                 #define int long long#define pb push_backusing std::queue ;using std::set ;using std::pair ;using std::max ;using std::min ;using std::priority_queue ;using std::vector ;using std::swap ;using std::sort ;using std::unique ;using std::greater ;template < class T > inline T read () { T x = 0 , f = 1 ; char ch = getchar () ; while ( ch < '0' || ch > '9' ) { if ( ch == '-' ) f = - 1 ; ch = getchar () ; } while ( ch >= '0' && ch <= '9' ) { x = ( x << 3 ) + ( x << 1 ) + ( ch - 48 ) ; ch = getchar () ; } return f * x ;}int l , r , ans ;inline bool check (int x , int cmp) { int cnt = 0 ; while ( x ) ++ cnt , x /= 10 ; return cnt == cmp ;}signed main (int argc , char * argv[]) { l = rint () ; r = rint () ; rep ( i , 1 , 17 ) rep ( b , 1 , i ) rep ( j , 0 , 9 ) rep ( k , 0 , 9 ) { if ( j == k ) continue ; int res = 0 ; rep ( w , 1 , b - 1 ) res = res * 10 + k ; res = res * 10 + j ; rep ( w , b + 1 , i ) res = res * 10 + k ; if ( ! check ( res , i ) ) continue ; if ( res >= l && res <= r ) ++ ans ; } printf ("%lld\n" , ans ) ; return 0 ;}