首页 > 代码库 > 1193 Eason

1193 Eason

2024-10-30 02:01:39   210人阅读

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≤106。如果a和b都为0，那么输入结束，这个样例不需要处理。

输出

每行输出一个样例的结果，先输出喜欢数字的个数，再输出不喜欢数字的个数。

样例输入

1 10 1 100 1 1000000 0 0

样例输出

2 2 28 36 215488 737856
 

Sample Input

 
 

Sample Output

 
 

Source

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

先上暴力的解法：

技术分享
 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <climits> 7 #include <vector> 8 #include <queue> 9 #include <cstdlib>10 #include <string>11 #include <set>12 #include <stack>13 #define LL long long14 #define INF 0x3f3f3f3f15 #define pii pair<int,int>16 using namespace std;17 int ans[1000001],uu[1000001];18 void go(int dep,int cur,int step,bool like,bool ulike){19     if(step > dep || like && ulike) return;20     ans[cur] = like;21     if(!like && !ulike) uu[cur] = 1;22     for(int i = step?0:1; i <= 9; ++i)23         go(dep,cur*10+i,step+1,like||i == 3||i == 6,ulike||i == 4||i == 7);24 }25 int main(){26     go(6,0,0,false,false);27     uu[1000000] = 1;28     for(int i = 1; i < 1000001; ++i){29         ans[i] += ans[i-1];30         uu[i] += uu[i-1];31     }32     int a,b;33     while(scanf("%d %d",&a,&b),a||b){34         int tmp = ans[b]-ans[a-1];35         printf("%d %d\n",tmp,(b-a+1)-(uu[b]-uu[a-1])-tmp);36     }37     return 0;38 }
View Code

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

技术分享
 1 #include <cstdio> 2 int ans[1000001],uu[1000001],arr[] = {0,1,2,3,5,6,8,9},a,b; 3 bool check[10] = {false,false,false,true,false,true}; 4 void go(int dep,int cur,int step,bool like){ 5     if(step > dep) return; 6     if(like) ans[cur] = 1; 7     else uu[cur] = 1; 8     for(int i = step?0:1; i < 8; ++i) 9         go(dep,cur*10+arr[i],step+1,like||check[i]);10 }11 int main(){12     go(6,0,0,false);13     uu[1000000] = 1;14     for(int i = 1; i < 1000001; ++i){15         ans[i] += ans[i-1];16         uu[i] += uu[i-1];17     }18     while(scanf("%d %d",&a,&b),a||b){19         int tmp = ans[b]-ans[a-1];20         printf("%d %d\n",tmp,(b-a+1)-(uu[b]-uu[a-1])-tmp);21     }22     return 0;23 }
View Code

 

然后是数位dp

技术分享
 1 #include <cstdio> 2 #include <cstring> 3 int dp[10][2]; 4 void calc(char *str,int &x,int &y){ 5     bool xh = false,bxh = false; 6     int len = strlen(str); 7     static const int cnt[10] = {0,1,2,3,4,4,5,6,6,7}; 8     static const int cnt2[10] = {0,1,2,3,3,3,4,4,4,5}; 9     for(int i = x = y = 0; str[i+1]; ++i){10         int p = (str[i] > ‘3‘) + (str[i] > ‘6‘);11         if(!bxh){12             if(xh) x += cnt[str[i]-‘0‘]*(dp[len-i-1][1]+dp[len-i-1][0]);13             else{14                 x += cnt[str[i]-‘0‘]*dp[len-i-1][0] + p*dp[len-i-1][1];15                 y += cnt2[str[i]-‘0‘]*dp[len-i-1][1];16             }17         }18         if(str[i] == ‘4‘ || str[i] == ‘7‘) bxh = true;19         if(str[i] == ‘3‘ || str[i] == ‘6‘) xh = true;20     }21     for(int i = 0; i <= str[len-1]-‘0‘; ++i){22         if(!xh && !bxh &&(i == 3 || i == 6)) ++x;23         if(xh && !bxh && i != 4 && i != 7) ++x;24         if(!bxh && !xh && i != 3 && i != 6 && i != 4 && i != 7) ++y;25     }26 }27 int main(){28     dp[1][0] = 2;29     dp[1][1] = 6;30     for(int i = 2; i <= 6; ++i){31         dp[i][0] = (dp[i-1][0]<<3) + (dp[i-1][1]<<1);32         dp[i][1] = 6*dp[i-1][1];33     }34     char str[10];35     int a,b;36     while(scanf("%d %d",&a,&b),a||b) {37         int x,y,x1,y1;38         sprintf(str,"%d",--a);39         calc(str,x,y);40         sprintf(str,"%d",b);41         calc(str,x1,y1);42         int tmp = x1 - x;43         printf("%d %d\n",tmp,b-a-tmp-y1+y);44     }45     return 0;46 }
View Code

 

1193 Eason


联系
我们