pdd0515_1

Posted on | In |
Words count in article: 643 | Reading time ≈ 2

多多君接到了一个给活动商品编号的任务:每次可选的商品编号区间是[L,R]。由于活动的日期定在05月20号，多多君认为包含5，20和520的编号是有特殊含义，准备保留给对应的商品。例如:618520,其中包含了520，是一个特殊编号;而12368就是一个普通编号。多多君想知道，在可选的商品编号区间内，有多少符合上面要求的特殊编号。

输入描述

第一行，1个整数T，表示每次可选的编码区间。( 1 <=T<= 1,000 ) 接下来T行，每行2个整数:L和R，表示编码可选的区间(闭区间，即包括L和R)。( 1<=L<=R<= 1,000,000 )

输出描述

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

示例：

1
2
3
4
5
6
7
8
9
10
输入：
3
1 20
100 1000
520 5200

输出：
2 1 0
252 19 1
1441 187 6

分析：

难度：容易

1
2
3
4
5
此题要求统计每个区间[L, R]中的符合条件的三种数字的数量
暴力：
	最容易想到的做法是第一层循环枚举区间数量，第二层枚举改区间并统计符合的数字，此时时间复杂度为1000 * 1000000，一定会超时
优化：
	统计某个区间中的满足某个条件的数字个数，想到前缀和，因此用空间换时间的做法，用前缀和提前统计。

代码

  • C++

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
#include <bits/stdc++.h>

using namespace std;

const int N = 1000010;

// 前缀和数组
int s1[N], s2[N], s3[N];

int main() {
    int T;
    cin >> T;

    for (int i = 1;i < 1000001;i ++) {
        // 为了方便判读是否包含某个数字，转为字符串
        string t = to_string(i);
        
        s1[i] = s1[i - 1] + (t.find("5") != string::npos);
        s2[i] = s2[i - 1] + (t.find("20") != string::npos);
        s3[i] = s3[i - 1] + (t.find("520") != string::npos);
    }

    while (T --) {
        int L, R;
        cin >> L >> R;
        // 利用前缀和数组计算数量
        cout << (s1[R] - s1[L - 1]) << " " << (s2[R] - s2[L - 1]) << " " << (s3[R] - s3[L - 1]) << endl;
    }

    return 0;
}
  • Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
N = 1000010

s1, s2, s3 = [0] * N, [0] * N, [0] * N

if __name__ == '__main__':
    T = int(input())

    for i in range(1, 1000001):
        t = str(i)

        s1[i] = s1[i - 1] + int('5' in t)
        s2[i] = s2[i - 1] + int('20' in t)
        s3[i] = s3[i - 1] + int('520' in t)

    while T:
        L, R = map(int, input().split())
        print(str(s1[R] - s1[L - 1]) + " " + str(s2[R] - s2[L - 1]) + " " + str(s3[R] - s3[L - 1]))
        T -= 1
0%