uq_43625241302

用户名：uq_43625241302

访问量：3160

签　名：

等　　级
排　　名	7726
经　　验	1287
参赛次数	1
文章发表	6
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

预处理 + 双端队列
浏览：365

你可能喜欢

模拟分类（标题不能太短）

　　作者: uq_43625241302　　　　发表时间：2023-05-10 18:48:55 浏览：424　|　评论：0　

原题链接：蓝桥杯2022年第十三届决赛真题-好数之和

# 模拟分类
## 解题思路
举个例子：
假设要找区间[1, 123456789]中所有的好数之和：
1. 假设`2022`出现在最后四位，即我们要求类似于`xxxxx2022`结构的数，思考其前后缀可以是什么？
	* 其前缀可以是区间`[0， 12345)`中的任意一个数，构成`[2022, 12022, ..., 123442022]`，后缀为`0`
	* 边界情况需特殊讨论：当后四位 < `2022` 时，取不到边界。此时，可以取到边界
2. 将`2022`向左移动，变为求类似于`xxxx2022x`结构的数，同上，讨论前后缀：
	* 非边界，前缀为`[0, 1234)`中任意一个数时，后缀为`[0, 10)`
	* 边界情况，即前缀为`1234`，此时如讨论接下来四位数`num`和`2022`大小关系：
		* `num < 2022`，则不能取
		* `num == 2022`，可以取，但后缀限制为`[0, 最后一位数的大小]`
		* `num > 2022`，可以取，后缀无限制，为`[0, 10)`
3. 继续将`2022`左移，变为求类似于`xxx2022xx`结构的数，同上，讨论前后缀：
	* 非边界，前缀为`[0, 123)`中任意一个数时，后缀为`[0, 100)`
	* 边界情况，即前缀为`123`，此时如讨论接下来四位数`num`和`2022`大小关系：
		* `num < 2022`，则不能取
		* `num == 2022`，可以取，但后缀限制为`[0, 最后两位数的大小]`
		* `num > 2022`，可以取，后缀无限制，为`[0, 100)`
4. 继续将`2022`左移，变为求类似于`xx2022xxx`结构的数，同上，讨论前后缀：(**注意：此时要考虑去重了**)
	* 非边界，前缀为`[0, 12)`中任意一个数时，后缀为`[0, 1000)`
	* 边界情况，即前缀为`12`，此时如讨论接下来四位数`num`和`2022`大小关系：
		* `num < 2022`，则不能取
		* `num == 2022`，可以取，但后缀限制为`[0, 最后三位数的大小]`
		* `num > 2022`，可以取，后缀无限制，为`[0, 1000)`
	* **注意：去重**，因为像`12022022`之类`2022`出现多次的数，在前面已经计算过了，因此，在此时需要对后六位数`022xxx`进行判断:
		 * 如果后六位`022xxx`出现了`2022`，则此时不需要计算，因为前面已经算过了
		 * 没有出现`2022`，则加进答案
5. 重复上述操作即可

## 代码实现
```java
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        new Main().go();
    }

public void go() {
        Scanner sc = new Scanner(System.in);
        int l = sc.nextInt(), r = sc.nextInt();
        System.out.println(dfs(r) - dfs(l - 1));
    }

public long dfs(int num) {
        if(num < 2022) return 0;
        int n = getLength(num), x = 2022, y = 10000, z = 1;
        long res = 0;
        for(int i = 0; i < n - 3; i++) {
            int prefix = num / y;
            for(int j = 0; j < prefix; j++) {
                for(int k = 0; k < z; k++) {
                    long m = (long) j * y + x + k;
                    // 去重操作：因为像12022022出现了两次2022的，只能计算一次，因此需要保证尾部不能有2022
                    res += isValid(m % (z * 1000L)) ? 0 : m;
                }
            }
            // 判断临界情况
            int flag = (num / z) % 10000;
            int up = flag == 2022 ? num % z + 1 : flag < 2022 ? 0 : z;
            for(int j = 0; j < up; j++) {
                long m = (long) prefix * y + x + j;
                // 去重操作：因为像12022022出现了两次2022的，只能计算一次，因此需要保证尾部不能有2022
                res += isValid(m % (z * 1000L)) ? 0 : m;
            }
            y *= 10; x *= 10; z *= 10;
        }
        return res;
    }

public boolean isValid(long x) {
        String s = String.valueOf(x);
        return s.contains("2022");
    }

public int getLength(int x) {
        int res = 0;
        while (x != 0) {
            res++;
            x /= 10;
        }
        return res;
    }
}

```

0.0分

5 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

uq_43625241302

TA的其他文章

你可能喜欢

C二级辅导-分段函数（C语言代码）

矩阵转置（C语言代码）

【回文数(二)】（C++代码）

川哥的吩咐（C++代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

模拟分类（标题不能太短）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）

C语言训练-求1+2!+3!+...+N!的和（C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

永远的丰碑（C语言代码）

青年歌手大奖赛_评委会打分（C语言代码）

神奇的fans （C语言代码）

10月月赛题解

uq_43625241302

TA的其他文章

你可能喜欢

C二级辅导-分段函数 （C语言代码）

矩阵转置 （C语言代码）

【回文数(二)】 （C++代码）

川哥的吩咐 （C++代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

模拟分类（标题不能太短）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）

C语言训练-求1+2!+3!+...+N!的和 （C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

永远的丰碑 （C语言代码）

青年歌手大奖赛_评委会打分 （C语言代码）

神奇的fans （C语言代码）

10月月赛题解

C二级辅导-分段函数（C语言代码）

矩阵转置（C语言代码）

【回文数(二)】（C++代码）

川哥的吩咐（C++代码）

　　评论区

C语言训练-求1+2!+3!+...+N!的和（C语言代码）

永远的丰碑（C语言代码）

青年歌手大奖赛_评委会打分（C语言代码）