「技术笔试」蚂蚁金服 2023-03-16

T1 整数抽取

1e14 范围以内的一个正整数，将其每一数位上的奇数和偶数分别抽取出来组成两个新的数字，求这两差的绝对值。

直接模拟即可，用字符串存数字会方便一些。不然数字还需要倒置。

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int main() {
    string s;
    cin >> s;
    ll odd = 0, even = 0;
    for (auto c : s) {
        if ((c - '0') & 1) {
            odd = odd * 10 + c - '0';
        } else {
            even = even * 10 + c - '0';
        }
    }
    cout << abs(odd - even) << "\n";
    return 0;
}

T2 组装电脑

n 组零件，每组零件有若干种，每一种有一个价格和性能。你需要从每组里面选出一种零件，使得总价格不超过 x，并且性能总和最大。

n <= 40, 所有零件的种类数不超过 40，其他数值 1e9。

注意到总的零件种类不超过 40，假设平分到 p 干个组，然后暴力枚举的复杂度是 (40 / p) ^ p。当 p 是 20 时复杂度是 2^20，当 p 是 13 时复杂度是 3^13... 依次类推发现完全可以暴力。

应该可以证明当每组种类数是 3 时，要枚举的情况数是最多的。对 p 求一下倒数。

题目难度对标力扣周赛比较简单的 T4 或者难的 T3。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    ll n, all;
    cin >> n >> all;
    vector<vector<int>> v(n);
    vector<vector<int>> w(n);
    for (int i = 0; i < n; i++) {
        int m;
        cin >> m;
        v[i].resize(m);
        w[i].resize(m);
        for (int j = 0; j < m; j++) {
            cin >> v[i][j];
        }
        for (int j = 0; j < m; j++) {
            cin >> w[i][j];
        }
    }

    ll res = -1;
    function<void(int, ll, ll)> dfs = [&](int cur, ll tot, ll sum) {
        if (cur == n) {
            res = max(res, sum);
            return;
        }
        for (int i = 0; i < v[cur].size(); i++) {
            // 超出预算则跳过
            if (tot + v[cur][i] > all) {
                continue;
            } 
            dfs(cur + 1, tot + v[cur][i], sum + w[cur][i]);
        }
    };
    dfs(0, 0, 0);
    cout << res << "\n";

    return 0;
}

T3 带传送阵的矩阵游离

n 行 m 列的矩阵，每个位置上有一个元素。你可以上下左右行走，代价是前后两个位置元素值差的绝对值。另外，你最多可以使用一次传送阵（只能从一个数跳到另外一个相同的树），求从走上角走到右下角最少需要多少时间。

1 <= n, m <= 500, 1 <= aij <= 1e9。

最短路问题，但需要带上是否使用传送阵这一维度状态。

d[i][j][k] 表示走到 i 行 j 列时，使用(k=1) 或未使用 (k=0) 时的最短时间。然后用 dijkstra 求解即可。

每次除去考虑往上下左右转移，还需要单独考虑 k = 0 时可以使用传送阵的情况。用哈希表提前存下来每种数的所有位置，然后遍历转移即可。

由于枚举传送带到达的位置时，可能会把所有数值都枚举一遍，极端情况是所有位置的数字都一样，这样复杂度会上升至 (nm)^2，会超时，所幸数据没有这种极端样例，aij 应该是随机生成的，所以这种解法可以通过。

不过再细想一下，如果已经考虑一个点传送到集合 v 中的某个点，那么集合 v 中的点在之后就不需要考虑互相转移（因为转移耗时是 0，如果要转移，不如当前就转移）。所以每次传送后就可以把该集合删除。这样总复杂度是 O(nmlog(nm) + nm)。

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using TP = tuple<ll, int, int, int>;
constexpr int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

int main() {
    unordered_map<int, vector<pair<int, int>>> mp;
    int n, m;
    cin >> n >> m;
    vector<vector<int>> a(n, vector<int>(m));
    vector d(n, vector(m, vector<ll>(2, LLONG_MAX / 2)));
    vector v(n, vector(m, vector<int>(2, 0)));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
            mp[a[i][j]].push_back({i, j});
        }
    }

    d[0][0][0] = 0;
    priority_queue<TP, vector<TP>, greater<TP>> q;
    q.push(make_tuple(0, 0, 0, 0));
    while (q.size()) {
        auto [dist, x, y, z] = q.top(); q.pop();
        if (v[x][y][z]) continue;
        v[x][y][z] = 1;
        // 上下左右
        for (int i = 0; i < 4; i++) {
            int nx = x + dir[i][0], ny = y + dir[i][1];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m || v[nx][ny][z] == 1) continue;
            if (d[nx][ny][z] > dist + abs(a[x][y] - a[nx][ny])) {
                d[nx][ny][z] = dist + abs(a[x][y] - a[nx][ny]);
                q.push({d[nx][ny][z], nx, ny, z});
            }
        }
        if (z == 1) continue;
        for (auto &[nx, ny] : mp[a[x][y]]) {
            if (v[nx][ny][1] || d[nx][ny][1] <= dist) continue;
            d[nx][ny][1] = dist;
            q.push({dist, nx, ny, 1});
        }
    }

    cout << min(d[n - 1][m - 1][0], d[n - 1][m - 1][1]) << "\n";
    return 0;
}