「技术笔试」美团暑期实习 2023-03-18

T1 捕获

题意

n 个敌人，每个敌人坐标 (x, y)，小美一次可以捕获很多敌人，但一次捕获的所有敌人其横坐标差不超过 a，纵坐标差不超过 b，求问一次最多可以捕获多少敌人。

n <= 500, a，b 以及 坐标范围 [1, 1000]。

思路

二维前缀和，注意 a 和 b 表示最大间隔，+1 后与 1000 取 min。时间复杂度 O(1000^2)

// 捕获
#include <bits/stdc++.h>
using namespace std;
constexpr int N = 1000;
int sum[N + 1][N + 1];
int n, a, b;

int main() {
    cin >> n >> a >> b;
    a++;
    b++;
    a = min(a, N);
    b = min(b, N);
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        sum[x][y]++;
    }
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
        }
    }
    int res = 0;
    for (int i = a; i <= N; i++) {
        for (int j = b; j <= N; j++) {
            res = max(res, sum[i][j] - sum[i - a][j] - sum[i][j - b] + sum[i - a][j - b]);
        }
    }
    cout << res << "\n";
    return 0;
}

T2 彩带

题意

长度为 n 的彩带，每一段上有一个颜色，你可以从中截取一段，但颜色种类不能超过 k 种，问最长可以截取多少。

n, k <= 5000，彩带颜色数字 [1, 2000]。

思路

双指针 + 哈希维护区间种类数，时间复杂度 O(n)。

哈希表统计每种数字出现的次数，双指针控制区间内数字的添加与删除。

// 彩带
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    unordered_map<int, int> cnt;
    int num = 0;
    auto add = [&](int x){ if (++cnt[x] == 1) num++; };
    auto sub = [&](int x){ if (--cnt[x] == 0) num--; };

    int res = 0;
    for (int i = 0, j = 0; i < n; i++) {
        cin >> a[i];
        add(a[i]);
        while (num > k) {
            sub(a[j]);
            j++;
        }
        res = max(res, i - j + 1);
    }
    cout << res << "\n";
    return 0;
}

T3 回文串

题意

给定一个字符串，你可以从中选择最多两个位置，将其字符改为 'a'~'z' 中的某一个。你需要找到可以通过修改得到的字典序最小的回文串。题目保证一定可以修改为回文串。

字符串长度 [1, 100000]。

思路

1. 首先将串变成回文串，即前 n/2 个字符与 n/2 个字符完全相同。
2. 然后如果有剩余的次数，优先使最前面的字符变为 a。注意这一步操作可能会修改第一步已经修改过的位置（如果有，则这一步只消耗一次）。
3. 如果串长度是奇数，并且还有剩余次数，则修改中间的字符。

#include <bits/stdc++.h>

using namespace std;

int main() {
    string s;
    cin >> s;
    int n = s.size();
    vector<int> v(n);

    int cnt = 2;
    // step 1
    for (int i = 0; i < n / 2; i++) {
        if (s[i] != s[n - i - 1]) {
            cnt--;
            auto to = min(s[i], s[n - i - 1]);
            s[i] = to;
            s[n - i - 1] = to;
            v[i] = 1;
        }
    }
    // step 2
    for (int i = 0; i < n / 2; i++) {
        if (s[i] != 'a') {
            int cost = v[i] == 1 ? 1 : 2;
            if (cnt >= cost) {
                cnt -= cost;
                s[i] = s[n - i - 1] = 'a';
            }
        }
    }
    // step 3
    if (cnt >= 1 && n % 2 == 1) {
        if (s[n / 2] != 'a') {
            s[n / 2] = 'a';
        }
    }

    cout << s << "\n";
    return 0;
}

T4 商店

题意

商店有 n 个商品，每个商品有原价和折扣价。小美有 m 元，一共 k 张折扣券。

首先她希望最大化购买商品的数量，然后尽量减少花费。

1 <= n <= 100, m <= 5000, k <= 50，每个商品的原价和折扣价都介于 [1, 50]。

思路

动态规划，d[i][j][t] 表示前 i 个物品中购买了 j 个物品，并使用了 t 次折扣时的最小花费。

转移，如果当前不使用折扣，则 d[i][j][t] = min(d[i][j][t], d[i - 1][j - 1][t] + p[i])。

如果使用折扣，则 d[i][j][t] = min(d[i][j][t], d[i - 1][j - 1][t - 1] + p2[i])。

时间复杂度为 O(n^2k)

// 商店

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<int> p(n + 1), p2(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> p[i] >> p2[i];
    }

    vector<vector<vector<int>>> d(n + 1, vector<vector<int>>(n + 1, vector<int>(k + 1, INT_MAX / 2)));
    d[0][0][0] = 0;
    for (int i = 1; i <= n; i++) {
        d[i] = d[i - 1];
        for (int j = 1; j <= i; j++) {
            for (int t = 0; t <= i && t <= k; t++) {
                // 原价购买
                if (d[i - 1][j - 1][t] + p[i] <= m) {
                    d[i][j][t] = min(d[i][j][t], d[i - 1][j - 1][t] + p[i]);
                }
                if (t >= 1 && d[i - 1][j - 1][t - 1] + p2[i] <= m) {
                    d[i][j][t] = min(d[i][j][t], d[i - 1][j - 1][t - 1] + p2[i]);
                }
            }
        }
    }

    int cnt = 0, cost = m + 1;
    for (int j = 0; j <= n; j++) {
        for (int t = 0; t <= k; t++) {
            if (d[n][j][t] <= m) {
                if (cnt < j) {
                    cnt = j;
                    cost = d[n][j][t]; 
                } else if (cnt == j) {
                    cost = min(cost, d[n][j][t]);
                }
            }
        }   
    }
    if (cost > m) cost = 0;
    cout << cnt << ' ' << cost << '\n';

    return 0;
}

T5 能量（具体题目名称忘记了）

题意

给定一颗 n 个节点的树，每个节点有一个能量塔，可以为距离当前点不超过给定值的点提供一点能量。问最终每个点可以获得多少能量。距离的定义是两点之间边的个数，自己也可以给自己提供能量。

n <= 500

思路

对于树上的某个点，dfs 一次即可，复杂度为 O(n^2)。

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> dis(n), res(n);
    vector<vector<int>> g(n);
    for (int i = 0; i < n; i++) {
        cin >> dis[i];
    }
    for (int i = 1; i < n; i++) {
        int x, y; cin >> x >> y;
        x--;y--;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    // <当前点、father、与起点距离、最远可达距离>
    function<void(int, int, int, int)> dfs = [&](int x, int f, int d, int mx) {
        res[x]++;
        if (d + 1 > mx) return;
        for (auto y : g[x]) {
            if (y == f) continue;
            dfs(y, x, d + 1, mx);
        }
    };

    for (int i = 0; i < n; i++) {
        dfs(i, i, 0, dis[i]);
    }

    for (int i = 0; i < n; i++) {
        cout << res[i] << " \n"[i == n - 1];
    }
    return 0;
}