poj-3899-The Lucky Numbers 模擬+數學

題目意思：   求給定區間內，只含4、7的數的個數以及通過反轉後在該區間內的個數和。   解題思路：   模擬+數學。   代碼解釋的很詳細，請看代碼。

<SPAN style="FONT-SIZE: 18px">#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\n",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\n",ans);

   }
   return 0;
}




</SPAN>