首页 > 代码库 > NOIP模拟赛 准考证号
NOIP模拟赛 准考证号
准考证号 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 else33 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 else47 {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 }
NOIP模拟赛 准考证号
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。