题解：幸运数字

问题分析

给定一个区间 ([l, r])，我们需要找出区间内的所有“幸运数字”。幸运数字的定义是每一位数字都是严格递增的。也就是说，从左到右读这个数字时，每一位数都严格大于前一位。

例如，数字 1234 是幸运数字，因为每一位数字都比前一位大，而数字 1432 不是幸运数字，因为数字 4 后面跟着 3，违反了递增的规则。

要求：

对于给定的区间 ([l, r])，输出这个区间内的幸运数字的个数。

关键点：

1. 需要判断一个数是否是幸运数字。
2. 给定的区间上限为 (1 \leq l \leq r \leq 1000000)，所以需要一种高效的方式来判断。

解题思路

1. 幸运数字的判断：

   • 对于一个数字，如果其每一位都严格递增，那么这个数字就是幸运数字。
   • 例如，123 是幸运数字，因为 1 < 2 < 3，而 321 不是幸运数字。

2. 解决方式：

   • 我们可以通过将数字从低位到高位逐位比较，判断每一位是否严格大于前一位。
   • 如果是幸运数字，我们就计数。

3. 遍历所有数字：

   • 对于区间 ([l, r])，遍历区间内的所有数字，检查每个数字是否为幸运数字。

4. 时间复杂度：

   • 对于每个数字，检查其每一位是否递增。一个数字最多有 6 位（因为 (r \leq 1000000)），所以每个数字的检查时间复杂度为 (O(k))，其中 (k) 是数字的位数。
   • 因此，时间复杂度为 (O((r - l + 1) \times k))，其中 (k \leq 6)，即每个数字最多需要检查 6 次。

代码实现

#include<bits/stdc++.h>
using namespace std;

bool lucky(int i) {
    int num1, num2;
    // 循环检查数字每一位
    while (i > 9) {
        num1 = i % 10;  // 当前位数字
        num2 = i / 10 % 10;  // 前一位数字
        // 如果当前位小于或等于前一位，说明不是幸运数字
        if (num1 <= num2) {
            return 0;
        } else {
            i = i / 10;  // 去掉当前最低位
        }
    }
    return 1;  // 如果所有位都严格递增
}

int main() {
    int a, b, num = 0;
    cin >> a >> b;
    
    // 遍历区间 [a, b]
    for (int i = a; i <= b; i++) {
        if (i < 10) {
            num++;  // 单个数字（1-9）都是幸运数字
        } else {
            if (lucky(i) == 1) {
                num++;  // 判断是否为幸运数字
            }
        }
    }
    cout << num;  // 输出幸运数字个数
    return 0;
}

本人水平有限，如果有什么不对的话，可以评论一下，因为我也是大一的