题意，问1~n 有多少个数含有49.
f[i][0]表示小于等于i位的不含有49数有几个。
f[i][1]表示小于等于i位的含有49的数有几个。
f[i][2]表示小于等于i位的不含有49，但是最高位是9的数有几个。
f[i][0]=f[i-1][0]+f[i-1][0]*9-f[i-1][2]; 第一个f[i-1][0]表示小于i位的所有数。f[i-1][0]*9表示i-1位的数，在第i位有9种可能。也可以理解成最高位可以是0，049就是一个两位数。
f[i][1]=f[i-1][1]*10+f[i-1][2];
f[i][2]=f[i-1][0];
49,049,0049是不是重复算了？是的，是重复算了，但“重叠”是没有关系的。两位的时候49算作一次。三位的时候049算作一次，但是49这个数不算了，已被049替代。
如果n=34549,则可以把n分成几个部分,1~29999, 30000~33999, 34000~34499, 344500~344539, 344540~344548, 344549.
3* f[4][1] + 3*f[3][1] + 4*f[2][1] + 3*f[1][1] +8*f[0][1] 单独计数。
关于这个单独计数，有个tip。作一次n++，(n+1)这次单独计数就不用算了。
如果遇到n=491934，这样，某i位的前两位是49，则后i位是不含有49的也得计入。（即把0000~1933全部计数） ①
如果某i位大于4，则应该把f[i-1][2]也计入。 ②
但是①计入以后， ②就不能计入了。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51 |
#include <stdio.h>#include <string.h>#include <algorithm>using
namespace std;long
long f[100][3];int main(){ int
i,j,m; f[0][0]=1;f[0][1]=0;f[0][2]=0; for
(i=1;i<20;i++) { f[i][0]=f[i-1][0]*10-f[i-1][2];// no 49 f[i][1]=f[i-1][1]*10+f[i-1][2];// have 49 f[i][2]=f[i-1][0]; // zuigaowei 9 & no 49 } int
t; scanf("%d",&t); int
cas; char
a[100]; long
long n; long
long ans=0; for
(cas=0;cas<t;cas++) { ans=0; scanf("%I64d",&n); int
len=0; n++; while
(n>0) { a[++len]=n%10+48; n/=10; } a[len+1]=‘\0‘; a[0]=‘0‘; a[len+1]=‘0‘; a[len+2]=‘0‘; bool
flag=false; for
(i=len;i>=1;i--) { ans+=(long
long )(a[i]-‘0‘)*f[i-1][1]; if
(a[i+2]==‘4‘
&& a[i+1]==‘9‘) flag=true; if
(flag) ans+=(long
long )f[i-1][0]*(a[i]-‘0‘); if
(!flag && a[i]>‘4‘) ans+=(long
long )f[i-1][2]; } printf("%I64d\n",ans); } return
0;} |
原文：http://www.cnblogs.com/six-god/p/3585255.html