以下题解为个人题解，不提供具体思路，仅提供题解代码。本题解使用的编程语言为C++。本次笔试为模拟测试，得分79/100，ac数3/5。题解内容仅供参考

美团2024年春季校园招聘 第一场笔试【技术类】 题解（C++）

美团0309春招第一场笔试

T1. 小美的平衡矩阵

小美拿到了一个𝑛∗𝑛的矩阵，其中每个元素是 0 或者 1。
小美认为一个矩形区域是完美的，当且仅当该区域内 0 的数量恰好等于 1 的数量。
现在，小美希望你回答有多少个𝑖∗𝑖的完美矩形区域。你需要回答1≤𝑖≤𝑛的所有答案。

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 256M，其他语言512M

输入描述：

第一行输入一个正整数n，代表矩阵大小。
接下来的n行，每行输入一个长度为n的 01 串，用来表示矩阵。
1 <= n <= 200

输出描述：

输出n行，第i行输出i*i的完美矩形区域的数量。

示例1

输入例子：

4
1010
0101
1100
0011

输出例子：

0
7
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 210;
char g[N][N];
int s[N][N], ans[N], n;

void io() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
}

int get(int x1, int y1, int x2, int y2) {
    return s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
}

int main() {
    io();
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> g[i][j];
            s[i][j] = g[i][j] - '0';
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            for (int k = 1; k <= n; k++) {
                if (i + k - 1 <= n && j + k - 1 <= n) {
                    int x = get(i, j, i + k - 1, j + k - 1);
                    if (x * 2 == k * k) {
                        ans[k]++;
                    }
                }
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        cout << ans[i] << '\n';
    }
    return 0;
}

T2. 小美的数组询问

小美拿到了一个由正整数组成的数组，但其中有一些元素是未知的（用 0 来表示）。
现在小美想知道，如果那些未知的元素在区间[𝑙,𝑟][l,r]范围内随机取值的话，数组所有元素之和的最小值和最大值分别是多少？
共有𝑞次询问。

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 256M，其他语言512M

输入描述：

第一行输入两个正整数n, q，代表数组大小和询问次数。
第二行输入n个整数ai，其中如果输入的ai为 0，那么说明是未知的。
接下来的q行，每行输入两个正整数l, r ，代表一次询问。
1 <= n, q <= 1e5
0 <= ai <= 1e9
1 <= l <= r <= 1e9

输出描述：

输出q行，每行输出两个正整数，代表所有元素之和的最小值和最大值。

示例1

输入例子：

3 2
1 0 3
1 2
4 4

输出例子：

5 6
8 8

例子说明：

只有第二个元素是未知的。
第一次询问，数组最小的和是 1+1+3=5，最大的和是 1+2+3=6。
第二次询问，显然数组的元素和必然为 8。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll maxn = 1e5 + 10;

void io() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
}

int main() {
    io();
    ll a[maxn];
    int n, q;
    cin >> n >> q;
    int cnt = 0;
    ll sum = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (a[i] == 0) {
            cnt++;
        }
        sum += a[i];
    }
    while (q--) {
        ll l, r;
        cin >> l >> r;
        cout << sum + cnt * l << ' ' << sum + cnt * r << '\n';
    }
    return 0;
}

T3. 小美的MT

MT 是美团的缩写，因此小美很喜欢这两个字母。
现在小美拿到了一个仅由大写字母组成字符串，她可以最多操作𝑘次，每次可以修改任意一个字符。小美想知道，操作结束后最多共有多少个’M’和’T’字符？

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 256M，其他语言512M

输入描述：

第一行输入两个正整数n, k，代表字符串长度和操作次数。
第二行输入一个长度为n的、仅由大写字母组成的字符串。
1 <= k <= n <= 1e5

输出描述：

输出操作结束后最多共有多少个'M'和'T'字符。

示例1

输入例子：

5 2
MTUAN

输出例子：

4

例子说明：

修改第三个和第五个字符，形成的字符串为 MTTAM，这样共有 4 个'M'和'T'。
#include<bits/stdc++.h>
using namespace std;

void io() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
}

int main() {
    io();
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    int cnt = 0;
    for (int i = 0; i < s.length(); i++) {
        if (s[i] == 'M' || s[i] == 'T') {
            cnt++;
        }
    }
    cout << cnt + min(k, n - cnt) << '\n';
}

T4. 小美的朋友关系

小美认为，在人际交往中，但是随着时间的流逝，朋友的关系也是会慢慢变淡的，最终朋友关系就淡忘了。
现在初始有一些朋友关系，存在一些事件会导致两个人淡忘了他们的朋友关系。小美想知道某一时刻中，某两人是否可以通过朋友介绍互相认识？
事件共有 2 种：
1 u v：代表编号 u 的人和编号 v 的人淡忘了他们的朋友关系。
2 u v：代表小美查询编号 u 的人和编号 v 的人是否能通过朋友介绍互相认识。

注：介绍可以有多层，比如 2 号把 1 号介绍给 3 号，然后 3 号再把 1 号介绍给 4 号，这样 1 号和 4 号就认识了。

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 256M，其他语言512M

输入描述：

第一行输入三个正整数n, m, q，代表总人数，初始的朋友关系数量，发生的事件数量。
接下来的m行，每行输入两个正整数u, v，代表初始编号的人u和编号的人v是朋友关系。
接下来的q行，每行输入三个正整数op, u, v，含义如题目描述所述。
1 <= n <= 1e9
1 <= m, q <= 1e5
1 <= u, v <= n
1 <= op <= 2
保证至少存在一次查询操作。

输出描述：

对于每次 2 号操作，输出一行字符串代表查询的答案。如果编号 u 的人和编号 v 的人能通过朋友介绍互相认识，则输出"Yes"。否则输出"No"。

示例1

输入例子：

5 3 5
1 2
2 3
4 5
1 1 5
2 1 3
2 1 4
1 1 2
2 1 3

输出例子：

Yes
No
No

例子说明：

第一次事件，1 号和 5 号本来就不是朋友，所以无事发生。
第二次事件是询问，1 号和 3 号可以通过 2 号的介绍认识。
第三次事件是询问，显然 1 号和 4 号无法互相认识。
第四次事件，1 号和 2 号淡忘了。
第五次事件，此时 1 号无法再经过 2 号和 3 号互相认识了。

本题未AC。但是读者可以根据我提供的思路尝试完成本题：本题实际上要求使用并查集，需要考虑离散化+离线处理，并且要考虑重边的情况

T5. 小美的区间删除

小美拿到了一个大小为𝑛的数组，她希望删除一个区间后，使得剩余所有元素的乘积末尾至少有𝑘个 0。小美想知道，一共有多少种不同的删除方案？

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 256M，其他语言512M

输入描述：

第一行输入两个正整数n, k。
第二行输入n个正整数ai，代表小美拿到的数组。
1 <= n, k <= 1e5
1 <= ai <= 1e9

输出描述：

一个整数，代表删除的方案数。

示例1

输入例子：

5 2
2 5 3 4 20

输出例子：

4

例子说明：

第一个方案，删除[3]。
第二个方案，删除[4]。
第三个方案，删除[3,4]。
第四个方案，删除[2]。

本题未完全ac，通过样例数19/20

读者可根据下面的参考代码，修改参考代码并尝试完成本题

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
typedef long long ll;
int a[maxn], cnt2[maxn], cnt5[maxn];

void io() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
}

int get(int x, int p) {
    int res = 0;
    while (x % p == 0) {
        x /= p;
        res++;
    }
    return res;
}

int main() {
    io();
    int n, k;
    cin >> n >> k;
    int c2 = 0, c5 = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    for (int i = 0; i < n; i++) {
        cnt2[i] = get(a[i], 2);
        cnt5[i] = get(a[i], 5);
        c2 += cnt2[i];
        c5 += cnt5[i];
    }

    ll res = 0;
    for (int l = 0, r = 0; r < n; r++) {
        c2 -= cnt2[r];
        c5 -= cnt5[r];
        while (min(c2, c5) < k) {
            c2 += cnt2[l];
            c5 += cnt5[l];
            l++;
        }
        res += (r - l + 1);
    }
    cout << res << '\n';
    return 0;
}