首页 > 代码库 > 2014.12.13模拟赛【准考证号】
2014.12.13模拟赛【准考证号】
准考证号 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 。
数位dp
无非是f[i][j]表示i位的数第一位是j的方案数，然后乱搞
我真是太弱了……黄巨大说我写代码的风格跟**一样
#include<cstdio>#include<iostream>#include<cstring>#include<cstdlib>#include<algorithm>#include<cmath>#include<queue>#include<deque>#include<set>#include<map>#include<ctime>#define LL long long#define inf 0x7ffffff#define pa pair<int,int>#define pi 3.1415926535897932384626433832795028841971using namespace std;inline LL read(){ LL x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f;}int f[20][10];LL a,b;LL sec[20];inline void pre(){ sec[0]=1;for (int i=1;i<=15;i++)sec[i]=sec[i-1]*10; f[1][4]=1; for (int i=2;i<=12;i++) { for (int j=0;j<=9;j++) { for (int k=0;k<=9;k++) f[i][j]+=f[i-1][k]; } f[i][3]+=sec[i-2]-f[i-1][7]; f[i][4]=sec[i-1]; }}inline LL calc(LL x){ if (x<1)return 0; int dig[20]={0},len=0; LL tot=0,dat=x; while (x) { dig[++len]=x%10; x/=10; } while (len) { for (int i=0;i<dig[len];i++)tot+=(LL)f[len][i]; if (dig[len]==4) { tot+=(LL)dat%sec[len-1]+1; break; } if (dig[len+1]==3&&dig[len]==7) { tot+=(LL)dat%sec[len-1]+1; break; } if (dig[len+1]==3&&dig[len]>7) { tot-=(LL)f[len][7]; tot+=sec[len-1]; } len--; } return dat-tot;}int main(){ freopen("ticket.in","r",stdin); freopen("ticket.out","w",stdout); pre(); a=read();b=read(); printf("%d\n",calc(b)-calc(a-1)); return 0;}
2014.12.13模拟赛【准考证号】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。