准考证号 128M 0.1s ticket.cpp
escription
蒟蒻hzwer NOIP2014惨跪，他依稀记得他的准考证号是37，现在hzwer又将要面临一场比赛，他希望准考证号不出现37（连续），同时他又十分讨厌4，所以也不希望4出现在准考证号中。。。现在他想知道在A和B之间有多少合法的准考证号
Input
包含两个整数，A B
Output
一个整数。
Sample Input
【输入样例一】
1 10
【输入样例二】
25 50
Sample Output
【输出样例一】
9
【输出样例二】
14
【数据规模和约定】
20%的数据，满足 1 <= A <= B <= 1000000 。
100%的数据，满足 1 <= A <= B <= 2000000000 。
F[i][j]表示第i位数字为j的方案数
黄学长原谅我这么弱。。。
1 #include<iostream> 2 using namespace std; 3 4 int A,B; 5 int base[15]; 6 int F[15][10]; 7 8 inline void pre() 9 { 10 base[1]=1; 11 for(int i=2;i<=10;i++) base[i]=base[i-1]*10; 12 for(int i=0;i<10;i++) if(i!=4) F[1][i]=1; 13 for(int i=2;i<=10;i++) 14 for(int j=0;j<10;j++) 15 for(int k=0;k<10;k++) 16 if(j!=4&&k!=4&&(j!=3||k!=7)) 17 F[i][j]+=F[i-1][k]; 18 } 19 20 inline int calc(int x) 21 { 22 if(x==0) return 0; 23 int L=10,pre=0,cur=0,ans=0; 24 while(base[L]>x) L--; 25 for(int i=1;i<L;i++) 26 for(int j=1;j<10;j++) 27 ans+=F[i][j]; 28 cur=x/base[L];x%=base[L]; 29 if(L==1) 30 for(int i=1;i<=cur;i++) 31 ans+=F[L][i]; 32 else 33 for(int i=1;i<cur;i++) 34 ans+=F[L][i]; 35 pre=cur; 36 for(int i=L-1;i;i--) 37 { 38 if(cur==4) break; 39 cur=x/base[i];x%=base[i]; 40 if(i==1) 41 { 42 for(int j=0;j<=cur;j++) 43 if(pre!=3||j!=7) 44 ans+=F[i][j]; 45 } 46 else 47 { 48 for(int j=0;j<cur;j++) 49 if(pre!=3||j!=7) 50 ans+=F[i][j]; 51 } 52 if(pre==3&&cur==7)break; 53 pre=cur; 54 } 55 return ans; 56 } 57 58 int main() 59 { 60 cin>>A>>B; 61 pre(); 62 cout<<calc(B)-calc(A-1); 63 }