蚂蚁0420暑期实习笔试

第一题

小红拿到了一个数组，她可以进行怡好一次操作:选择两个相邻元素将它们合井，合并后的新元素为原来的两个元素之和。小红想知道，操作1次后数组的极差的最小值是多少？数组的极差为:数组的最大值减最小值。

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

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

    vector<int> pre_max(n), pre_min(n), suf_max(n), suf_min(n);
    // pre_max[i]：前i个数中的最大值
    // pre_min[i]：前i个数中的最小值
    // suf_max[i]：后i个数中的最大值
    // suf_min[i]：后i个数中的最小值

    // 计算 pre_max 和 pre_min
    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 和 suf_min
    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 = a[i] + a[i+1];
       mx = max(mx, i+2 < n ? suf_max[i+2] : INT_MIN);  // 若 i+2 < n，则后面的数中的最大值对答案有贡献
      mx = max(mx, i-1 >= 0 ? pre_max[i-1] : INT_MIN);  // 若 i-1 >= 0，则前面的数中的最大值对答案有贡献
        int mi = a[i] + a[i+1];
      mi = min(mi, i+2 < n ? suf_min[i+2] : INT_MAX);  // 若 i+2 < n，则后面的数中的最小值对答案有贡献
      mi = min(mi, i-1 >= 0 ? pre_min[i-1] : INT_MAX);  // 若 i-1 >= 0，则前面的数中的最小值对答案有贡献
       ans = min(ans, mx - mi);
    }

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

第二题

小红非常喜欢‘R’字符，而不喜欢‘B’字符。因此她定义字符串的权值为字符‘R’的出现次数。例如，"RRBRB"的权值为3。小红拿到了一个长度为n的仅由‘R’和‘B’组成的字符串s。她想知道，长度为n的、仅由‘R’和‘B’组成的字符串中，字典序不小于s的字符串的权值之和是多少?由于答案可能太大，请对10^9+7取模后再输出。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <functional>

using namespace std;
//思路 
//使用递归函数和记忆化搜索，计算给定字符串中满足要求的子序列的个数。其中，递归函数 dfs(i, j) 计算以第 i 个字符结尾、且满足要求的子序列的个数，递归函数 getAns(k, f1) 计算从第 k 个字符开始、且满足要求的子序列的个数。函数计算过程中使用记忆化技术避免重复计算。
// 设置取模常量
const int mod = 1e9 + 7;

int n;
string s;

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

// 递归函数，用于计算答案
int getAns(int k, int f1) {
    if (k > n) {
        return 0;
    }
    int cur = 0;
    if (!f1 || s[k-1] == 'B') {
        cur += getAns(k + 1, f1 && s[k - 1] == 'B');
    }
    cur += getAns(k + 1, f1 && s[k - 1] == 'R');
    cur += dfs(k+1, f1 && s[k-1] == 'R');
    return cur % mod;
}

int main() {
    // 读取输入
    cin >> n;
    cin >> s;

    // 计算答案并输出
    dfs(1, 1);
    cout << getAns(1, 1) << endl;

    return 0;
}

第三题

定义一个数组的权值为:数组所有元素乘积的因子数量。例如，数组[23]的权值为4，因为2*3=6有4个因子:1、2、3、6。小红拿到了一个仅包含2和3的数组，她希望你把该数组重新排列，使得所有连续子数组的权值之和尽可能小。你能帮帮她吗?

#include <iostream>
#include <vector>

using namespace std;

int main() {
int n;
cin >> n; // 读取 n 的值

vector<int> a(n);
for (int i = 0; i < n; i++) {
    cin >> a[i]; // 读取整数列表 a
}

int cnt2 = 0, cnt3 = 0, ans = 0;
vector<int> sum2(n+1), sum3(n+1);

// 计算 a 中 2 和 3 的数量
for (int i = 0; i < n; i++) {
    if (a[i] == 2) {
        cnt2++;
    } else {
        cnt3++;
    }
}

// 计算 2 的和
for (int i = 1; i <= cnt2; i++) {
    sum2[i] = sum2[i-1] + i + 1;
    ans += sum2[i];
}

// 计算 3 的和
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;

先点赞，再收藏，听说会直接进面哦hhh