笔试时间：2023年5月15日 暑期实习

第一题

题目：多多的商品编号

多多君接到了一个给活动商品编号的任务:每次可选的商品编号区间是[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的编号数量

示例输入

3

1 20

100 1000

520 5200

示例输出

2 1 0

252 19 1

1441 187 6

对于第一组可选编号区间:[1,20]，符合要求的特殊编号包括:

{ 5,15,20}，其中包括5的有2个，20的1个，520的0个。

对于第三组可选编号区间:[520,5200]，包含520的特殊编号包括:

{ 520，1520，2520，3520，4520，5200 }，共6个。

参考题解

C++：

#include <iostream>
#include <vector>
#include <string>

using namespace std;

const int mxn = 1000000;

int main() {
    vector<int> pre5(mxn + 1, 0);
    vector<int> pre20(mxn + 1, 0);
    vector<int> pre520(mxn + 1, 0);

    for (int i = 1; i <= mxn; i++) {
        pre5[i] = pre5[i - 1];
        pre20[i] = pre20[i - 1];
        pre520[i] = pre520[i - 1];

        string str_i = to_string(i);
        if (str_i.find("5") != string::npos) {
            pre5[i]++;
        }
        if (str_i.find("20") != string::npos) {
            pre20[i]++;
        }
        if (str_i.find("520") != string::npos) {
            pre520[i]++;
        }
    }

    int T;
    cin >> T;

    for (int t = 0; t < T; t++) {
        int L, R;
        cin >> L >> R;

        int ans5 = pre5[R] - pre5[L - 1];
        int ans20 = pre20[R] - pre20[L - 1];
        int ans520 = pre520[R] - pre520[L - 1];

        cout << ans5 << " " << ans20 << " " << ans520 << endl;
    }

    return 0;
}

Java：

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        final int mxn = 1000000;
        int[] pre5 = new int[mxn + 1];
        int[] pre20 = new int[mxn + 1];
        int[] pre520 = new int[mxn + 1];

        for (int i = 1; i <= mxn; i++) {
            pre5[i] = pre5[i - 1];
            pre20[i] = pre20[i - 1];
            pre520[i] = pre520[i - 1];

            String str_i = Integer.toString(i);
            if (str_i.contains("5")) {
                pre5[i]++;
            }
            if (str_i.contains("20")) {
                pre20[i]++;
            }
            if (str_i.contains("520")) {
                pre520[i]++;
            }
        }

        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt();

        for (int t = 0; t < T; t++) {
            int L = scanner.nextInt();
            int R = scanner.nextInt();

            int ans5 = pre5[R] - pre5[L - 1];
            int ans20 = pre20[R] - pre20[L - 1];
            int ans520 = pre520[R] - pre520[L - 1];

            System.out.println(ans5 + " " + ans20 + " " + ans520);
        }
    }
}

Python：

mxn = 10**6
pre5, pre20, pre520 = [0 for _ in range(mxn + 1)],[0 for _ in range(mxn + 1)],[0 for _ in range(mxn + 1)]
for i in range(1, 1000001):
    pre5[i], pre20[i],pre520[i] = pre5[i-1], pre20[i-1],pre520[i-1]
    if '5' in str(i):
        pre5[i] += +1
    if '20' in str(i):
        pre20[i] += 1
    if '520' in str(i):
        pre520[i] += 1

T = int(input())
for _ in range(T):
    L, R = map(int, input().split(" "))
    print(pre5[R] - pre5[L-1], end=" ")
    print(pre20[R] - pre20[L-1], end=" ")
    print(pre520[R] - pre520[L-1])

第二题

题目：多多的植树计划IV

多多君在多多农场的某块林地上种了N颗树苗（(编号1~N)，其中第i颗树有健康度Hi。多多君计划给树苗们浇水，每次给某棵树苗浇水可以使其健康度上升A点;同时由于水的流动，其他树苗的健康度都会上升B点(其中A大于等于B)。为了每棵树苗都能够顺利成长，多多君希望所有树苗的健康度都大于或等于M。多多君想知道，在达到这个目标的前提下，最少的浇水次数是多少。

输入描述

第一行，4个整数N，M，A和B，分别表示农场中树苗的数量、目标达到的健康度、直接浇水增加的健康度和间接浇水增加的健康度。( 1 <= N,M,A,B<= 1,000,000，A >=B) 接下来N行，每行1个整数Hi，分别表示第i棵树苗初始的健康度Hi。(0<= Hi <= 1,000,000 )

输出描述

共一行，1个整数，表示最少的浇水次数使得所有树苗都能达到目标的健康度。

示例输入

4 10 5 3

2

3

6

8

示例输出

2

两次浇水:

第一次浇水选择第1号树苗，树苗们的健康度变为:{7，6，9,11}

第二次浇水选择第2号树苗，树苗们的健康度变为:{ 10,11，12,14 }

满足所有树苗的健康度都大于或等于10

参考题解

C++：

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int main() {
    int N, M, A, B;
    cin >> N >> M >> A >> B;

    vector<int> healths(N);
    for (int i = 0; i < N; i++) {
        cin >> healths[i];
    }

    sort(healths.begin(), healths.end());

    auto check = [&](int x) {
        priority_queue<int, vector<int>, greater<int>> nums(healths.begin(), healths.end());
        int target = M;
        for (i