数字游戏

[https://vjudge.net/problem/LibreOJ-10164]:

题目大意：
科协里最近很流行数字游戏。

某人命名了一种不降数，这种数字必须满足从左到右各位数字呈非下降关系，如 123，446。

现在大家决定玩一个游戏，指定一个整数闭区间 [a,b]，问这个区间内有多少个不降数。

输入格式
输入包含多组测试数据。

每组数据占一行，包含两个整数 a 和 b。

输出格式
每行给出一组测试数据的答案，即 [a,b] 之间有多少不降数。

数据范围
1≤ a ≤ b ≤2^31−1

解题思路：
f[i][j] 数组代表着最高位是j并且一共有i位不降数的集合
f[i][j] = f[i-1][j] + f[i-1][j+1] + f[i-1][j+2] +…+ f[i-1][9];

按照数位DP分析步骤： 假设我们当前枚举到第i位，且第i位上的数字是x，那么现在对于答案的第i位数字j来说，可以填两类数字：

1.j 取0~x-1 那么res += f[i+1][j];

2.j 取 x last记录x，再枚举下一位

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
#include <bits/stdc++.h>
using namespace std;
const int N = 12;
int a[N];    //存整数的每一位数字
int f[N][N]; // f[i][j]表示一共有i位，且最高为数字是j的不降数的个数
void init()  //预处理不降数的个数
{
    for (int i = 0; i <= 9; i++)
    {
        f[1][i] = 1; //一位数就是1
    }
    for (int i = 2; i < N; i++) //阶段：枚举位数
    {
        for (int j = 0; j <= 9; j++) //状态：枚举最高位
        {
            for (int k = j; k <= 9; k++) //决策：枚举次高位
            {
                f[i][j] += f[i - 1][k]; //累加所有方案数
            }
        }
    }
}
int dp(int n)
{
    if (n == 0) //特判，n=0就一个数字
    {
        return 1;
    }
    int cnt = 0;
    while (n)
    {
        a[++cnt] = n % 10; //从低到高存每一位数
        n /= 10;
    }
    int ans = 0;
    int last = 0;                  // last表示上一位数字
    for (int i = cnt; i >= 1; i--) //从高到低依次枚举
    {
        int now = a[i];                  // now表示当前位数字
        for (int j = last; j < now; j++) //枚举当前为可填入的数字
        {
            ans += f[i][j]; //累加方案数
        }
        if (now < last) //若比上一位小，直接退出
        {
            break;
        }
        last = now; //更新last的值
        if (i == 1) //走到a1时，最后会少加一个右边界数，要加一
        {
            ans++;
        }
    }
    return ans;
}
int main()
{
    init();
    int l, r;
    while (cin >> l >> r)
    {
        printf("%d\n", dp(r) - dp(l - 1));
    }
    return 0;
}

windy数

[https://www.luogu.com.cn/problem/P2657]:

题意：windy定义了一种windy数。

不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。

windy想知道，在A和B之间，包括A和B，总共有多少个windy数？

Input

包含两个整数，A，B。

满足1≤A≤B≤2000000000 .

Sample 1

Input Output
1 10 9 
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
#include <bits/stdc++.h>
using namespace std;
const int N = 12;
int a[N];    //存整数的每一位数字
int f[N][N]; // f[i][j]表示一共有i位，且最高为数字是j的不降数的个数
void init()  //预处理不降数的个数
{
    for (int i = 0; i <= 9; i++)
    {
        f[1][i] = 1; //一位数就是1
    }
    for (int i = 2; i < N; i++) //阶段：枚举位数
    {
        for (int j = 0; j <= 9; j++) //状态：枚举最高位
        {
            for (int k = 0; k <= 9; k++) //决策：枚举次高位
            {
                if (abs(j - k) >= 2)
                {
                    f[i][j] += f[i - 1][k];
                }
            }
        }
    }
}
int dp(int n)
{
    if (n == 0) //特判，n=0就一个数字
    {
        return 0;
    }
    int cnt = 0;
    while (n)
    {
        a[++cnt] = n % 10; //从低到高存每一位数
        n /= 10;
    }
    int ans = 0;
    int last = -2;                 // last表示上一位数字
    for (int i = cnt; i >= 1; i--) //从高到低依次枚举
    {
        int now = a[i];
        for (int j = (i == cnt); j < now; j++)
        {
            if (abs(j - last) >= 2)
            {
                ans += f[i][j];
            }
        }
        if (abs(now - last) < 2) //若比上一位小，直接退出
        {
            break;
        }
        last = now; //更新last的值
        if (i == 1) //走到a1时，最后会少加一个右边界数，要加一
        {
            ans++;
        }
    }
    //前面算的都是cnt位的
    //需要加上小于cnt位的数
    for (int i = 1; i < cnt; i++)
    {
        for (int j = 1; j <= 9; j++) //不能有前导0
        {
            ans += f[i][j];
        }
    }
    return ans;
}
int main()
{
    init();
    int l, r;
    cin >> l >> r;
    printf("%d\n", dp(r) - dp(l - 1));
    return 0;
}

acwing1081：度的数量

img

image-20220920091633855

image-20220920094600561.png

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
#include <bits/stdc++.h>
using namespace std;
const int N = 35;
int a[N];    //把b进制的每一位数存起来
int f[N][N]; // f[i][j]表示在i个位置上，放置j个1的组合数
int k, b;
void init()
{
    for (int i = 0; i < N; i++) //预处理组合数
    {
        f[i][0] = 1;
    }
    for (int i = 1; i < N; i++)
    {
        for (int j = 1; j <= i; j++)
        {
            f[i][j] += f[i - 1][j] + f[i - 1][j - 1];
        }
    }
    // c(j,i)=c(j-1,i-1)+c(j,i-1);
}
int dp(int n)
{
    if (n == 0) //特判，n==0返回0
    {
        return 0;
    }
    int cnt = 0;
    while (n) //把b进制数的每一位存入数组
    {
        a[++cnt] = n % b;
        n /= b;
    }
    int ans = 0, last = 0;         // last表示第i位之前放置的1
    for (int i = cnt; i >= 1; i--) //从高位到低位枚举
    {
        int x = a[i];
        if (x) //第i位==0时，直接跳过，枚举下一位
        {
            ans += f[i - 1][k - last]; //第i位放0
            if (x > 1)
            {
                if (k - (last + 1) >= 0)
                {
                    ans += f[i - 1][k - (last + 1)]; //第i位放1
                    break;                           //第i位放大于1的数，不符合题意，直接退出
                }
            }
            else //第i位等于1时，后面不能用组合数计算，比如65转换成4进制是1001，如果用组合数计算会出现比65大的值，所以应继续向下枚举
            {
                last += 1;
                if (last > k) // 1的个数多于k，则break
                {
                    break;
                }
            }
        }
        if (i == 1 && last == k) //判断末位是否符合题意
        {
            ans++;
        }
    }
    return ans;
}
int main()
{
    init();
    int l, r;
    scanf("%d%d", &l, &r);
    scanf("%d", &k);
    scanf("%d", &b);
    printf("%d\n", dp(r) - dp(l - 1));
    return 0;
}