小美，你今年的算法题不难啊！

上周四在卡码网（ https://kamacoder.com/ ）举办了 美团24年春季笔试周赛。

美团这次笔试难度不大，前三道题都比较简单，信心给的足足的。

第四题和第五题比较有难度。

建议大家去卡码网体验一下大厂笔试的难度。

往期大厂笔试真题在这里： https://kamacoder.com/contest.php

以下为C++代码实现， 其他语言版本可以看卡码网（ https://kamacoder.com /）对应题目的评论区，有各个语言的实现版本。

196.小美的MT

题目链接： https://kamacoder.com/problempage.php?pid=1275

模拟+计数，思路分析

用一个变量cnt记录'M', 'T'出现的次数, 然后剩下可操作的字符数量为n-cnt, n为字符串的长度, 剩下的操作次数为k, 我们取最小值加上即可.

C++代码实现：

#include
#define endl '\n';
const int N = 10005, MOD = 1000000007;
using namespace std;
using LL = long long;
using PIL = pair<int, LL>;
using PII = pair<int, int>;
int t, ans = 0;
int main() {
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    int cnt = 0;
    for (char c : s) {
        if (c == 'M' || c == 'T') ++cnt;
    }
    ans = cnt + min(k, n - cnt);
    cout     return 0;
}

• 时间复杂度: O(n)
• 空间复杂度: O(1)

197.小美的数组询问

题目链接： https://kamacoder.com/problempage.php?pid=1276

模拟+计数，思路分析：

用一个变量cnt记录0出现的次数, 然后计算数组中所有元素的和sum, 由于sum的值是固定的, 未知值的数量为cnt个, 所以最小的数组和为sum + cnt * l, 最大的值为sum + cnt * r.

#include
#define endl '\n';
const int N = 10005, MOD = 1000000007;
using namespace std;
using LL = long long;
using PIL = pair<int, LL>;
using PII = pair<int, int>;
int t, ans = 0;
int main() {
    int n, k, cnt = 0;
    cin >> n >> k;
    int *nums = new int[n]{};
    // 输入
    for (int i = 0; i scanf("%d", nums+i);
    LL sum = 0;
    // 统计0的数量并计算数组的和
    for (int i = 0; i         sum += nums[i];
        if (!nums[i]) ++cnt;
    }
    int l, r;
    // 处理k次的询问结果
    while (k--) {
        scanf("%d%d", &l, &r);
        cout <1LL * cnt * l + sum <' ' <1LL * cnt * r + sum     }
    return 0;
}

1. 时间复杂度: O(n+q)
2. 空间复杂度: O(1)

198.小美的平衡矩阵

题目链接： https://kamacoder.com/problempage.php?pid=1277

二维前缀和，思路分析：

先求出矩阵的二维前缀和, 由于n最大为200, 所以可以枚举以[2, n]为边长的正方形的所有位置（ 先枚举边长, 然后枚举这个边长对应的正方形的左上角的横纵坐标 ）。

然后计算这个正方形内部的所有数字的和s, 然后判断是否s * 2 == i * i, 因为矩阵的数值只有0和1, 所以如果0和1的数量相等, 那么当前的正方形的所有数加起来和一定等于正方形面积的一半.

#include
using namespace std;
const int N = 10005, nOD = 1000000007;
using LL = long long;
using PIL = pair<int, LL>;
using PII = pair<int, int>;
int t, ans = 0;
int main() {
    int n;
    cin >> n;
    // 输入
    char **grid = new char*[n];
    for (int i = 0; i         grid[i] = new char[n + 1];
        scanf("%s", grid[i]);
    }
    // 计算二维前缀和
    int **prefix = new int*[n + 1];
    prefix[0] = new int[n + 1]{};
    for (int i = 0; i         prefix[i + 1] = new int[n + 1];
        for (int j = 0; j             prefix[i + 1][j + 1] = prefix[i + 1][j] + prefix[i][j + 1] - prefix[i][j] + (grid[i][j] == '1');
        }
    }
    cout <0     // 计算每个正方形边长对应的数量
    for (int k = 2; k <= n; ++k) {
        // 总面积
        int area = k * k, cnt = 0;
        for (int i = 0; i <= n - k; ++i) {
            for (int j = 0; j <= n - k; ++j) {
                // 计算1所占的面积
                int actual = prefix[i + k][j + k] - prefix[i + k][j] - prefix[i][j + k] + prefix[i][j];
                if (actual + actual == area) ++cnt;
            }
        }
        cout     }
    for (int i = 0; i delete[] grid[i];
    delete[] grid;
    for (int i = 0; i <= n; ++i) delete[] prefix[i];
    delete[] prefix;
    return 0;
}

1. 时间复杂度: O(n^3), 枚举边长O(n), 枚举正方形的左上角坐标O(n^2), 一共O(n^3)
2. 空间复杂度: O(n^2), 前缀和数组需要的空间.

199.小美的区间删除

题目链接： https://kamacoder.com/problempage.php?pid=1278

数学+滑动窗口，思路分析：

首先我们需要知道末尾的0的本质是什么, 换句话说, 末尾的0是怎么来的, 先说结论:

只有相乘的数里面有 因子2和因子5相乘才会出现末尾的0, 而且这个0的数量取决于因子2和因子5的数量 。

例如: 25 * 8=200, 末尾有两个0, 因为25包含两个5因子, 而8包含三个2因子, 取最小值, 所以末尾包含两个0. 这里不做证明, 但是不难发现这个规律.

有了上面的规律, 我们需要末尾至少有k个0, 那就是说数组里面剩下来的数, 至少要有k个2因子和5因子.

假设一开始, 我们不进行删除, 我们求出所有的数一共包含多少个2因子和5因子, 并且记录每个数的2因子和5因子的数量, 并记为总数为c2, c5, 那么我们能删除的数里面最多包含c2-k个2因子和c5-k个5因子.

由于我们要删除的部分只能是一个连续的区间, 而且区间越长包含的2因子和5因子越多. 满足单调性. 所以可以利用滑动窗口来解决.

我们考虑以每一个位置i为结尾进行删除, 可以删除的最大数量为i+1, 最小的数量为0 . 并且我们维护一个窗口, 这个窗口里面的所有数最多只能包含c2-k个2因子, c5-k个5因子.

由于我们考虑的是以每一个位置为结尾的子数组, 所以需要求出能删除的 最远的左端点在哪里 , 知道了这个左端点的位置,那么就能知道以这个位置为结尾能有多少个删除的方案.

因为最远的左端点我们都能删除, 那么如果左端点进行右移的时候, 我们也一定能删除, 因为左端点右移, 说明了区间在变短, 由于单调性的存在, 保证这个结论是对的.

所以最终知道以这个位置i为结尾的子数组能有多少种删除的方案, 这个方案数为区间的长度: i-j+1 .

Cpp

#include
#define endl '\n';
const int N = 10005, MOD = 1000000007;
using namespace std;
using LL = long long;
using PIL = pair<int, LL>;
using PII = pair<int, int>;
int t, ans = 0;
PII get25(int x) {
    int c2 = 0, c5 = 0;
    while (x >= 2) {
        if (x % 2 == 0) ++c2, x /= 2;
        else if (x % 5 == 0) ++c5, x /= 5;
        else break;
    }
    return {c2, c5};
}
int main() {
    int n, k;
    // 记录窗口的大小
    int w2 = 0, w5 = 0;
    cin >> n >> k;
    int *nums = new int[n];
    for (int i = 0; i scanf("%d", nums+i);
    // 记录并计算每一位数字的因数中包含的2和5的数量
    vector vp;
    for (int i = 0; i         auto [x, y] = get25(nums[i]);
        w2 += x, w5 += y;
        vp.emplace_back(x, y);
    }
    int c2 = 0, c5 = 0;
    // 窗口中最多只能拥有w2个2, w5个5
    w2 -= k, w5 -= k;
    // 如果一个都不删除也不能有k个尾随的0, 那么输出0
    if (w2 0 ||w5 0) {
        cout <0         return 0;
    }
    LL ans = 0;
    for (int i = 0, j = 0; i         c2 += vp[i].first;
        c5 += vp[i].second;
        while (c2 > w2 || c5 > w5) c2 -= vp[j].first, c5 -= vp[j++].second;
        ans += i - j + 1;
    }
    cout     return 0;
}

1. 时间复杂度: O(nlogC), 我们需要处理每一个数包含的2因子和5因子的数量
2. 空间复杂度: O(n), 需要存储每个数的2因子和5因子的数量

200.小美的朋友关系

题目链接： https://kamacoder.com/problempage.php?pid=1279

并查集+离散化，思路分析：

这题难度较大, 由于并查集不能支持删边的操作, 也就是说, 只能进行加边操作. 所以需要进行逆向思维, 将遗忘操作变成加边的操作.

不难发现, 由于n的范围来到了1e9, 所以如果直接开数组的话会爆内存。

所以我们需要利用离散化将所有的编号映射到从1开始编号的自然数范围内, 假设这个范围是[1, m], 其中m为所有的输入中出现的不同编号的人的总数量.

具体做法是可以利用set存储每个出现的编号, 然后对这些出现的编号进行排序, 并将他们依次赋值为从1开始的自然数.