洛谷 P2602 [ZJOI2010]数字计数

题目传送门

解题思路:

在搜的时候,出现个数作为一个参量,实时更新,到时直接传就行

AC代码:

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<cmath>
 5 
 6 using namespace std;
 7 
 8 long long a,b,ansa,ansb;
 9 long long len,s[20],f[20][2][20][2];
10 
11 inline long long dfs(int d,bool li,int p,bool qd,int sum) {
12     if(d > len) return sum;
13     if(f[d][qd][sum][li] != -1)
14         return f[d][qd][sum][li];
15     long long ss = 0;
16     int res = li ? s[len-d+1] : 9;
17     for(int i = 0;i <= res; i++)
18         ss += dfs(d + 1,li && (i == res),p,qd && (i == 0),sum + ((!qd || i) && (i == p)));    
19     f[d][qd][sum][li] = ss;
20     return ss;
21 }
22 
23 inline long long solve(long long x,int o) {
24     len = 0;
25     while(x) {
26         s[++len] = x % 10;
27         x /= 10;
28     }
29     memset(f,-1,sizeof(f));
30     return dfs(1,1,o,1,0);
31 }
32 
33 int main() {
34     scanf("%lld%lld",&a,&b);
35     for(int j = 0;j <= 9; j++) {
36         ansa = solve(b,j);
37         ansb = solve(a - 1,j);
38         printf("%lld ",ansa - ansb);
39     }
40     return 0;
41 }