首页 > 代码库 > HDU P2089

HDU P2089

2024-09-03 01:14:49   216人阅读

题目大意为，统计区间内不含4和62的数字的个数；

老实说，看到这题我是抵触的。。。。。

基本上是数位DP的板子，话说数位DP好像全是模板题吧；

预处理，有关的整区间的数字个数；

调用已有的区间，求解0~左端点，0~右端点，然后作差；

具体有关数位DP的事宜

参见：http://www.cnblogs.com/nietzsche-oier/p/6363315.html

代码如下：

 1 #include<cstdio> 2 #include<cmath> 3 using namespace std; 4 int f[8][10]; 5  6 int work(int); 7  8 int main() 9 {10     int n,m,ans=0,i,j,k;11     f[0][0]=1;12     for(k=1;k<=7;k++)13     for(i=0;i<=9;i++)14         if(i!=4)15             for(j=0;j<=9;j++)16                 if(i!=6||j!=2)17                     f[k][i]+=f[k-1][j];18     while(scanf("%d%d",&n,&m)==2&&m||n){19         ans=work(m);20         ans=ans-work(n-1);21         if(m<n)ans=0;22         printf("%d\n",ans);23     }24 }25 26 int work(int x)27 {28     int i,j,k,y=0,sum=0,z=0;29     if(x==0)return 1;30     int len=(int)log10(x)+1;31     int mod=1;32     for(i=1;i<=len-1;i++)33         mod*=10;34     for(k=len;k>=1;k--){35         y=x/mod;36         x%=mod;37         if(z!=4)38             for(i=0;i<y;i++)39                 if(z!=6||i!=2)40                     sum+=f[k][i];41         if(k==1&&y!=4&&z!=4&&(z!=6||y!=2))42             sum++;43         if(y==4||(z==6&&y==2))break;44         z=y;45         mod/=10;46     }47     return sum;48 }

祝AC哟；

 

HDU P2089


联系
我们