CF1036C Classy Numbers dfs+二分-白红宇

CF1036C Classy Numbers dfs+二分

阅读量：6840 次

发布时间：2019-06-26

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

Let's call some positive integer classy if its decimal representation contains no more than $33 non-zero digits. For example, numbers 44, 200000200000, 1020310203 are classy and numbers 42314231, 102306102306, 72774200007277420000 are not.$

You are given a segment $[L;R][L;R]. Count the number of classy integers xx such that L\leqx\leqRL\leqx\leqR.$

Each testcase contains several segments, for each of them you are required to solve the problem separately.

Input

The first line contains a single integer $TT (1\leqT\leq1041\leqT\leq104) — the number of segments in a testcase.$

Each of the next $TT lines contains two integers LiLi and RiRi (1\leqLi\leqRi\leq10181\leqLi\leqRi\leq1018).$

Output

Print $TT lines — the ii-th line should contain the number of classy integers on a segment [Li;Ri][Li;Ri].$

Example

input

Copy

4 1 1000 1024 1024 65536 65536 999999 1000001

output

Copy

1000 1 0 2

题意：classy数：一个数的不为0的位数不超过三位，问你le到ri范围内有多少个classy数？

分析：考虑le和ri的范围为10^18，这之间满足条件的classy数不超过一百万（自己暴搜计算一下），将这些数存进数组里，排下序找出le的位置和ri的位置，相减就可以得出中间classy数的多少

AC代码：

#include #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      #define ls (r<<1)#define rs (r<<1|1)#define debug(a) cout << #a << " " << a << endlusing namespace std;typedef long long ll;const ll maxn = 1e5+10;const ll mod = 2e9+7;const double pi = acos(-1.0);const double eps = 1e-8;vector
                      
                        v;void dfs( ll dep, ll res, ll n ) { //dep表示现在这个数是第几位，res表示现在这个数的大小，n表示res中不为0的位数 v.push_back(res); if( dep == 18 ) { return ; } dfs(dep+1,res*10,n); if( n < 3 ) { for( ll i = 1; i <= 9; i ++ ) { dfs(dep+1,res*10+i,n+1); } }}int main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); ll T, le, ri; for( ll i = 1; i <= 9; i ++ ) { dfs(1,i,1); } v.push_back(1e18); sort(v.begin(),v.end()); //排序数组 //debug(v.size()); cin >> T; while( T -- ) { cin >> le >> ri; cout << upper_bound(v.begin(),v.end(),ri)-lower_bound(v.begin(),v.end(),le) << endl; //二分查找 } return 0;}

转载于:https://www.cnblogs.com/l609929321/p/9628817.html

你可能感兴趣的文章