蚂蚁集团软件算法笔试

校招一对一进阶提高，带领学员斩获大厂实习秋招春招offer！！！

笔试科目一帮助，踢踢饲料沃！！！

题目1：

小红拿到了一个数组，她可以进行怡好一次操作:选择两个相邻元素将它们合井，合并后的新元素为原来的两个元素之和。

小红想知道，操作1次后数组的极差的最小值是多少？

数组的极差为:数组的最大值减最小值。

输入描述

第二行输入n个正整数ai，代表数组的元素。

2<=n<10^5，1<ai<10^9

输出描述

一个整数，代表操作后的极差最小值。

输入

3

1 4 5

输出

0

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits.h>
using namespace std;

int n;
vector<int> a, pre_max, pre_min, suf_max, suf_min;

int get_max(int i) {
    int ret = a[i] + a[i+1];
    if (i+2 < n) {
        ret = max(ret, suf_max[i+2]);
    }
    if (i-1 >= 0) {
        ret = max(ret, pre_max[i-1]);
    }
    return ret;
}

int get_min(int i) {
    int ret = a[i] + a[i+1];
    if (i+2 < n) {
        ret = min(ret, suf_min[i+2]);
    }
    if (i-1 >= 0) {
        ret = min(ret, pre_min[i-1]);
    }
    return ret;
}

int main() {
    cin >> n;
    a.resize(n);
    pre_max.resize(n);
    pre_min.resize(n);
    suf_max.resize(n);
    suf_min.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    pre_max[0] = pre_min[0] = a[0];
    for (int i = 1; i < n; i++) {
        pre_max[i] = max(pre_max[i-1], a[i]);
        pre_min[i] = min(pre_min[i-1], a[i]);
    }

    suf_max[n-1] = suf_min[n-1] = a[n-1];
    for (int i = n-2; i >= 0; i--) {
        suf_max[i] = max(suf_max[i+1], a[i]);
        suf_min[i] = min(suf_min[i+1], a[i]);
    }

    int ans = INT_MAX;
    for (int i = 0; i < n-1; i++) {
        int mx = get_max(i);
        int mi = get_min(i);
        ans = min(ans, mx-mi);
    }

    cout << ans << endl;
    return 0;
}

题目2：

小红非常喜欢‘R’字符，而不喜欢‘B’字符。因此她定义字符串的权值为字符‘R’的出现次数。例如，"RRBRB"的权值为3。

小红拿到了一个长度为n的仅由‘R’和‘B’组成的字符串s。她想知道，长度为n的、仅由‘R’和‘B’组成的字符串中，字典序不小于s的字符串的权值之和是多少?由于答案可能太大，请对10^9+7取模后再输出。

输入描述

第一行输入一个正整数n。 第二行输入一个长度为n的、仅由字符 'R'和'B'组成的字符串. 1<=n<=10^5

输出描述

请输出一个整数，代表长度为n的、字典序不小于s的字符串权值之和。由于答案可能太大，请对10^9+7取模后再输出。

输入

3

RBR

输出

7

说明

共有3个字符串符合要求:

RBR的权值为2。

RRB的权值为2。

RRR的权值为3。

#include <iostream>
#include <string>
#include <vector>
using namespace std;

const int mod = 1e9 + 7;
int n;
string s;
vector<vector<int>> dp1, dp2;

int dfs(int i, int j) {
    if (i > n) {
        return 1;
    }
    if (dp1[i][j] != -1) {
        return dp1[i][j];
    }
    int cur = 0;
    if (!j || s[i-1] == 'B') {
        cur = dfs(i+1, j && (s[i-1] == 'B'));
    }
    cur = (cur + dfs(i+1, j && (s[i-1] == 'R'))) % mod;
    dp1[i][j] = cur;
    return cur;
}

int getAns(int k, int f1) {
    if (k > n) {
        return 0;
    }
    if (dp2[k][f1] != -1) {
        return dp2[k][f1];
    }
    int cur = 0;
    if (!f1 || s[k-1] == 'B') {
        cur = getAns(k+1, f1 && (s[k-1] == 'B'));
    }
    cur = (cur + getAns(k+1, f1 && (s[k-1] == 'R'))) % mod;
    cur = (cur + dfs(k+1, f1 && (s[k-1] == 'R'))) % mod;
    dp2[k][f1] = cur;
    return cur;
}

int main() {
    cin >> n;
    cin >> s;
    dp1.resize(n+1, vector<int>(2, -1));
    dp2.resize(n+1, vector<int>(2, -1));
    dfs(1, 1);
    cout << getAns(1, 1) << endl;
    return 0;
}

题目3：

定义一个数组的权值为:数组所有元素乘积的因子数量。例如，数组[23]的权值为4，因为2*3=6有4个因子:1、2、3、6。

小红拿到了一个仅包含2和3的数组，她希望你把该数组重新排列，使得所有连续子数组的权值之和尽可能小。你能帮帮她吗?

输入描述

第一行输入一个正整数n，代表数组的大小。 第二行输入n个正整数ai，代表小红拿到的数组

输出描述

一个正整数，代表重排后，所有连续子数组权值之和的最小值.

输入

2

2 3

输出

8

说明

无论是否重排，该数组的连续子数组权值之和都是8:

[2]的权值为2。

[3]的权值为2。

[2,3]的权值为4。

#include <iostream>
#include <vector>
using namespace std;

int n;
vector<int> a;

int main() {
    cin >> n;
    a.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    int cnt2 = 0, cnt3 = 0, ans = 0;
    vector<int> sum2(n+1), sum3(n+1);
    for (int i = 0; i < n; i++) {
        if (a[i] == 2) {
            cnt2++;
        } else {
            cnt3++;
        }
    }

    for (int i = 1; i <= cnt2; i++) {
        sum2[i] = sum2[i-1] + i + 1;
        ans += sum2[i];
    }

    for (int i = 1; i <= cnt3; i++) {
        sum3[i] = sum3[i-1] + i + 1;
        ans += sum3[i];
        ans += (i + 1) * sum2[cnt2];
    }

    cout << ans << endl;
    return 0;
}