蚂蚁0330算法岗笔试总结

写在前面：

蚂蚁的题总有一种阿里的气息，场外做题的感觉真的比场内要放松很多。

本篇文章仅分享本人解答代码做学习交流，若涉密或侵权可联系我删除。

题目 1

题目描述

小红拿到了一个 01 串 \(s\) ，她将进行恰好一次如下操作：

选择下标 \(i, j(i \ne j)\) ，交换 \(s_i\) 和 \(s_j\)。

小红想知道，不同的操作方案，最终能生成多少不同的字符串？

解题方法

根据题意，我们可以想到对于每一位 0 都可以和前面的若干个 1 交换位置形成新的字符串，同理 1 也可以和前面的 0 交换，因此需要统计前缀 0 和 1 的个数，即可计算出最终答案。（但需要特判一下长度为 2 的字符串）

或者只需要统计 0 和 1 的个数，直接相乘得到答案。

// version 1
#include <bits/stdc++.h>

using namespace std;

int main() {
    string s;
    cin >> s;
    if (s.length() == 2) {
        cout << 1 << endl;
        return 0;
    }
    long long int zero = 0, one = 0;
    long long int ans = 1;
    for(int i = 0; i < s.size(); i++) {
        if(s[i] == '0') {
            ans += one;
            zero++;
        }
        else {
            ans += zero;
            one++;
        }
    }
    cout << ans << endl;
    return 0;
}

// version 2
#include <bits/stdc++.h>

using namespace std;

int main() {
    string s;
    cin >> s;
    long long int zero = 0;
    for(int i = 0; i < s.size(); i++) {
        if(s[i] == '0') {
            zero++;
        }
    }
    long long int ans = (zero*(s.length() - zero) == 0 ? 1:zero*(s.length() - zero));
    cout << ans << endl;
    return 0;
}

题目 2

题目描述

小红定义一个字符串为好串，当且仅当该字符串是回文的，且包含 "red" 子串。例如，"redoder" 是好串。

现在小红拿到了一个字符串，她想知道该字符串有多少个子串是好串？

解题方法

动态规划。\(dp[i][j]\) 表示字符串下标从 \(i\) 到 \(j\) 的子串是否为回文子串，同时再判断是否包含 "red" 即可。（可能不是最优解，还有优化的空间）

#include <bits/stdc++.h>

using namespace std;

int countSubstrings(string s) {
    int len = s.length();
    vector<vector<bool>> yes(len, vector<bool>(len, true));
    for (int i = len - 1; i >= 0; i--) {
        for (int j = i + 1; j < len; j++) {
            yes[i][j] = (s[i] == s[j] && yes[i+1][j-1]);
        }
    }
    int ans = 0;
    for (int i = 0; i < len; i++) {
        for (int j = i; j < len; j++) {
            string tmp = s.substr(i, j - i + 1);
            if (yes[i][j] && j - i >= 2 && tmp.find("red") != tmp.npos) {
                ans++;
            }
        }
    }
    return ans;
}


int main() {
    string s;
    cin >> s;
    cout << countSubstrings(s) << endl;
}

题目 3

题目描述

小红定义一个数组的权值为：平均数正好等于 \(k\) 的最长连续子数组的长度，

请你求所有长度为 \(n\) 的，且元素不大于 \(m\) 的正整数组成的数组中，权值恰好等于 \(n\) 的数组数量。答案对 1e9 + 7 取模。

\(q\) 次询问，\(1 \le q \le 10^4\)，每次告诉你 \(n, m, k\)。

解题方法

动态规划。我们可以把问题转化为：

一个体积为 \(n*k\) 的背包，可以放 \(n\) 件物品，每件物品的最大体积为 \(m\) ，求放满背包的方案数。

由于询问的次数很多，如果对每次询问做 dp 会超时，可以借助离线查询的思维，先处理出所有的情况，\(dp[i][j][k]\) 表示放 \(i\) 件物品，体积为 \(j\)，每件物品的最大体积为 \(k\) 时的方案个数。

没在场上测试过，大致算了一下 \(10^7\) 次运算，勉勉强强吧，等看到正解再补一下。

#include <bits/stdc++.h>

using namespace std;

const int maxn_n = 100;
const int maxn_k = 100;
const int maxn_m = 10;
const int mod = 1e9+7;

int main() {
    int q;
    cin >> q;
    vector<vector<vector<int>>> dp(maxn_n + 1, vector<vector<int>>(maxn_n*maxn_k + 1, vector<int>(maxn_m + 1, 0)));
    for (int i = 0; i <= maxn_m; i++) {
        dp[0][0][i] = 1;
    }
    for (int i = 1; i <= maxn_n; i++) {
        for (int j = 1; j <= maxn_n*maxn_k; j++) {
            for (int g = 1; g <= maxn_m; g++) {
                for (int l = 1; l <= g; l++) {
                    if (j - l < 0) {
                        break;
                    }
                    dp[i][j][g] = (dp[i][j][g] + dp[i - 1][j - l][g])%mod;
                }
            }
        }
    }
    while (q--) {
        int n, m, k;
        cin >> n >> m >> k;       
        cout << dp[n][n*k][m] << endl;
    }
}