解题思路: 对于这道题,猛一看到脑袋里出现的就是暴力的做法,当然不能这样,会TLE。 打表是一定要打的。但是如何打的优美就是一个值得思考的问题了。这里我了解到一个很好的找数字里面有无62或4的方法。 我们可以将数字 n 用 itoa 函数转换成字符串,然后用查询子串的方法找 n 中是否含有62、4。 说到打表,我们可以建立一个数组dp[n],来记录从1~n中出现62、4的数字。但是要注意一点的是,如果n中即包含62又包含4,那么我们这里还是只统计一次的。 代码:
1 #include<math.h> 2 #include<ctype.h> 3 #include<stdlib.h> 4 #include<stdio.h> 5 #include<string.h> 6 #include<limits.h> 7 #include<stdlib.h> 8 9 #define N 100010 10 #define fl 0x555555555 11 12 typedef long long int ll; 13 14 int dp[1000010]; 15 char num[1000010]; 16 int main() 17 { 18 int n, m; 19 int i; 20 memset(dp, 0, sizeof(dp)); 21 for(i=1;i<=1000000;i++) 22 { 23 itoa(i, num, 10); 24 dp[i]=dp[i-1]; //将i前一个数字的统计值存入dp[i],以便后续的使用 25 if(strstr(num, "4")!=NULL) 26 dp[i]+=1; 27 else if(strstr(num, "62")!=NULL) //如果字符串中已经出现过4的话就跳过这个语句了 28 dp[i]+=1; 29 } 30 while(scanf("%d%d", &n, &m), n||m ) 31 { 32 printf("%d\n", (m-n+1)-(dp[m]-dp[n-1])); //输出n~m中不含4、62的数字的个数 33 } 34 return 0; 35 }