1193 Eason

Eason

Acceteped : 57		Submit : 129
Time Limit : 1000 MS		Memory Limit : 65536 KB

Description
题目描述 Eason是个非常迷信的人，他喜欢数字3和6，不喜欢4和7。如果一个数字的数码中没有4和7，而有3或者6的话，他就会喜欢这个数字。比如，他会喜欢13,36，但是不会喜欢14,34。但对于28这种的，他就无所谓喜欢还是不喜欢。 Eason想知道区间[a,b]中一共有多少个他喜欢和不喜欢的数字？输入每行输入一个样例，为a和b,0≤a≤b≤10⁶。如果a和b都为0，那么输入结束，这个样例不需要处理。输出每行输出一个样例的结果，先输出喜欢数字的个数，再输出不喜欢数字的个数。样例输入 1 10 1 100 1 1000000 0 0 样例输出 2 2 28 36 215488 737856

Sample Input


Sample Output


Source

解题：暴力或者数位dp乱搞

先上暴力的解法：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <algorithm>

 #include <climits>

 #include <vector>

 #include <queue>

 #include <cstdlib>

 #include <string>

 #include <set>

 #include <stack>

 #define LL long long

 #define INF 0x3f3f3f3f

 #define pii pair<int,int>

 using namespace std;

 int ans[],uu[];

 void go(int dep,int cur,int step,bool like,bool ulike){

     if(step > dep || like && ulike) return;

     ans[cur] = like;

     if(!like && !ulike) uu[cur] = ;

     for(int i = step?:; i <= ; ++i)

         go(dep,cur*+i,step+,like||i == ||i == ,ulike||i == ||i == );

 }

 int main(){

     go(,,,false,false);

     uu[] = ;

     for(int i = ; i < ; ++i){

         ans[i] += ans[i-];

         uu[i] += uu[i-];

     }

     int a,b;

     while(scanf("%d %d",&a,&b),a||b){

         int tmp = ans[b]-ans[a-];

         printf("%d %d\n",tmp,(b-a+)-(uu[b]-uu[a-])-tmp);

     }

     return ;

 }

写得比较挫，很多冗余计算。。。后来改了下，起码好看得多了

 #include <cstdio>

 int ans[],uu[],arr[] = {,,,,,,,},a,b;

 bool check[] = {false,false,false,true,false,true};

 void go(int dep,int cur,int step,bool like){

     if(step > dep) return;

     if(like) ans[cur] = ;

     else uu[cur] = ;

     for(int i = step?:; i < ; ++i)

         go(dep,cur*+arr[i],step+,like||check[i]);

 }

 int main(){

     go(,,,false);

     uu[] = ;

     for(int i = ; i < ; ++i){

         ans[i] += ans[i-];

         uu[i] += uu[i-];

     }

     while(scanf("%d %d",&a,&b),a||b){

         int tmp = ans[b]-ans[a-];

         printf("%d %d\n",tmp,(b-a+)-(uu[b]-uu[a-])-tmp);

     }

     return ;

 }

然后是数位dp

 #include <cstdio>

 #include <cstring>

 int dp[][];

 void calc(char *str,int &x,int &y){

     bool xh = false,bxh = false;

     int len = strlen(str);

     static const int cnt[] = {,,,,,,,,,};

     static const int cnt2[] = {,,,,,,,,,};

     for(int i = x = y = ; str[i+]; ++i){

         int p = (str[i] > '') + (str[i] > '');

         if(!bxh){

             if(xh) x += cnt[str[i]-'']*(dp[len-i-][]+dp[len-i-][]);

             else{

                 x += cnt[str[i]-'']*dp[len-i-][] + p*dp[len-i-][];

                 y += cnt2[str[i]-'']*dp[len-i-][];

             }

         }

         if(str[i] == '' || str[i] == '') bxh = true;

         if(str[i] == '' || str[i] == '') xh = true;

     }

     for(int i = ; i <= str[len-]-''; ++i){

         if(!xh && !bxh &&(i ==  || i == )) ++x;

         if(xh && !bxh && i !=  && i != ) ++x;

         if(!bxh && !xh && i !=  && i !=  && i !=  && i != ) ++y;

     }

 }

 int main(){

     dp[][] = ;

     dp[][] = ;

     for(int i = ; i <= ; ++i){

         dp[i][] = (dp[i-][]<<) + (dp[i-][]<<);

         dp[i][] = *dp[i-][];

     }

     char str[];

     int a,b;

     while(scanf("%d %d",&a,&b),a||b) {

         int x,y,x1,y1;

         sprintf(str,"%d",--a);

         calc(str,x,y);

         sprintf(str,"%d",b);

         calc(str,x1,y1);

         int tmp = x1 - x;

         printf("%d %d\n",tmp,b-a-tmp-y1+y);

     }

     return ;

 }

巴特西

1193 Eason

Eason

Description

题目描述

输入

输出

样例输入

样例输出

Sample Input

Sample Output

Source

最新文章

热门文章