目录
题目
要求
思路
暴力解法
缺点
技巧
中间一部分
末尾一部分
开头一部分
最后
代码部分讲解
最终所有代码
题目
这天小明正在学数数。
他突然发现有些正整数的形状像一挫 “山”, 比如 123565321、145541123565321它 们左右对称 (回文) 且数位上的数字先单调不减, 后单调不增。
小朋数了衣久也没有数完, 他惒让你告诉他在区间 [2022,2022222022] 中有 多少个数的形状像一座 “山”。
要求
填空题，要写出答案即可
思路
暴力解法
思路非常简单，提取每一个数字的位数来判断两边是否相等，并且判断前一半是否是单调不减的
缺点
缺点是每一个都要计算会十分麻烦，计算量直接来到了10的10次方，估计要运行一分多钟，虽然题目只要求答案，你可以运行完成后直接打印答案，但是还有更加巧妙的思路
技巧
中间一部分
由于1111~999999999可以进行变化
取前一半数字，只要他满足单调不减就行了
比如如果五位数
取前一半也就是三个数字
124时，后面必定有且只有一种数字（21）与其对应，形成12421
所以我们只需算前一半的数字即可
也就是11~99999
这一个变化带来速度提升是巨大的
时间直接缩小几个数量级
末尾一部分
在末尾中2022222022这个数字比较特殊
因为开头为2所以前一位也必须不比2小的数
显然2后面是0无法满足条件
所以最高位2必须要变小，然而不能为0
所以只能是1（个位同时也必须是1），而且中间部分位数可以随便变化（因为1111111111~1999999991属于2022~2022222022）
于是可以把他看成为8位数字，然后再算一次加起来就行了
开头一部分
开头没什么好说的
2022~9999
提取前一半位数，同时由于最小为2，所以百位也必须是不比2小的数字（2,3,4,5,6,7,8,9）
以此类推可以心算出来开头部分（2022~9999）的符合条件的个数为8+7+6+5+4+3+2+1
最后
最后全部加起来
代码部分讲解
中间一部分加末尾一部分为
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| int sum_2 = 0;
int sum_3 = 0;
int sum_4 = 0;
if (i == 10)
sum_2 = 9 / 2;
else if (i % 2 == 0)
sum_2 = i / 2;
else
sum_2 = i / 2+1;
for (int j = 0; j <= sum_2-1; j++)
{
sum_3 = sum_3 + 1*pow(10, j);
sum_4 = sum_4 + 9 * pow(10, j);
}
for (int z = sum_3; z <= sum_4; z++)
{
if (Function_1(z))
{
max++;
}
}
|
由于奇数位数的数字取一半用的是进一法，而c/c++用的是退一法，所以对奇数位数的数字做出分类以及改变
其中pow代表的是指数公式（前面为底数，后面为指数），sum3和sum4分别表示各个位数的值的最大和最小值，方便通过访问来遍历数组的元素
当位数个数为10个时也就是到了"末尾一部分"的数字了
这时候可以直接当做8，当成8位数来计算就可以了
同时判断是否递增的函数可以用循环来判断
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| bool Function_1(int n)
{
int x_1 = 9;
int x_2 = 9;
int y_1 = 9;
while (n > 0)
{
int y_1 = x_1;
x_1 = n % 10;
x_2 = y_1;
n = n / 10;
if (x_1 > x_2)
{
return false;
}
}
return true;
}
|
最终所有代码
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
| #include <iostream>
#include<math.h>
using namespace std;
bool Function_1(int n)
{
int x_1 = 9;
int x_2 = 9;
int y_1 = 9;
while (n > 0)
{
int y_1 = x_1;
x_1 = n % 10;
x_2 = y_1;
n = n / 10;
if (x_1 > x_2)
{
return false;
}
}
return true;
}
int main()
{
int max = 0;
int sum_1=0;
max = 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1;
for (int i = 5; i <= 10; i++)
{
int sum_2 = 0;
int sum_3 = 0;
int sum_4 = 0;
if (i == 10)
sum_2 = 9 / 2;
else if (i % 2 == 0)
sum_2 = i / 2;
else
sum_2 = i / 2+1;
for (int j = 0; j <= sum_2-1; j++)
{
sum_3 = sum_3 + 1*pow(10, j);
sum_4 = sum_4 + 9 * pow(10, j);
}
for (int z = sum_3; z <= sum_4; z++)
{
if (Function_1(z))
{
max++;
}
}
}
cout << max << endl;
return 0;
}
|
