上周四在卡码网（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<bits/stdc++.h>
#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 << ans << endl;
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<bits/stdc++.h>
#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 < n; ++i) scanf("%d", nums+i);
LL sum = 0;
// 统计0的数量并计算数组的和
for (int i = 0; i < n; ++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 << endl;
}
return 0;
}
时间复杂度: O(n+q) 空间复杂度: O(1)
198.小美的平衡矩阵
题目链接：https://kamacoder.com/problempage.php?pid=1277
二维前缀和，思路分析：
先求出矩阵的二维前缀和, 由于n最大为200, 所以可以枚举以[2, n]为边长的正方形的所有位置（先枚举边长, 然后枚举这个边长对应的正方形的左上角的横纵坐标）。
然后计算这个正方形内部的所有数字的和s, 然后判断是否s * 2 == i * i, 因为矩阵的数值只有0和1, 所以如果0和1的数量相等, 那么当前的正方形的所有数加起来和一定等于正方形面积的一半.
#include<bits/stdc++.h>
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 < n; ++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 < n; ++i) {
prefix[i + 1] = new int[n + 1];
for (int j = 0; j < n; ++j) {
prefix[i + 1][j + 1] = prefix[i + 1][j] + prefix[i][j + 1] - prefix[i][j] + (grid[i][j] == '1');
}
}
cout << 0 << endl;
// 计算每个正方形边长对应的数量
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 << cnt << endl;
}
for (int i = 0; i < n; ++i) delete[] grid[i];
delete[] grid;
for (int i = 0; i <= n; ++i) delete[] prefix[i];
delete[] prefix;
return 0;
}
时间复杂度: O(n^3), 枚举边长O(n), 枚举正方形的左上角坐标O(n^2), 一共O(n^3) 空间复杂度: 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<bits/stdc++.h>
#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 < n; ++i) scanf("%d", nums+i);
// 记录并计算每一位数字的因数中包含的2和5的数量
vector<PII> vp;
for (int i = 0; i < n; ++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 << endl;
return 0;
}
LL ans = 0;
for (int i = 0, j = 0; i < n; ++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 << ans << endl;
return 0;
}
时间复杂度: O(nlogC), 我们需要处理每一个数包含的2因子和5因子的数量 空间复杂度: O(n), 需要存储每个数的2因子和5因子的数量
200.小美的朋友关系
题目链接：https://kamacoder.com/problempage.php?pid=1279
并查集+离散化，思路分析：
这题难度较大, 由于并查集不能支持删边的操作, 也就是说, 只能进行加边操作. 所以需要进行逆向思维, 将遗忘操作变成加边的操作.
不难发现, 由于n的范围来到了1e9, 所以如果直接开数组的话会爆内存。
所以我们需要利用离散化将所有的编号映射到从1开始编号的自然数范围内, 假设这个范围是[1, m], 其中m为所有的输入中出现的不同编号的人的总数量.
具体做法是可以利用set存储每个出现的编号, 然后对这些出现的编号进行排序, 并将他们依次赋值为从1开始的自然数.
接下来我们创建两个并查集, 第一个并查集将所有初始时刻就是朋友的边全部加进去, 然后不动了, 并且记这个并查集为u1.
第二个并查集, 将要删除的(即后面会遗忘的)边全部除掉, 然后将剩下的边全部插入到第二个并查集u2, 然后我们倒序遍历整个查询数组。
每次遇到查询操作的时候, 我们就在u2里面进行查询, 看看他们是不是连通的, 如果是就记录这个查询的结果为Yes, 反之为No。
如果遇到淡忘操作, 就将这条边插入u2并查集, 由于可能会有本来就不认识的两个人淡忘的操作.
这种边我们是不能进行插入的, 所以需要利用u1判断是否这两个人初始时刻是不是认识的, 如果这两个人一开始就是认识的, 就可以将这条边加入u2. 如果不是, 就不做任何操作.
为什么要对所有查询进行逆向操作? 因为我们建立并查集u2的时候, 是提前将所有的遗忘操作全部提前进行的, 对于最后一次操作来说, 他进行查询的时候, 前面的操作一定是全部进行的, 所以这样不会影响最后一次查询的答案。
然后如果遇到了淡忘操作的时候, 我们就把这条边加入到u2并查集, 因为对于前面的操作执行的时候, 这个淡忘操作并没有执行.
注意: 最后的答案需要逆向输出.
#include<bits/stdc++.h>
#define endl '\n';
const int N = 400005, MOD = 1000000007;
using namespace std;
using LL = long long;
using PIL = pair<int, LL>;
using PII = pair<int, int>;
using T3I = tuple<int, int, int>;
int t = 0;
LL ans = 0;
// 并查集
class UnionFind {
private:
int* pa;
public:
UnionFind(int n) {
pa = new int[n];
for (int i = 0; i < n; ++i) pa[i] = i;
}
int find(int x) {
if (x == pa[x]) return x;
return pa[x] = find(pa[x]);
}
void merge(int x, int y) {
int px = find(x);
int py = find(y);
pa[px] = py;
}
~UnionFind() {
delete[] pa;
pa = nullptr;
}
};
int main() {
int n, m, q, u, v, op;
cin >> n >> m >> q;
// 存储朋友关系, 以及接下来会断开关系的边(需要删除的边)
set<PII> sp, asp;
// 存储查询
vector<T3I> queries;
// 存储所有节点的编号
set<int> node;
// 处理输入
for (int i = 0; i < m; ++i) {
scanf("%d%d", &u, &v);
node.emplace(u);
node.emplace(v);
sp.emplace(u, v);
}
for (int i = 0; i < q; ++i) {
scanf("%d%d%d", &op, &u, &v);
queries.emplace_back(op, u, v);
node.emplace(u);
node.emplace(v);
if (op == 1 && (sp.count({u, v}) || sp.count({v, u})))
asp.emplace(u, v);
}
// 进行离散化,因为n的数值比较大
unordered_map<int, int> ump;
int idx = 1;
for (int t : node) {
ump[t] = idx++;
}
// 初始化并查集
UnionFind u1(idx), u2(idx);
// 如果不删除应该会有一个怎么样的并查集存在
for (auto [x, y] : sp) {
u1.merge(ump[x], ump[y]);
}
// 为初始的朋友建立关系
for (auto [x, y] : sp) {
// 这个需要建立的关系不能在需要删除的集合中
if (asp.count({x, y}) || asp.count({y, x})) continue;
u2.merge(ump[x], ump[y]);
}
vector<int> ans;
// 倒序遍历queries,将删边变成添加边
for (int i = q - 1; i >= 0; --i) {
auto [op, x, y] = queries[i];
if (op == 2) {
if (u2.find(ump[x]) == u2.find(ump[y])) ans.push_back(1);
else ans.push_back(0);
} else {
if (u1.find(ump[x]) == u1.find(ump[y])) {
u2.merge(ump[x], ump[y]);
}
}
}
// 倒序输出答案
for (int i = ans.size() - 1; i >= 0; --i) {
cout << (ans[i] ? "Yes" : "No") << endl;
}
return 0;}