递增数的一种思路

蓝桥杯线上模拟赛—递增数

题目

若一个正整数A，相邻位总是满足低位大于等于高位，则称之为递增数。 例如：1223，667 等都是递增数。
现在有个正整数X，请问有多少个正整数A满足1<=A<=X，且A为递增数。

Input 输入数据一个正整数X(1<=X<=100000000)
Output 对于每个数据，输出一个答案，参见输出样例。

其他方法

赛时感觉题目蛮有意思的，准备赛后写个博客留念，赛后资料的时候找到了一个全排+回溯的算法，意识到或许我的方法不太一样，后面我来说一下我的思路。

思路

首先可以确定暴力一定会超时，然后考虑分段来看。
我考虑的是分 位数和这个位数上的数来看。比如个位上对应1-9，都只有一个递增数（这毫无疑问只有它本身）；10—99之间，十位是1的递增数有9个，是2的递增数有8个……是9的递增数有一个；100-999之间百位是一的递增数有……
其中第一列是这个位数所有递增数之和，后面对应这一位为1-9的递增数数目。

    9        1        1        1        1        1        1        1        1        1
   45        9        8        7        6        5        4        3        2        1
  165       45       36       28       21       15       10        6        3        1
  495      165      120       84       56       35       20       10        4        1
 1287      495      330      210      126       70       35       15        5        1
 3003     1287      792      462      252      126       56       21        6        1
 6435     3003     1716      924      462      210       84       28        7        1
12870     6435     3432     1716      792      330      120       36        8        1
24310    12870     6435     3003     1287      495      165       45        9        1
43758    24310    11440     5005     2002      715      220       55       10        1

代码如下：

    int a[10][10] = { 0 };
    for (int i = 1; i < 10; i++)
        a[0][i] = 1;
    for (int i = 1; i < 10; i++)
        for (int j = 1; j < 10; j++)
            for (int k = j; k < 10; k++)
                a[i][j] += a[i - 1][k];
    for (int i = 0; i < 10; i++)
        for (int j = 1; j < 10; j++)
            a[i][0] += a[i][j];

之后从高位到低位以此查找这些数就好了。比如25387920，最高位2，说明1-19999999中的所有递增数都符合要求，再看第二位5，说明从2222222-4999999之间的所有递增数符合要求，而第三位3小于5，则剩下的就没有讨论必要了。

代码

话不多说，上代码

#include<iostream>
using namespace std;

int main()
{
    int a[10][10] = { 0 };
    for (int i = 1; i < 10; i++)
        a[0][i] = 1;
    for (int i = 1; i < 10; i++)
        for (int j = 1; j < 10; j++)
            for (int k = j; k < 10; k++)
                a[i][j] += a[i - 1][k];
    for (int i = 0; i < 10; i++)
        for (int j = 1; j < 10; j++)
            a[i][0] += a[i][j];
    int n,nn[10];
    cin >> n;
    int n_= n;
    int weishu = 0, ans = 0;
    for (; n_ != 0; weishu++)
        nn[weishu] = n_ % 10, n_ /= 10;
    for (int i = 0; i < weishu-1; i++)
        ans += a[i][0];
    for (int i = 1; i < nn[weishu - 1]; i++)
        ans += a[weishu-1][i];
    
    for (int j = weishu - 1; j > 0; j--)
    {
        if (nn[j] > nn[j - 1])
            break;
        if (nn[j] <= nn[j-1])
            for (int i = nn[j]; i < nn[j-1]; i++)
                ans += a[j][i];
    }
    cout << ans;
    return 0;
}