拼多多笔试 拼多多软件算法笔试5-15

订阅专栏，方便查阅，时刻更新各厂软件算法笔试https://blog.nowcoder.net/zhuanlan/0oDWVm

题目1：多多的商品编号

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

输入

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个。

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

using namespace std;

const int mxn = 1e6;

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

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

        string s = to_string(i);

        if (s.find('5') != string::npos)
            pre5[i]++;

        if (s.find("20") != string::npos)
            pre20[i]++;

        if (s.find("520") != string::npos)
            pre520[i]++;
    }

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

        cout << pre5[R] - pre5[L - 1] << " ";
        cout << pre20[R] - pre20[L - 1] << " ";
        cout << pre520[R] - pre520[L - 1] << "\n";
    }

    return 0;
}

题目2：多多的植树计划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个整数，表示最少的浇水次数使得所有树苗都能达到目标的健康度。

示例1

输入

4 10 5 3

2

3

6

8

输入

2

说明

两次浇水:

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

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

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

示例2

输入

3 20 10 5

10

5

0

输出

3

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

using namespace std;

int N, M, A, B;
vector<int> healths;

bool check(int x) {
    priority_queue<int, vector<int>, greater<int>> nums(healths.begin(), healths.end());
    int target = M;
    for (int i = 0; i < x; ++i) {
        int minn = nums.top();
        nums.pop();
        nums.push(minn + A - B);
        target -= B;
    }
    return nums.top() >= target;
}

int main() {
    cin >> N >> M >> A >> B;
    healths.resize(N);
    for (int i = 0; i < N; ++i) {
        cin >> healths[i];
    }

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

    int l = 0, r = 1e6;
    while (l < r) {
        int mid = (l + r) / 2;
        if (check(mid)) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }

    cout << r << endl;

    return 0;
}

题目3：多多的字符翻转

多多君在研究十六进制字符串的翻转关系，每次可以选择字符串中的某个子串，进行一次整体变大或变小的翻转。例如: "ABCD"选择中间2个字符的子串"BC"，变大翻转会变成: "ACDD"，变小翻转会变成:"AABD"。特别的，字符0'变小的翻转会变成字符F'，同理字符'F'的变大翻转会变成字符0'，以此ABAB