为了更好的阅读体检，可以查看我的算法学习网
在线评测链接:P1296

题目描述

塔子哥接到了一个给音乐会门票编号的任务。每次可选的门票编号区间是 $[L, R]$ 。

由于音乐会的日期定在 $5$ 月 $20$ 号，塔子哥认为包含 $5$ ， $20$ 和 $520$ 的编号是有特殊含义，准备保留给对应的门票。例如： $12345$ ，其中包含了 $5$ ，是一个特殊编号；而 $24678$ 就是一个普通编号。

现在塔子哥想知道，在可选的门票编号区间内，有多少符合上面要求的特殊编号。

输入描述

输入第一行一个整数 $T$ ，表示可选的门票编码区间个数。( $\leq T \leq 1000$ )

接下来T行，每行2个整数: $L$ 和 $R$ ，表示编码可选的区间(闭区间，即包括 $L$ 和 $R$ 。( $\leq L \leq R \leq 10^6$ )

输出描述

输出一共 $T$ 行，每行 $3$ 个整数，分别表示对应区间里的 $5 、 20$ 和 $520$ 的编号数量

样例

样例输入

样例输出

2 1 0
18 1 0
2348 218 16

样例说明

对于第一组可选编号区间: $[5, 20]$ ，符合要求的特殊编号包括: ${ 5,15,20}$ ，其中包括 $5$ 的有 $2$ 个， $20$ 的 $1$ 个， $520$ 的 $0$ 个。

对于第三组可选编号区间:[52,1000]，包含520的特殊编号包括:{ $520 ， 1520 ， 2520 ， 3520 ， 4520 ， 5200, 5201, 5202, 5203, 5204, 5205, 5206, 5207, 5208, 5209, 5520$ }，共 $16$ 个。

思路：前缀和+预处理

对于一次查询 $L, R$ ，因为数据范围为 $1\leq L,R\leq 10^6$ 。
对于 $[L, R]$ 内的每个数，查询其是否存在 $5$ 的次数为 $R - L + 1$ ，同时还取决于这个数的长度。
长度为 $1$ 的数有 $9$ 个，长度为 $2$ 的数有 $90$ 个，长度为 $3$ 的数有 $900$ 个，长度为 $4$ 的数有 $9000$ 个，长度为 $5$ 的数有 $90000$ 个，长度为 $6$ 的数 $900000$ 个，长度为 $7$ 的数至多就 $1000000$ 这一个数。

假设每个数都得完全遍历，总的遍历次数为： $7+\sum\limits_{i=1}^6 9\times 10^{i-1} = 5888890\approx6\times 10^6$ 。

而 $T$ 组数据，最多有 $1000$ 组，故需要考虑优化。

定义 $c n t [i] [0]$ 表示 $[1, i]$ 中存在 $5$ 的数的个数。
则求解 $[L, R]$ 中 $5$ 的数的个数即为： $c n t [R] [0] - c n t [L - 1] [0]$ ，对于 $20$ 和 $520$ 同理。

这样，一次预处理后，每组数据只需要 $O (1)$ 时间即可。

类似题目推荐

LeetCode

303. 区域和检索 - 数组不可变，前缀和模板题
304. 二维区域和检索 - 矩阵不可变，二维前缀模板题
209. 长度最小的子数组
363. 矩形区域不超过 K 的最大数值和

Codefun2000

美团 P1140. 2023.04.01-第四题-倒水魔法
美团 P1287. 2023.05.13-春招-第二题-南北对决

代码

CPP

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

const int MAXV = 1000001;
// cnt[i][0] 表示前i个数中有5的数的个数
// cnt[i][1] 表示前i个数中有20的数的个数
// cnt[i][2] 表示前i个数中有520的数的个数
int cnt[MAXV][3];

void solve() {

    int l, r;
    cin >> l >> r;

    // 直接前缀和相减即区间和
    cout << (cnt[r][0] - cnt[l - 1][0]) << " " << (cnt[r][1] - cnt[l - 1][1]) << " " << (cnt[r][2] - cnt[l - 1][2]) << "\n";
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // 预处理前i个数中有5、20、520的数的个数
    for (int i = 1; i < MAXV; ++i) {
        string s = to_string(i);
        int c[3] = {0};
        for (int j = 0; j < s.size(); ++j) {
            // 注意这里每个数只统计一次，所有出现过标记为 1 即可
            if (s[j] == '5') c[0] = 1;
            if (j + 1 < s.size() && s[j] == '2' && s[j + 1] == '0') c[1] = 1;
            if (j + 2 < s.size() && s[j] == '5' && s[j + 1] == '2' && s[j + 2] == '0') c[2] = 1;
        }

        // 累加当前数是否出现过5、20、520即可
        for (int j = 0; j < 3; ++j) cnt[i][j] = cnt[i - 1][j] + c[j];
    }

    int T = 1;
    cin >> T;
    while (T--) solve();

    return 0;
}

python_127">python

python">MAXV = 1000001

# cnt[0][i] 表示前i个数中有5的数的个数
# cnt[1][i] 表示前i个数中有20的数的个数
# cnt[2][i] 表示前i个数中有520的数的个数
cnt = [[0] * MAXV for _ in range(3)]

# 预处理前i个数中有5、20、520的数的个数
for i in range(1, MAXV):
    s = str(i)
    c = [0] * 3
    for j in range(len(s)):
        # 注意这里每个数只统计一次，所有出现过标记为 1 即可
        if s[j] == '5':
            c[0] = 1
        if j + 1 < len(s) and s[j] == '2' and s[j + 1] == '0':
            c[1] = 1
        if j + 2 < len(s) and s[j] == '5' and s[j + 1] == '2' and s[j + 2] == '0':
            c[2] = 1
    # 累加当前数是否出现过5、20、520即可
    for j in range(3):
        cnt[j][i] = cnt[j][i-1] + c[j]

T = int(input())

for _ in range(T):
    l, r = map(int, input().split())
    # 直接前缀和相减即区间和
    print(cnt[0][r] - cnt[0][l-1], cnt[1][r] - cnt[1][l-1], cnt[2][r] - cnt[2][l-1])

Java

java">import java.util.Scanner;

public class Main {
    static final int MAXV = 1000001;
    // cnt[i][0] 表示前i个数中有5的数的个数
    // cnt[i][1] 表示前i个数中有20的数的个数
    // cnt[i][2] 表示前i个数中有520的数的个数
    static int[][] cnt = new int[MAXV][3];

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        // 预处理前i个数中有5、20、520的数的个数
        for (int i = 1; i < MAXV; ++i) {
            String s = Integer.toString(i);
            int[] c = new int[3];
            for (int j = 0; j < s.length(); ++j) {
                // 注意这里每个数只统计一次，所有出现过标记为 1 即可
                if (s.charAt(j) == '5') c[0] = 1;
                if (j + 1 < s.length() && s.charAt(j) == '2' && s.charAt(j + 1) == '0') c[1] = 1;
                if (j + 2 < s.length() && s.charAt(j) == '5' && s.charAt(j + 1) == '2' && s.charAt(j + 2) == '0') c[2] = 1;
            }

            // 累加当前数是否出现过5、20、520即可
            for (int j = 0; j < 3; ++j) cnt[i][j] = cnt[i - 1][j] + c[j];
        }

        int T = scanner.nextInt();
        while (T-- > 0) solve(scanner);
    }

    public static void solve(Scanner scanner) {

        int l = scanner.nextInt();
        int r = scanner.nextInt();

        // 直接前缀和相减即区间和
        System.out.println((cnt[r][0] - cnt[l - 1][0]) + " " + (cnt[r][1] - cnt[l - 1][1]) + " " + (cnt[r][2] - cnt[l - 1][2]));
    }
}

Go

package main

import "fmt"

const MAXV = 1000001

// cnt[i][0] 表示前i个数中有5的数的个数
// cnt[i][1] 表示前i个数中有20的数的个数
// cnt[i][2] 表示前i个数中有520的数的个数
var cnt [MAXV][3]int

func main() {
    var T int
    fmt.Scan(&T)
    // 预处理前i个数中有5、20、520的数的个数
    for i := 1; i < MAXV; i++ {
        s := fmt.Sprintf("%d", i)
        c := [3]int{0, 0, 0}
        for j := 0; j < len(s); j++ {
            // 注意这里每个数只统计一次，所有出现过标记为 1 即可
            if s[j] == '5' {
                c[0] = 1
            }
            if j+1 < len(s) && s[j] == '2' && s[j+1] == '0' {
                c[1] = 1
            }
            if j+2 < len(s) && s[j] == '5' && s[j+1] == '2' && s[j+2] == '0' {
                c[2] = 1
            }
        }

        // 累加当前数是否出现过5、20、520即可
        for j := 0; j < 3; j++ {
            cnt[i][j] = cnt[i-1][j] + c[j]
        }
    }

    for ; T > 0; T-- {
        var l, r int
        fmt.Scan(&l, &r)

        // 直接前缀和相减即区间和
        fmt.Println(cnt[r][0]-cnt[l-1][0], cnt[r][1]-cnt[l-1][1], cnt[r][2]-cnt[l-1][2])
    }
}

Js

process.stdin.resume();
process.stdin.setEncoding('utf-8');
let input = '';
process.stdin.on('data', (data) => {
    input += data;
    return;
});
process.stdin.on('end', () => {
    const lines = input.trim().split('\n');
    const MAXV = 1000001;

    // cnt[0][i] 表示前i个数中有5的数的个数
    // cnt[1][i] 表示前i个数中有20的数的个数
    // cnt[2][i] 表示前i个数中有520的数的个数
    const cnt = [[0], [0], [0]];
    for (let i = 1; i < MAXV; i++) {
        const s = String(i);
        const c = [0, 0, 0];
        for (let j = 0; j < s.length; j++) {
            // 注意这里每个数只统计一次，所有出现过标记为 1 即可
            if (s[j] === '5') {
                c[0] = 1;
            }
            if (j + 1 < s.length && s[j] === '2' && s[j + 1] === '0') {
                c[1] = 1;
            }
            if (j + 2 < s.length && s[j] === '5' && s[j + 1] === '2' && s[j + 2] === '0') {
                c[2] = 1;
            }
        }
        // 累加当前数是否出现过5、20、520即可
        cnt[0][i] = cnt[0][i - 1] + c[0];
        cnt[1][i] = cnt[1][i - 1] + c[1];
        cnt[2][i] = cnt[2][i - 1] + c[2];
    }

    for (let i = 1; i < lines.length; i++) {
        const [l, r] = lines[i].trim().split(' ').map(Number);
        // 直接前缀和相减即区间和
        console.log(
            cnt[0][r] - cnt[0][l - 1],
            cnt[1][r] - cnt[1][l - 1],
            cnt[2][r] - cnt[2][l - 1]
        );
    }
});