This page looks best with JavaScript enabled

「ZJOI2010」数字计数-数位dp

 ·  ✏️ About  685 words  ·  ☕ 2 mins read · 👀... views

给定两个正整数 $a$ 和 $b$ ,求在 $[a,b]$ 中的所有整数中,每个数码(digit)各出现了多少次。

链接

Luogu P2602

题解

比较入门的数位dp…很适合我这种蒟蒻。

令 $dp[i][j]$ 为当倒数第 $i$ 位为 $j$ 时,后 $i$ 位的数码总计(一个储存着十个整数的结构体,加减即为对位加减)。若 $j=10$ ,则代表这位是前导 $0$ 。(感觉这个搞法有点笨拙…巨佬能不能教教我…)

令 $sum(i,j)$ 为有 $i$ 数码有 $j$ 个,其他均为 $0$ 的状态。

则状态转移方程为:

$$dp[1][j] = sum(j,1)$$

$$dp[i][j] = sum(j,10^{i-1}) + \sum_{w = 0}^{9} dp[i-1][w]; ,0\leq j \leq 9$$

$$dp[i][10] = \sum_{w = 1}^{10} dp[i-1][w]$$

计算答案时,这个实在不太好说…看代码的注释会更好理解…

代码

 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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <cstdio>
using namespace std;
#define ll long long 

ll a,b;

const int MAXN = 20;

struct sum{
    ll num[10];
    sum(int pos = -1,ll d = 1){
        for(int i = 0;i<10;i++) num[i] = 0;
        if(~pos)
            num[pos] = d;
    }
    sum operator +(const sum a)const{
        sum ans = sum();
        for(int i = 0;i<=9;i++)
            ans.num[i] = this->num[i] + a.num[i];
        return ans;
    }
    sum operator *(const int a)const{
        sum ans = sum();
        for(int i = 0;i<=9;i++)
            ans.num[i] = this->num[i] * a;
        return ans;
    }
    sum operator -(const sum a)const{
        sum ans = sum();
        for(int i = 0;i<=9;i++)
            ans.num[i] = this->num[i] - a.num[i];
        return ans;
    }
};

sum dp[MAXN][MAXN];
ll t[MAXN];
//dp[i][j] -> 后i位,倒数第i位为j,j == 10 代表为先导0

void init(){
    scanf("%lld %lld",&a,&b);
    t[0] = 1;
    for(int i = 1;i<=15;i++)
        t[i] = 10*t[i-1];
}

void build(){
    for(int j = 0;j<=9;j++)
        dp[1][j] = sum(j,1); 
    for(int i = 2;i<=15;i++){
        for(int j = 0;j<=9;j++){
            dp[i][j] = sum(j,t[i-1]);
            for(int w = 0;w<=9;w++)
                dp[i][j] = dp[i][j] + dp[i-1][w];
        }
        dp[i][10] = sum();
        for(int w = 1;w<=10;w++)
            dp[i][10] = dp[i][10] + dp[i-1][w]; 
    }
}

sum getnum(ll a){
    ll tmp = a;
    sum ans = sum(0,1);
    if(a == 0) return sum(0,1);
    int num[15],cnt = 0;
    while(a){
        num[++cnt] = a % 10;
        a/=10;
    }
    ans = ans + dp[cnt][10] - dp[cnt][0];
    //加上在这一位有前导0,再除去在这一位是0的
    for(int i = cnt;i>=1;--i){
        for(int j = 0;j<num[i];++j)
            ans = ans + dp[i][j];
        //加上所有比当前位置小的数的数码
        ans = ans + sum(num[i],tmp%t[i-1]+1);
        //补上后面的数中不再计算的这一位的数码
    }
    return ans;
}

void solve(){
    sum ans = getnum(b)-getnum(a-1);
    for(int i = 0;i<=9;i++){
        printf("%lld ",ans.num[i]);
    }
    printf("\n");
}

int main(){
    init();
    build();
    solve();
    return 0;
}

cqqqwq
WRITTEN BY
cqqqwq
A student in Computer Science.

评论: