解题思路:
这题第一次做的时候,因为数据范围小,只有10^6,所以果断选择了暴力打表。在够表的时候,一开始少了a[i/10]==1这个条件,算出来的值总是多,,
然后加上后,扫一遍就过。
先看看暴力的代码吧.
# include<cstdio> # include<iostream> # include<cstring> using namespace std; # define MAX 1000000+4 int a[MAX]; void init() { a[0] = 1; for ( int i = 1;i <= MAX;i++ ) { if ( ( i%10!=4 )&&( i%100!=62 )&&a[i/10]==1 ) { a[i] = 1; } else { a[i] = 0; } } } int main(void) { int n,m; init(); while ( cin>>n>>m ) { int ans = 0; if (n==0&&m==0) break; for ( int i = n;i <= m;i++ ) { if ( a[i]==1 ) { ans++; } } cout<<ans<<endl; } return 0; }
这几天刚好开始搞数位dp,所以,顺便把这道题用数位dp,重新写一下,感觉数位dp就是快。有关数位dp的学习,初学者我推荐从这个课件学起来,写的很好,,
好了, 来分析下什么是数位dp了。
数位dp就是说,对于那种要求在一个区间上进行操作的问题的求解,但是我们无法用暴力,因为暴力会T,区间的跨度往往是很大的。那么我们就需要借助每一个数位之间的递推关系来得到最终的结果,而不是蛮力的搜索。。。
而在进行数位dp开始的时候,我们必须要进行预处理的工作,就是枚举0~9是每一位数的可能,比如说,让我们统计在[L,R]中满足题意的数的个数有几个的时候,我们就可以通过求解[0,R]和[0,L-1]这两个区间中满足题意的数字的个数,然后做差就好了。通过这个,我们就可以得到[0,n]的通用方法了。
对于一个小于n的数,肯定是从高位到低位出现某一位<n对应的那一位。
如 n = 58 n为十进制数。
x = 49 此时x的十位<n的十位
x = 51 此时x的个位<n的个位
有了上述性质,我们就可以从高到低枚举第一次<n对应位是哪一位。这样之前的位确定了,之后的位就不受n的限制即从00...0~99...9,可以先预处理,然后这时就可以直接统计答案。
代码:
# include<cstdio> # include<iostream> # include<cstring> using namespace std; int dp[8][10];//dp[i][j]表示的是以j开头的i位数中,不含4和62的个数 int digit[10]; void init() { memset(dp,0,sizeof(dp)); dp[0][0] = 1; for ( int i = 1;i <= 7;i++ ) { for ( int j = 0;j <= 9;j++ ) {//枚举第i位 for ( int k = 0;k <= 9;k++ ) {//枚举第i-1位 if ( j!=4&&(!( j==6&&k==2 ))) { dp[i][j] = dp[i][j] + dp[i-1][k]; } } } } } int cal ( int n ) { int len = 0; int ans = 0; while ( n!=0 ) { digit[++len] = n%10; n = n / 10; } digit[len+1] = 0; for ( int i = len;i >=1 ;i-- ) { for ( int j = 0;j < digit[i];j++ ) { if ( j!=4&&(!(digit[i+1]==6&&j==2 )) ) { ans+=dp[i][j]; } } if ( digit[i]==4||( digit[i]==2&&digit[i+1]==6 )) { break; } } return ans; } int main(void) { int n,m; while ( cin>>n>>m ) { if ( n==0&&m==0 ) break; init(); printf("%d\n",cal(m+1)-cal(n)); } return 0; }