poj - 3899 - The Lucky Numbers 시 뮬 레이 션 + 수학

제목 링크:
http://poj.org/problem?id=3899
제목:
주어진 구간 내 에 4, 7 의 개수 만 포함 하고 반전 을 통 해 이 구간 내 개수 와 합 을 구하 십시오.
문제 풀이 방향:
시 뮬 레이 션 + 수학.
코드 설명 이 상세 하 니 코드 를 보 세 요.
 

#include<iostream>

#include<cmath>

#include<cstdio>

#include<cstdlib>

#include<string>

#include<cstring>

#include<algorithm>

#include<vector>

#include<map>

#include<set>

#include<stack>

#include<list>

#include<queue>

#define eps 1e-6

#define INF 0x1f1f1f1f

#define PI acos(-1.0)

#define ll __int64

#define lson l,m,(rt<<1)

#define rson m+1,r,(rt<<1)|1

using namespace std;



/*

freopen("data.in","r",stdin);

freopen("data.out","w",stdout);

*/

char A[50],B[50];

//g1(a,b,len)   1-a    b lucky ，  len b   

//g2(a,b)  1-a      b lucky 

//A-B    lucky     g1(B,0,0)-g1(A-1,0,0)

//    A-B    lucky   g2(A,A)-g2(A,B)+g2(B,B)-g2(A,B)



ll g1(char * a,char * b,int len)

{

   int alen=strlen(a);

   ll res=0;

   bool ism=false;



   for(int i=0;i<len;i++) //  a  len  b   ，>=

   {

      int j=i+alen-len;

      if(a[j]>b[i])

         break;

      else if(a[j]<b[i])

      {

         ism=true;

         break;

      }

   }

   if(len==0)  //     alen    lucky 

   {

      for(int i=1;i<alen;i++)

         res+=(ll)1<<i;  //i      2^i lucky 

   }//  len!=0      m    1-m，          

   int m=alen-len; //   a    lucky 

   int i;

   for(i=0;i<m;i++) //          

   {

      if(a[i]>'7') //4 7   

      {

         res+=(ll)1<<(m-i);

         break;

      }

      else if(a[i]=='7') //4    ，7     

         res+=(ll)1<<(m-i-1);//  4       ，    7   

      else if(a[i]>'4'&&a[i]<'7')

      {

         res+=(ll)1<<(m-i-1); // 4   ,      

         break;

      }

      else if(a[i]<'4')

         break;

   }

   if((i==m)&&!ism) //      

      res++;

   return res;

}



ll g2(char * a,char * b) //1-a  ，     b lucky 

{  //b      >=a   

    int alen=strlen(a);

    char tmp[50],*last=&tmp[49];  //    

    ll res=0;



    for(int i=0;i<alen;i++)

    {

       if(b[i]>'7')  //      7 ,       

         break ;

       else if(b[i]=='7') //    

            *(last--)='7';

       else if(b[i]>'4'&&b[i]<'7') //     

       {

          *last='7'; //           7，        

          res+=g1(a,last,i+1);

          break;

       }

       else if(b[i]=='4')

       {

          *last='7';

          res+=g1(a,last,i+1); //    7,       

          *(last--)='4'; //     4      

       }

       else

       {

          *last='7'; //   7，      

          res+=g1(a,last,i+1);

          *last='4'; //   4，      

          res+=g1(a,last,i+1);

          break;

       }

    }

    //         ，          

    return res;

}



int main()

{

   int  t;



   char aa[4]="999",bb[2]="7";

   printf("%I64d
",g1(aa,bb,1));



   scanf("%d",&t);

   while(t--)

   {

      scanf("%s%s",A,B);

      int lea=strlen(A),leb=strlen(B);



      if(A[lea-1]!='0')

         --A[lea-1]; //         

      ll ans=0;

      ans+=(g1(B,NULL,0)-g1(A,NULL,0)+g2(A,A)+g2(B,B));

      if(lea==leb)

         ans-=(2*g2(A,B));

      printf("%I64d
",ans);



   }

   return 0;

}