poj 3909-白红宇

poj 3909

阅读量：7288 次

发布时间：2019-06-30

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

我的wa代码 wa到吐血，找不到错。

View Code

1 #include
      
         2 #include
       
          3 #include
        
           4 using namespace std;  5 __int64 num[1000000],sum,cnt;  6 const __int64 maxn=1000000000100;  7 void dfs(__int64 u,__int64 d)  8 {
     9     if(d>12) return; 10     dfs(num[sum++]=u*10+4,d+1); 11     dfs(num[sum++]=u*10+7,d+1); 12 } 13 void Dfs(__int64 t,int pos) 14 {
    15     for(int i=pos;i
         
          0&&tem<=maxn) {
    19             num[cnt++]=tem; 20             Dfs(tem,i); 21         } 22         else break; 23     } 24 } 25 void init() 26 {
    27     sum=0; 28     dfs(0,1);cnt=sum; 29     sort(num,num+cnt); 30     Dfs(1,0); 31     sort(num,num+cnt); 32     cnt=unique(num,num+cnt)-num; 33     num[cnt]=maxn+1; 34 } 35 __int64 sch(__int64 u) 36 {
    37     __int64 low=0,high=cnt,mid; 38     while(low
          
           >1; 41         if(num[mid]
           
            u) high=mid-1; 44 else {high=low=mid; break;} 45 } 46 mid=(high+low)>>1; 47 if(num[mid]!=u) 48 return mid-1; 49 else return mid; 50 } 51 int main() 52 { 53 init();__int64 cas,x,y; 54 scanf("%I64d",&cas); 55 while(cas--) 56 { 57 scanf("%I64d%I64d",&x,&y); 58 printf("%I64d\n",sch(y)-sch(x-1)); 59 } 60 return 0; 61 }

网上大牛解法：类似，不过运用了vector

View Code

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 using namespace std;  7 typedef  __int64 lld;  8 vector
           
             lu,res; 9 int tot; 10 void dfs(lld num,int de){ 11 if(de==12) return ; 12 lu.push_back(num); 13 dfs(num*10+4,de+1); 14 dfs(num*10+7,de+1); 15 } 16 void dfs1(int x,lld num){ 17 for(int i=x;i

ac代码：

View Code

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 using namespace std;  6 vector<__int64>num;  7 __int64 sum,cnt;  8 const __int64 maxn=1000000000100;  9 void dfs(__int64 u,__int64 d) 10 {
    11     if(d>12) return; 12     num.push_back(u*10+4); 13     num.push_back(u*10+7); 14     dfs(u*10+4,d+1); 15     dfs(u*10+7,d+1); 16 } 17 void Dfs(__int64 t,int pos) 18 {
    19     for(int i=pos;i
          
           0&&tem<=maxn) {
    23             num.push_back(tem); 24             Dfs(tem,i); 25         } 26         else break; 27     } 28 } 29 void init() 30 {
    31     num.clear(); 32     dfs(0,1);sum=num.size(); 33     sort(num.begin(),num.end()); 34     Dfs(1,0); 35     sort(num.begin(),num.end()); 36     cnt=unique(num.begin(),num.end())-num.begin(); 37 } 38 int main() 39 {
    40     init();__int64 cas,x,y; 41     scanf("%I64d",&cas); 42     while(cas--) 43     {
    44         scanf("%I64d%I64d",&x,&y); 45         int l=lower_bound(num.begin(),num.begin()+cnt,x)-num.begin(); 46         int r=upper_bound(num.begin(),num.begin()+cnt,y)-num.begin(); 47         printf("%d\n",r-l); 48     } 49     return 0; 50 }

终于a掉了：

View Code

1 #include
      
         2 #include
       
          3 #include
        
           4 using namespace std;  5 __int64 num[1000000],sum,cnt;  6 const __int64 maxn=1000000000100;  7 void dfs(__int64 u,__int64 d)  8 {
     9     if(d>12) return; 10     dfs(num[sum++]=u*10+4,d+1); 11     dfs(num[sum++]=u*10+7,d+1); 12 } 13 void Dfs(__int64 t,int pos) 14 {
    15     for(int i=pos;i
         
          0&&tem<=maxn) {
    19             num[cnt++]=tem; 20             Dfs(tem,i); 21         } 22         else break; 23     } 24 } 25 void init() 26 {
    27     sum=0; 28     dfs(0,1);cnt=sum; 29     sort(num,num+cnt); 30     Dfs(1,0); 31     sort(num,num+cnt); 32     cnt=unique(num,num+cnt)-num; 33     num[cnt]=maxn+1; 34 } 35 __int64 sch(__int64 u) 36 {
    37     __int64 low=0,high=cnt,mid; 38     while(low
          
           >1; 41         if(num[mid]
           
            u) high=mid-1; 44 else {high=low=mid; break;} 45 } 46 mid=(high+low)>>1; 47 if(num[mid]>u) 48 return mid-1; 49 else return mid; 50 } 51 int main() 52 { 53 init();__int64 cas,x,y; 54 scanf("%I64d",&cas); 55 while(cas--) 56 { 57 scanf("%I64d%I64d",&x,&y); 58 printf("%I64d\n",sch(y)-sch(x-1)); 59 } 60 return 0; 61 }