蓝桥杯线上模拟赛—递增数
题目
若一个正整数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;
}